? ? ? ? 繞來(lái)繞去绰上，千辛萬(wàn)苦泡垃，我們終于創(chuàng)建了抽象語(yǔ)法樹析珊，完成了對(duì)整個(gè)源代碼結(jié)構(gòu)性的分析，似乎可以喘一口氣了蔑穴。但是唾琼，對(duì)于下面的代碼：

int main()
{
    a = 1;
    return;
}

可以得到下面的抽象語(yǔ)法樹圖示：

圖6-1. 抽象語(yǔ)法樹

class FunctionDefn(AST):
    """A node representing a function definition"""
    def __init__(self, declaration, body):
        self.name = declaration.name
        self.type = declaration.type
        self.return_type = declaration.type.child
        self.body = body

是由多個(gè)其它類型的節(jié)點(diǎn)組成，并且相互之間存在聯(lián)系品山。對(duì)訪問(wèn)函數(shù)體而言胆建，其實(shí)就是訪問(wèn)CompoundStatement節(jié)點(diǎn)。而該節(jié)點(diǎn)則由更多的聲明節(jié)點(diǎn)Declaration和具體的語(yǔ)句節(jié)點(diǎn)如IfStatement組成肘交。因此笆载，可以從根節(jié)點(diǎn)出發(fā)，按照節(jié)點(diǎn)的具體類型進(jìn)行逐次地遍歷涯呻×棺ぃ基于這種方法，我們引入python中的屬性函數(shù)getattr()复罐，進(jìn)行如下設(shè)計(jì)：

• 修改模板節(jié)點(diǎn)

class AST(object):
    ...

    def visit(self, visitor):
        return self.dig_visit(self.__class__, visitor)

    def dig_visit(self, node, visitor):
        """appending the class' name with 'visit_'"""
        method_name = 'visit_' + node.__name__
        visitor_method = getattr(visitor, method_name, None)
        if visitor_method is None:
            # call the class's superclass
            bases = node.__bases__
            last = None
            for child in bases:
                last = self.dig_visit(child, visitor)
            return last
        else:
            return visitor_method(self)

我們將從當(dāng)前節(jié)點(diǎn)出發(fā)涝登，遍歷所有用visit_前綴和具體節(jié)點(diǎn)類名組成的定義在visitor中的函數(shù)，稱之為節(jié)點(diǎn)函數(shù)效诅，如果沒有對(duì)應(yīng)的實(shí)現(xiàn)胀滚，則會(huì)往父類方向遍歷咳短，直到模板節(jié)點(diǎn)AST為止，因?yàn)槲覀儠?huì)定義一個(gè)模板節(jié)點(diǎn)的函數(shù)蛛淋，以阻止遍歷往更基類的方向進(jìn)行咙好。
? ? ? ? 有了上面遍歷抽象語(yǔ)法樹的方式，我們將語(yǔ)義分析分成聲明檢查褐荷、流程檢查和類型檢查三個(gè)部分進(jìn)行分別檢查勾效。

6.1 聲明檢查

? ? ? ? 簡(jiǎn)單地說(shuō)，就是看變量使用之前是否已經(jīng)被聲明叛甫。由于C語(yǔ)言允許在不同作用域定義同名變量层宫。因此，這部分檢查還需要考慮作用域其监，其一般用大括號(hào)對(duì){}劃分萌腿。我們先定義一個(gè)這樣的作用域類：

class ScopedSymbolTable:
    """scoped symbol table for look up"""
    def __init__(self, enclosing_scope=None):
        self._symbols = {}
        self.enclosing_scope = enclosing_scope

    # insert symbols
    def insert(self, name, value):
        """add symbol with the given value"""
        if name in self._symbols:
            if not self._symbols[name].type == value.type:
                comment = f"Variable '{name}' has declared before."
                raise Exception(comment)
       
        self._symbols[name] = value

    # look up symbols
    def lookup(self, name):
        symbol = self._symbols.get(name)

        if symbol is not None:
            return symbol

        # recursively go up the chain and lookup the name
        if self.enclosing_scope is not None:
            return self.enclosing_scope.lookup(name)
        else:
            return None

其中，symbols用來(lái)存儲(chǔ)所有聲明的變量抖苦，而每一個(gè)作用域enclosing_scope都會(huì)有自己的_symbols毁菱。整個(gè)類型檢查的邏輯就是：變量在聲明的時(shí)候，會(huì)被插入到當(dāng)前作用域的_symbols中锌历。當(dāng)某個(gè)變量被使用的時(shí)候贮庞，則用lookup進(jìn)行查找，如果不能在當(dāng)前或者更上一層的作用域范圍內(nèi)找到究西，則可以判斷該變量沒有被聲明窗慎。那么，剩下的任務(wù)就是遍歷抽象語(yǔ)法樹卤材，找到可能存在變量聲明和使用的地方遮斥。
? ? ? ? 接下來(lái)，我們開始遍歷抽象語(yǔ)法樹扇丛。首先定義如下的類：

