本系列文章参考国外编程高手鲁斯兰的博客文章《Let’s Build A Simple Interpreter》。
通过前面的学习，我们了解了以下内容：
1、 如何把语句分解为记号。
这个过程叫做词法分析（lexical analysis）。
解释器的一部分被称作词法分析器（lexical analyzer或 lexer）、扫描器（scanner）或记录器（tokenizer）。
我们已经学会不借助正则表达式或其它任何工具（例如Lex）从底层编写我们的词法分析器。
2、 如何识别出记号流中的短语。
在记号流中识别一个短语的过程，或者说，在记号流中找到短语结构的过程称为解析（parsing）或语法分析（syntax analysis）。
解释器或编译器中，完成这项工作的部分称为解析器（parser）或语法分析器（syntax analyzer）。
3、 如何用语法图来表示编程语言的语法规则。
语法图是编程语言中语法规则的图形表示，它直观地表达了在我们的编程语言中哪些语句是允许的，哪些是不允许的。
4、 如何使用另一种广泛使用的表示法来指定编程语言的语法。
这里说的是上下文无关文法（context-free grammars），简称为文法（grammars）或BNF（Backus-Naur Form）。
5、 如何将文法映射到代码，以及如何编写递归下降解析器（recursive-descent parser）。
6、 如何编写一个真正的基本解释器（interpreter）。
7、 运算符的结合律（associativity）和优先级（precedence）如何工作，以及如何使用优先级表构造文法。
8、 如何构造一个解析语句的抽象语法树（Abstract Syntax Tree ：AST），以及如何将Pascal的整个源程序表示为一个大的AST。
9、 如何访问AST，以及如何将我们的解释器作为AST节点访问器来实现。
正如上面所说的，凭借我们的知识和经验，我们已经建立了一个解释器，可以进行词法分析、语法分析和构建AST，并通过访问AST来解释我们的第一个完整的Pascal程序。
如果你一直没有松懈的学习完上面所说的内容，并已理解这些内容，那么收获一定是很多的。
不过，虽然我们已经覆盖了很多方面，但还有更令人兴奋的内容正在到来。
到目前为止，我们差不多已经准备好去处理以下内容：
- 嵌套过程与函数
- 过程与函数调用
- 语义分析（类型检查，确保变量在使用之前声明，并且基本上检查程序是否有意义。）
- 控制流程单元（例如if语句）
- 聚合数据类型（Records）
- 更多内置类型
- 源代码级调试器（Source-level debugger）
- 其它上面没有提到优点
但是，在我们接触这些内容之前，我们需要先建立坚实的基础以及必要设施。
这里所指的是符号、符号表和域这些超级重要的内容。
这些内容会涵盖几篇文章。
一、 符号（Symbol）
首先，我们要了解什么是符号，以及我们为什么要对符号进行追踪。
出于我们的目的，我们非正式地将符号定义为某些程序实体的标识符，例如变量、子程序或内置类型。
如果想符号有用，它们至少需要获取它们所识别的程序实体的以下信息：
- 名称：例如“x”、“y”或“number”等。
- 类别：例如变量、子程序或内置类型。
- 类型：例如整数或实数。
这篇文章中，我们将处理变量符号和内置类型符号，因为我们以前已经使用过变量和类型。
提示：“内置类型”是指非自定义的类型，可以直接使用，例如之前的INTEGER和REAL类型。
我们来看一段Pascal程序，注意变量声明部分。
示例代码：
PROGRAM Part11; VAR x : INTEGER; y : REAL; BEGIN END.
我们能够看到，在上面这段代码中有4个符号：两个变量符号（x和y）和两个内置类型符号（INTEGER和REAL）。
1、如何在代码中表示符号？
我们可以创建一个基本符号类，类的参数为符号的名称“name”和类型“symbol_type”。
注意，并非所有符号都有与之关联的类型，所以符号类型是可选参数。
示例代码：
class Symbol: # 添加符号类
def __init__(self, name, symbol_type=None):
self.name = name # 符号名称
self.symbol_type = symbol_type # 符号类型
2、如何在代码中表示内置类型符号？
在符号类的代码中，我们没有看到类别的参数（注意类别和类型是两个概念）。
不同类别的符号，我们以类的类名来体现。
这意味着我们需要创建单独的类来表示不同的符号类别。
我们从基本的内置类型开始。
内置类型符号类继承自符号类，构造函数只需要类型的名称。
示例代码：
class BuiltinTypeSymbol(Symbol): # 添加内置类型符号类
def __init__(self, name):
super().__init__(name) # 调用基类构造函数初始化
def __str__(self):
return self.name # 返回符号名称
__repr__ = __str__
提示：在前文已经有过详细的介绍，双下划线（double underscore：简称dunder）中的方法__str__()和__repr__()是特殊的Python方法（或者叫魔法方法），通过这两个方法我们已经让它们具有良好的格式化消息，通过print()函数打印符号对象或者在Python Shell中创建符号对象并输入这个对象名称后回车时即可看到。
启动Python Shell，我们查看一下：
3、如何在代码中表示变量符号？
按照前面所说的，类名表示不同类别的符号，我们需要创建一个VarSymbol类。
示例代码：
class VarSymbol(Symbol): # 添加变量符号类
def __init__(self, name, symbol_type):
super().__init__(name, symbol_type) # 调用基类构造函数初始化
def __str__(self):
return f'<{self.name}:{self.symbol_type}>' # 返回符号信息
__repr__ = __str__
在变量符号类中，变量的名称和类型都是必选参数，类名“VarSymbol”表明类的实例将标识一个变量符号（类别是变量）。
再次进入Python shell，我们手动构造变量符号的实例：
正如我们所看到的，首先创建一个内置类型符号的实例，然后将它作为参数传递给VarSymbol类的构造函数。
符号的层次结构如下图所示：
二、跟踪符号
跟踪符号的原因主要包括：
- 为了确保当我们为变量赋值时，类型是正确的（类型检查）；
- 确保在使用变量之前声明变量；
下面是一个的错误Pascal程序代码：
PROGRAM Part11; VAR x : INTEGER; y : REAL; BEGIN y := 3.5; x := 2 + y; x := a; END.
上面的程序代码有两个问题：
1、在赋值语句“x := 2 + y”中，我们给变量“x”声明为整数类型，但是赋值却是整数与实数之和（实数类型），因此导致类型不兼容，无法解释。
2、在赋值语句“x := a”中，我们引用了未声明的变量“a”。
为了能够在运行时，对程序的源代码解释或求值之前识别这样的情况，我们需要跟踪程序符号。
那么，在哪里存储我们追踪的符号呢？
大家应该还记得符号表（symbol table）。
符号表是一种抽象数据类型（Abstract Data Type：ADT），用于跟踪源代码中的各种符号。
与之前不同，在这篇文章中，我们将把符号表实现为一个单独的类，并使用一些辅助方法。
我们将用符号表来执行两个主要操作：存储符号并能够按名称查找。
因此，我们需要定义两个辅助方法：define()和lookup()。
define()方法以符号对象作参数，并以符号对象的名称为key和符号对象自身为value，将符号对象存储在内部的有序字典中。
lookup()方法将符号对象名称作为参数，如果找到符号对象，则返回一个符号对象，否则返回None。
示例代码：
class SymbolTable: # 添加符号表类
def __init__(self):
self._symbols = OrderedDict() # 存储符号的有序字典
def __str__(self):
return f'Symbols:{[value for value in self._symbols.values()]}' # 返回符号列表信息
__repr__ = __str__
def define(self, symbol): # 添加定义符号的方法
print(f'定义：{symbol}')
self._symbols[symbol.name] = symbol # 符号添加到字典
def lookup(self, name): # 添加查询符号的方法
print(f'查询：{name}')
return self._symbols.get(name) # 返回符号对象
我们尝试为下方的Pascal程序手动填充符号表，包括创建变量符号和内置类型符号：
PROGRAM Part11; VAR x : INTEGER; y : REAL; BEGIN END.
再次启动Python shell：
如果你能够看到符号字典的内容，会像下图这样：
那么，如何让程序自动构建符号表呢？
我们编写另一个节点访问器类来访问由语法分析器构建的AST。
这是另一个拥有像AST这样的中间形式有用的例子。
我们不是扩展我们的语法分析器来处理符号表，而是分开关注点并编写一个新的节点访问器类。
在这样做之前，让我们在创建符号表实例时扩展符号表类来初始化内置类型。
下面是符号表类的全部源代码。
示例代码：
class SymbolTable: # 添加符号表类
def __init__(self):
self._symbols = OrderedDict() # 存储符号的有序字典
self.__init_builtins() # 初始化内置类型符号
def __init_builtins(self): # 添加初始化内置类型符号的方法
self.define(BuiltinTypeSymbol('INTEGER')) # 定义整数类型符号
self.define(BuiltinTypeSymbol('REAL')) # 定义实数类型符号
def __str__(self):
return f'Symbols:{[value for value in self._symbols.values()]}' # 返回符号列表信息
__repr__ = __str__
def define(self, symbol): # 添加定义符号的方法
print(f'定义：{symbol}')
self._symbols[symbol.name] = symbol # 符号添加到字典
def lookup(self, name): # 添加查询符号的方法
print(f'查询：{name}')
return self._symbols.get(name) # 返回符号对象
下面实现符号表生成器（AST节点访问器）的源代码。
需要注意，符号表的创建是为了跟踪符号，所以也需要对AST进行访问，这一点和解释器很像，方法代码有很多相同之处。
不过符号表不负责解释工作，只是对符号的定义与赋值进行验证。
当符号表完成验证之后，解释器才会对AST进行访问，执行解释过程。
基于上面所说的内容，我们添加符号表生成器类中的方法，这些方法都应与访问AST中的符号有关（注意注释中括号部分）。
示例代码：
class SymbolTableBuilder(NodeVisitor): # 添加符号表生成器类
def __init__(self): # 初始化
self.symbol_table = SymbolTable() # 创建符号表对象
def visit_Program(self, node): # 添加访问程序节点的方法
self.visit(node.block) # 访问块节点（块中可能包含符号）
def visit_Block(self, node): # 添加访问块节点的方法
for declaration in node.declarations: # 遍历声明节点
self.visit(declaration) # 访问声明语句节点（声明语句中可能包含符号）
self.visit(node.compound_statement) # 访问复合语句节点
def visit_VarDecl(self, node): # 添加访问变量声明节点方法
type_name = node.type_node.value # 获取变量类型名称
symbol_type = self.symbol_table.lookup(type_name) # 获取变量类型
var_name = node.var_node.value # 获取变量名称
var_symbol = VarSymbol(var_name, symbol_type) # 创建变量符号对象
self.symbol_table.define(var_symbol) # 变量符号对象添加到符号表
def visit_Compound(self, node): # 添加访问复合语句节点的方法
for child in node.children: # 遍历语句节点列表
self.visit(child) # 访问语句节点（语句中可能包含符号）
def visit_NoOperator(self, node): # 添加访问空语句的节点
pass # 不做任何处理（空语句之后的语句可能包含符号，需要跳过空语句）
def visit_BinaryOperator(self, node): # 添加访问二元运算符方法（二元运算中可能包含符号）
self.visit(node.left) # 访问左侧节点
self.visit(node.right) # 访问右侧节点
def visit_Num(self, node): # 添加访问数字的方法
pass # 不做任何处理（数字节点之后的内容可能包含符号，需要跳过数字，因为不进行解释，也无需返回数字的值）
def visit_UnaryOperator(self, node): # 添加访问一元运算符方法
self.visit(node.expr) # 访问表达式节点（表达式中可能包含符号）
我们以前在解释器类中见过大多数方法，但是visit_VarDecl()方法值得特别注意。
该方法负责访问（或者叫walking）一个VarDecl（变量声明）的AST节点并将相应的变量符号存储到符号表中。
首先，该方法在符号表中按名称查找内置类型符号，然后创建VarSymbol类的实例，并将其存储（或者叫定义）在符号表中。
我们用符号表生成器（AST 访问器）进行测试，查看运行中的动作。
测试代码：
PROGRAM Part11; VAR x : INTEGER; y : REAL; BEGIN END.
测试结果：
在上面的交互会话中，您可以看到“定义：…”和“查询：…”消息的序列，这些消息指示符号在符号表中定义和查找的顺序。
会话中的最后一个命令打印符号表的内容，我们可以看到它与我们以前手动构建的符号表的内容完全相同。
AST访问器的好处在于他们几乎自动完成了所有的工作。
我们可以很好的利用符号表和符号表生成器，使用它们来验证变量在赋值和表达式中使用之前完成了声明。
需要做的是在访问器中再添加两个两个方法：visit_Assign()和 visit_Variable()。
示例代码：
def visit_Assign(self, node): # 添加访问赋值节点的方法
var_name = node.left.name # 获取变量名称
var_symbol = self.symbol_table.lookup(var_name) # 查询变量符号
if var_symbol is None: # 如果变量未声明
raise NameError(f'错误的标识符：{repr(var_name)}') # 抛出名称错误异常
self.visit(node.right) # 访问右侧节点（赋值语句右侧可能包含符号）
def visit_Variable(self, node): # 添加访问变量节点的方法
var_name = node.name # 获取变量名称
var_symbol = self.symbol_table.lookup(var_name) # 查询变量符号
if var_symbol is None: # 如果变量未声明
raise NameError(f'错误的标识符：{repr(var_name)}') # 抛出名称错误异常
如果无法从符号表中查询到符号对象，这些方法将引发名称错误。
下面我们通过错误的程序代码，进行验证。
错误代码：（代码中引用了未声明的变量“b”）
PROGRAM NameError1; VAR a : INTEGER; BEGIN a := 2 + b; END.
我们来看一下，如果我们为程序构造一个AST并将它传递给我们的符号表生成器去访问，将会怎么样？
打开Python Shell进行测试：
结果符合我们的预期。
再来看另外一个错误的示例。
错误示例：（给尚未声明的变量“a”赋值）
PROGRAM NameError2; VAR b : INTEGER; BEGIN b := 1; a := b + 2; END.
打开Python Shell进行测试：
通过测试，我们的新访问器同样发现了这个问题。
再次强调一下：我们的符号表生成器（AST访问器）所做的所有检查都是在运行时之前进行的，也就是在我们的解释器解释源程序之前完成的。
我们通过解释下面的程序，彻底把这个概念了解清楚：
PROGRAM Part11; VAR x : INTEGER; BEGIN x := 2; END.
在程序退出之前，符号表和运行时GLOBAL_MEMORY的内容将是这样的：
我们能够看到符号表不会为变量“x”保存它的值“2”。
因为保存变量值是由解释器完成。
还记得第9部分中符号表用作全局存储的图片吗？
现在，我们已经我们有效地去掉了符号表作为全局存储的双重任务。
接下来，我们修改一下解释器和主程序，并通过测试代码进行测试。
测试代码：
PROGRAM Part11;
VAR
number : INTEGER;
a, b : INTEGER;
y : REAL;
BEGIN {Part11}
number := 2;
a := number ;
b := 10 * a + 10 * number DIV 4;
y := 20 / 7 + 3.14
END. {Part11}
示例代码：（Interpreter）
class Interpreter(NodeVisitor): # 修改解释器
def __init__(self, tree): # 修改构造方法
self.tree = tree # 获取参数AST
self.GLOBAL_MEMORY = OrderedDict() # 创建全局存储字典
...省略访问方法...
def interpret(self): # 修改解释方法
tree = self.tree # 获取AST
if tree is None: # 如果AST不存在
return '' # 返回空字符串
return self.visit(tree) # 否则访问AST
示例代码：（主程序）
def main():
text = '''
PROGRAM Part11;
VAR
number : INTEGER;
a, b : INTEGER;
y : REAL;
BEGIN {Part11}
number := 2;
a := number ;
b := 10 * a + 10 * number DIV 4;
y := 20 / 7 + 3.14
END. {Part11}
'''
lexer = Lexer(text)
parser = Parser(lexer)
tree = parser.parser()
symtab_builder = SymbolTableBuilder()
symtab_builder.visit(tree)
print('符号表中的内容：\n', symtab_builder.symbol_table)
print('-----------------------------------------------')
print('开始解释代码...')
interpreter = Interpreter(tree)
interpreter.interpret()
print('全局存储中的内容：')
for k, v in interpreter.GLOBAL_MEMORY.items():
print(f'{k}：{v}')
运行程序代码的结果如下：
定义：INTEGER
定义：REAL
查询：INTEGER
定义：<number:INTEGER>
查询：INTEGER
定义：<a:INTEGER>
查询：INTEGER
定义：<b:INTEGER>
查询：REAL
定义：<y:REAL>
查询：number
查询：a
查询：number
查询：b
查询：a
查询：number
查询：y
符号表中的内容：
Symbols:[INTEGER, REAL, <number:INTEGER>, <a:INTEGER>, <b:INTEGER>, <y:REAL>]
-----------------------------------------------
开始解释代码...
全局存储中的内容：
number：2
a：2
b：25
y：5.997142857142857
这里再强调一下，解释器类与构建符号表无关，它依赖于符号表生成器，以确保源代码中的变量在被解释器使用之前已经正确的声明。
最后，检查一下自己对概念的理解：
- 符号是什么？
- 为什么我们需要跟踪符号？
- 符号表是什么？
- 定义符号和解析/查找符号有什么区别？
- 下面给定的Pascal小程序，符号表和全局存储（解释器中的全局存储字典字典）分别是什么内容？
PROGRAM Part11; VAR x, y : INTEGER; BEGIN x := 2; y := 3 + x; END.
下一篇文章中，我们继续学习解析嵌套过程的内容。
项目源代码下载：【点此下载】
转载请注明：魔力Python » 一起来写个简单的解释器（11）