05 符号表与语义分析 | 《Let’s Build A Simple Interpreter》笔记

本系列是《Let’s Build A Simple Interpreter》的阅读笔记。

符号表

Pascal 是一个强类型语言，所以需要确保在向一个变量赋值时，类型是正确的（类型检查），以及确保变量在使用之前被声明。为了可以在运行时对程序源码进行解释/求值之前就识别出这样的问题，我们需要跟踪程序符号。符号表就是用来跟踪程序符号的组件。符号可理解为一些程序实体的标识符，可以标识程序实体的以下信息：

• 名字（例如“x”、“y”、“number”等）
• 类别（变量、子程序或内置类型等）
• 类型（INTEGER，REAL）

符号表是一种抽象数据结构（ADT），用来跟踪源码中的各种符号。在这篇文章中，符号表被实现为一个包含辅助方法的单独的类：

class Symbol():
    def __init__(self, name, type=None):
        self.name = name
        self.type = type
        self.catetory = catetory


# 内置符号
class BuiltinTypeSymbol(Symbol):
    def __init__(self, name):
	    super(BuiltinTypeSymbol, self).__init__(name)

    def __str__(self):
	    return self.name

    def __repr__(self):
	    return f"<{self.__class__.__name__}(name='{self.name}')"


# 变量符号
class VarSymbol(Symbol):
    def __init__(self, name, type):
	    super(VarSymbol, self).__init__(name, type)

    def __str__(self):
	    return f"<{self.__class__.__name__}(name='{self.name}', type='{self.type}')"

    __repr__ = __str__


class SymbolTable(object):
    def __init__(self):
        self._symbols = OrderedDict()
        self._init_builtins()

    def _init_builtins(self):
        self.insert(BuiltinTypeSymbol('INTEGER'))
        self.insert(BuiltinTypeSymbol('REAL'))

    def __str__(self):
        symtab_header = 'Symbol table contents'
        lines = ['\n', symtab_header, '_' * len(symtab_header)]
        lines.extend(
            ('%7s: %r' % (key, value))
            for key, value in self._symbols.items()
        )
        lines.append('\n')
        s = '\n'.join(lines)
        return s

    __repr__ = __str__

    def insert(self, symbol):
        print('Insert: %s' % symbol.name)
        self._symbols[symbol.name] = symbol

    def lookup(self, name):
        print('Lookup: %s' % name)
        symbol = self._symbols.get(name)
        # 'symbol' is either an instance of the Symbol class or None
        return symbol

语义分析

就算程序是语法上正确的且可以成功地构建抽象语法树，它仍然可能包含一些非常严重的错误。检查这些错误的操作即为语义分析，顾名思义，这是判断一个程序是否有意义的过程。在添加语义分析阶段之后，Pascal 解释器的结构就会是这样：

从上面的图片中可以看到 lexer 将源代码作为输入，将其转换为 token 作为 parser 的输入从而验证程序是语法正确的，然后 parser 会生成一个抽象语法树，语义分析阶段会使用该语法树来确保程序符合不同的 Pascal 语言要求。在语义分析阶段中，语义分析器会建立并使用符号表。在语义分析之后，解释器会得到该语法树，通过遍历该语法树来对程序进行求值并产生程序输出。

符号和符号表

通过遍历由 parser 建立的 AST 可以将建立符号表的过程自动化：

class SemanticAnalyzer(NodeVisitor):
    def __init__(self):
        self.symtab = SymbolTable()
    
    def visit_Block(self, node):
        for declaration in node.declarations:
        self.visit(declaration)
        self.visit(node.compound_statement)

    def visit_Program(self, node):
        self.visit(node.block)
    
    def visit_Compound(self, node):
        for child in node.children:
            self.visit(child)
    
    def visit_NoOp(self, node):
        pass
    
    def visit_BinOp(self, node):
        self.visit(node.left)
        self.visit(node.right)

    def visit_VarDecl(self, node):
        type_name = node.type_node.value
        type_symbol = self.symtab.lookup(type_name)

        # We have all the information we need to create a variable symbol.
        # Create the symbol and insert it into the symbol table.
        var_name = node.var_node.value
        var_symbol = VarSymbol(var_name, type_symbol)

        # Signal an error if the table alrady has a symbol with the same name
        if self.symtab.lookup(var_name) is not None:
            raise Exception("Error: Duplicate identifier '%s' found" % var_name)
        
        self.symtab.insert(var_symbol)

    def visit_Assign(self, node):
        # right-hand side
        self.visit(node.right)
        # left-hand side
        self.visit(node.left)

    def visit_Var(self, node):
        var_name = node.value
        var_symbol = self.symtab.lookup(var_name)

        if var_symbol is None:
            raise Exception("Error: Symbol(identifier) not found '%s'" % var_name)

前面的方法都是遍历各个 op 的子节点，visit_VarDecl 函数才是关键。这个方法负责访问（遍历）VarDecl 结点并将相应的符号保存到符号表中。首先，该方法根据名字从符号表中查找内置类型，然后创建一个 VarSymbol 的实例，名字是变量名，类型为刚才查找到的内置类型，并将它保存（定义）在符号表中。