绕来绕去，千辛万苦，我们终于创建了抽象语法树，完成了对整个源代码结构性的分析，似乎可以喘一口气了。但是，对于下面的代码：

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

可以得到下面的抽象语法树图示：

图6-1. 抽象语法树
但并不代表代码已经没有语法错误了。很明显，因为这里并没有定义变量a，而且函数也没有返回值。针对这样的情况，还需要对代码进行进一步的检查。
        在进行检查之前，我们先研究如何遍历这棵树。回顾一下，我们使用AST派生出多种节点来存储各种不同的表达式、声明和语句。比如存储函数定义的节点FunctionDefn：

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

是由多个其它类型的节点组成，并且相互之间存在联系。对访问函数体而言，其实就是访问CompoundStatement节点。而该节点则由更多的声明节点Declaration和具体的语句节点如IfStatement组成。因此，可以从根节点出发，按照节点的具体类型进行逐次地遍历。基于这种方法，我们引入python中的属性函数getattr()，进行如下设计：

• 修改模板节点

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)

我们将从当前节点出发，遍历所有用visit_前缀和具体节点类名组成的定义在visitor中的函数，称之为节点函数，如果没有对应的实现，则会往父类方向遍历，直到模板节点AST为止，因为我们会定义一个模板节点的函数，以阻止遍历往更基类的方向进行。
        有了上面遍历抽象语法树的方式，我们将语义分析分成声明检查、流程检查和类型检查三个部分进行分别检查。

6.1 声明检查

        简单地说，就是看变量使用之前是否已经被声明。由于C语言允许在不同作用域定义同名变量。因此，这部分检查还需要考虑作用域，其一般用大括号对{}划分。我们先定义一个这样的作用域类：

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用来存储所有声明的变量，而每一个作用域enclosing_scope都会有自己的_symbols。整个类型检查的逻辑就是：变量在声明的时候，会被插入到当前作用域的_symbols中。当某个变量被使用的时候，则用lookup进行查找，如果不能在当前或者更上一层的作用域范围内找到，则可以判断该变量没有被声明。那么，剩下的任务就是遍历抽象语法树，找到可能存在变量声明和使用的地方。
        接下来，我们开始遍历抽象语法树。首先定义如下的类：

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的引入有助于我们调用getattr()获取当前的visit_函数。同时，我们使用push和pop方法来保护当前父作用域，同时创建出新的子作用域。例如，CompoundStatement节点中会引入大括号，从而将引入新的作用域，因此访问这个节点函数时，我们需要先将当前作用域压入栈，创建新的作用域，然后访问组成它的节点，访问完毕再从栈中弹出父作用域，这样就有效地保护了不同作用域声明的变量。
        考虑这部分最开头的源代码，我们在SymbolTableVisitor中定义所关心的可能会包含变量的节点函数：

    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)

上面函数名前缀为visit_的即为节点函数。从visit_TranslationUnit进入，通过visit函数，我们会遍历以下的节点函数：

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

那么，我们如何判断变量是否使用之前已经声明了呢？

    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)

由于所有的变量都用节点Id存储，访问BinOp之后将访问Id，从而检查出对应的问题。如果对源代码进行修改如果，在最上面添加：

int a;

那么，我们遍历到声明节点，并通过visit_Declaration插入变量：

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

当再次经由BinOp访问Id时，就能够找到对应的已经声明的变量了。

        但是，我们研究的这段源代码中还有一个问题尚未解决：返回值检查。这部分内容，将在下一部分的流程检查中进行。

实现简易的C语言编译器（part 0）
实现简易的C语言编译器（part 1）
实现简易的C语言编译器（part 2）
实现简易的C语言编译器（part 3）
实现简易的C语言编译器（part 4）
实现简易的C语言编译器（part 5）
实现简易的C语言编译器（part 6）
实现简易的C语言编译器（part 7）
实现简易的C语言编译器（part 9）