class NodeVisitor(object):
    def visit(self, node):
        return node.visit(self)

    def visit_list(self, _list):
        """like NodeList in parser"""
        last = None
        for child in _list:
            last = child.visit(self)
        return last

class SymbolTableVisitor(NodeVisitor):
    def __init__(self):
        self.current_scope = None

    def push_table(self, node):
        """push the current_scope into stack and create a child scope"""
        self.current_scope = ScopedSymbolTable(
            enclosing_scope=self.current_scope 
        )

    def pop_table(self):
        """restore the parent scope"""
        self.current_scope = self.current_scope.enclosing_scope

基類NodeVisitor的引入有助于我們調(diào)用getattr()獲取當(dāng)前的visit_函數(shù)术吗。同時(shí)，我們使用push和pop方法來(lái)保護(hù)當(dāng)前父作用域，同時(shí)創(chuàng)建出新的子作用域。例如涯竟，CompoundStatement節(jié)點(diǎn)中會(huì)引入大括號(hào)规惰，從而將引入新的作用域，因此訪問(wèn)這個(gè)節(jié)點(diǎn)函數(shù)時(shí)堤器，我們需要先將當(dāng)前作用域壓入棧昆庇，創(chuàng)建新的作用域，然后訪問(wèn)組成它的節(jié)點(diǎn)闸溃，訪問(wèn)完畢再?gòu)臈Ｖ袕棾龈缸饔糜蛘海@樣就有效地保護(hù)了不同作用域聲明的變量拱撵。
? ? ? ? 考慮這部分最開頭的源代碼，我們?cè)?code>SymbolTableVisitor中定義所關(guān)心的可能會(huì)包含變量的節(jié)點(diǎn)函數(shù)：

    def visit_AST(self, node):
        pass

    """root"""
    def visit_TranslationUnit(self, node):
        """the entry of the file"""
        self.current_scope = ScopedSymbolTable(
            enclosing_scope=self.current_scope 
        )
        self.visit_NodeList(node)
        node.scope_symbol = self.current_scope

    """for all list derived from NodeList, eg. DeclarationList."""
    def visit_NodeList(self, node):
        self.visit_list(node.nodes)

    """expressions"""
    def visit_BinOp(self, node):
        node.left.visit(self)
        node.right.visit(self)

    """functions"""
    def visit_FunctionDefn(self, node):
        self.add_symbol(node)
        self.push_table(node)
        node.body.visit(self)
        self.pop_table()

    """statements"""
    def visit_CompoundStatement(self, node):
        self.push_table(node)
        node.declarations.visit(self)
        node.statements.visit(self)
        self.pop_table()

    def visit_ExpressionStatement(self, node):
        node.expr.visit(self)

    def visit_ReturnStatement(self, node):
        node.expr.visit(self)

上面函數(shù)名前綴為visit_的即為節(jié)點(diǎn)函數(shù)表蝙。從visit_TranslationUnit進(jìn)入拴测，通過(guò)visit函數(shù)，我們會(huì)遍歷以下的節(jié)點(diǎn)函數(shù)：

visit_TranslationUnit -> visit_FunctionDefn->visit_CompoundStatement\
->visit_ExpressionStatement->visit_BinOp->visit_AST

那么府蛇，我們?nèi)绾闻袛嘧兞渴欠袷褂弥耙呀?jīng)聲明了呢集索？

    def visit_Id(self, node):
        symbol = self.current_scope.lookup(node.expr)
        if symbol is None:
            comment = f"Identifier '{node.expr}' not found."
            raise Exception(comment)

由于所有的變量都用節(jié)點(diǎn)Id存儲(chǔ)，訪問(wèn)BinOp之后將訪問(wèn)Id汇跨，從而檢查出對(duì)應(yīng)的問(wèn)題务荆。如果對(duì)源代碼進(jìn)行修改如果，在最上面添加：

int a;

那么穷遂，我們遍歷到聲明節(jié)點(diǎn)函匕，并通過(guò)visit_Declaration插入變量：

  """declarations"""
    def visit_Declaration(self, node):
        self.current_scope.insert(node.name, node)

當(dāng)再次經(jīng)由BinOp訪問(wèn)Id時(shí)，就能夠找到對(duì)應(yīng)的已經(jīng)聲明的變量了蚪黑。

? ? ? ? 但是盅惜，我們研究的這段源代碼中還有一個(gè)問(wèn)題尚未解決：返回值檢查。這部分內(nèi)容忌穿，將在下一部分的流程檢查中進(jìn)行酷窥。

實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 0）
實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 1）
實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 2）
實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 3）
實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 4）
實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 5）
實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 6）
實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 7）
實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 9）
實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 10）
實(shí)現(xiàn)簡(jiǎn)易的C語(yǔ)言編譯器（part 11）