原文：Let’s Build A Simple Interpreter. Part 7: Abstract Syntax Trees
译文：
正如我上次承诺的那样，今天我们将讨论一个在接下来整个系列中都会使用的重要数据结构，所以准备好，我们开始。
到目前为止，我们将解析器和解释器的代码混合在一起，当解析器识别出某个语言结构（例如加法、减法、乘法或除法）时，解释器会立即对表达式进行求值。这类解释器被称为语法导向解释器，它们通常只对输入进行一次处理，适用于简单的语言应用。为了处理更复杂的Pascal编程语言结构，我们需要构建一种中间表示（IR）。解析器将负责构建IR，而解释器则利用IR来解释输入。
事实证明，树形结构非常适合用作IR。
树形数据结构的基本概念
树是一种由一个或多个节点组成的数据结构，这些节点按层次结构组织。
树有一个根节点，位于树的顶端。
除了根节点外，所有节点都有唯一的父节点。
下图中标有星号 * 的节点是父 节点，标有2 和7 的节点是-其子 节点，子节点从左到右排列。
没有子节点的节点称为叶子 节点。
有一个或多个子节点且不是根节点的节点称为内部 节点。
子节点也可以是完整的子树 。下图中，+节点的左侧子节点（标有星号）是一个带有自己子节点的完整子树 。
在计算机科学中，我们通常将树形结构倒过来画，根节点在顶部，分支向下延伸。
这是表达式 2 * 7 + 3 的树形结构：
抽象语法树（AST）与解析树 我们将使用的中间表示 称为抽象语法树（AST）。在深入探讨AST之前，我们先简单介绍一下解析树。虽然我们不会在解释器和编译器中使用解析树 ，但它们可以帮助你通过可视化解析器的执行过程来理解解析器是如何解析输入的。我们还会将它们与AST进行对比，说明为什么AST更适合作为中间表示。
那么，什么是解析树？解析树（有时称为具体语法树）是一种根据我们语法定义来表示语言结构的树形结构。它基本上展示了解析器如何识别语言结构，换句话说，它展示了语法的起始符号如何推导出编程语言中的特定字符串。
解析器的调用堆栈实际上隐含了一个解析树，它由解析器在试图识别某个语言结构时自动构建在内存中。
让我们看看表达式 2 * 7 + 3 的解析树：
从上图可以看出：
解析树记录了解析器应用的规则序列，用于识别输入。
解析树的根节点标有语法起始符号。
每个内部节点表示一个非终结符，即它代表一个语法规则的应用，在我们的例子中如 expr、term 或 factor。
每个叶子节点代表一个token。
正如我之前提到的，我们不会手动构建解析树并将其用于解释器，但解析树可以帮助你通过可视化解析器的调用顺序来理解解析器如何解释输入。
你可以通过尝试一个名为 genptdot.pyGraphviz 包。然后运行以下命令，你可以打开生成的 parsetree.png 文件，查看你作为命令行参数传递的表达式的解析树：
1 2 $ python genptdot.py "14 + 2 * 3 - 6 / 2" > \ parsetree.dot && dot -Tpng -o parsetree.png parsetree.dot
这是表达式 14 + 2 * 3 - 6 / 2 生成的图像 parsetree.png：
尝试用不同的算术表达式来看看特定表达式的解析树是什么样子。
抽象语法树（AST）的特点 现在，让我们讨论*抽象语法树**（AST）。这是我们将在整个系列中广泛使用的 中间表示（IR）***（IR）。它是我们解释器和未来编译器项目的核心数据结构之一。
让我们通过比较表达式 2 * 7 + 3 的AST和解析树来开始讨论：
从上图可以看出，AST在保持输入本质的同时更加简洁。
AST与解析树的主要区别如下：
AST使用操作符/操作作为根节点和内部节点，并将操作数作为子节点。
AST不使用内部节点来表示语法规则，而解析树则会这么做。
AST不表示语法的每一个细节（这也是它们被称为抽象 的原因）——例如，没有规则节点和括号。
相比于解析树，AST更加紧凑。
那么，什么是抽象语法树？**抽象语法树** (AST) 是一种表示语言结构的抽象语法结构的树形结构，其中每个内部节点和根节点表示一个操作符，而节点的子节点表示该操作符的操作数。
我之前提到过，AST比解析树更紧凑。让我们看看表达式 7 + ((2 + 3)) 的AST和解析树。你可以看到，下面的AST比解析树小得多，但仍然捕捉到了输入的本质。
目前为止，一切顺利，但你如何在AST中编码操作符的优先级呢？为了在AST中编码操作符优先级，即表示“X先于Y发生”，你只需将X放在树中比Y更低的位置。在之前的图片中，你已经看到了这一点。
让我们再看看一些例子。
在下图左侧，你可以看到表达式 2 * 7 + 3 的AST。通过将 7 + 3 放在括号内，我们改变了优先级。你可以看到右侧的AST是表达式 2 * (7 + 3) 的结构：
这是表达式 1 + 2 + 3 + 4 + 5 的AST：
从上面的图中可以看出，优先级较高的操作符最终会在树中位于较低的位置。
实现AST节点类型并修改解析器生成AST 接下来，让我们编写一些代码来实现不同的AST节点类型，并修改我们的解析器以生成由这些节点组成的AST。
首先，我们将创建一个名为 AST 的基础节点类，其他类将从该类继承：
1 2 class AST (object ): pass
虽然这个类本身内容很少，但请记住，AST表示操作符-操作数模型。目前为止，我们有四种操作符和整数操作数：加法、减法、乘法和除法。我们可以为每个操作符创建一个单独的类，如 AddNode、SubNode、MulNode 和 DivNode，但我们将使用一个名为 BinOp 的类来表示所有四种二元操作符（二元操作符是对两个操作数进行操作的操作符）：
1 2 3 4 5 class BinOp (AST ): def __init__ (self, left, op, right ): self.left = left self.token = self.op = op self.right = right
构造函数的参数是 left、op 和 right，其中 left 和 right 分别指向左操作数节点和右操作数节点。op 保存操作符本身的token：对于加法操作符为 Token(PLUS, '+')，对于减法操作符为 Token(MINUS, '-')，等等。
为了在AST中表示整数，我们将定义一个名为 Num 的类，该类保存一个 INTEGER token 及其值：
1 2 3 4 class Num (AST ): def __init__ (self, token ): self.token = token self.value = token.value
所有节点都存储了用于创建该节点的token，这主要是为了方便，将来可能会用到。
回想一下表达式 2 * 7 + 3 的AST。我们将在代码中手动创建该表达式的AST：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 >>> from spi import Token, MUL, PLUS, INTEGER, Num, BinOp>>> >>> mul_token = Token(MUL, '*' )>>> plus_token = Token(PLUS, '+' )>>> mul_node = BinOp(... left=Num(Token(INTEGER, 2 )),... op=mul_token,... right=Num(Token(INTEGER, 7 ))... )>>> add_node = BinOp(... left=mul_node,... op=plus_token,... right=Num(Token(INTEGER, 3 ))... )
这是我们新定义的节点类生成的AST的样子。下图也展示了上述手动构建过程：
修改后的解析器代码 以下是我们修改后的解析器代码，它在识别输入（算术表达式）后构建并返回一个AST：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 class AST (object ): pass class BinOp (AST ): def __init__ (self, left, op, right ): self.left = left self.token = self.op = op self.right = right class Num (AST ): def __init__ (self, token ): self.token = token self.value = token.value class Parser (object ): def __init__ (self, lexer ): self.lexer = lexer self.current_token = self.lexer.get_next_token() def error (self ): raise Exception('语法错误' ) def eat (self, token_type ): if self.current_token.type == token_type: self.current_token = self.lexer.get_next_token() else : self.error() def factor (self ): """factor : INTEGER | LPAREN expr RPAREN""" token = self.current_token if token.type == INTEGER: self.eat(INTEGER) return Num(token) elif token.type == LPAREN: self.eat(LPAREN) node = self.expr() self.eat(RPAREN) return node def term (self ): """term : factor ((MUL | DIV) factor)*""" node = self.factor() while self.current_token.type in (MUL, DIV): token = self.current_token if token.type == MUL: self.eat(MUL) elif token.type == DIV: self.eat(DIV) node = BinOp(left=node, op=token, right=self.factor()) return node def expr (self ): """ expr : term ((PLUS | MINUS) term)* term : factor ((MUL | DIV) factor)* factor : INTEGER | LPAREN expr RPAREN """ node = self.term() while self.current_token.type in (PLUS, MINUS): token = self.current_token if token.type == PLUS: self.eat(PLUS) elif token.type == MINUS: self.eat(MINUS) node = BinOp(left=node, op=token, right=self.term()) return node def parse (self ): return self.expr()
构建抽象语法树（AST）的过程 让我们来回顾一下构建一些算术表达式的AST的过程。
如果你查看上面的解析器代码，你会发现，它构建AST节点的方式是，每个 BinOp 节点将当前节点变量的值作为左子节点，并将调用 term 或 factor 的结果作为右子节点，因此它实际上是将节点向左推，表达式 1 + 2 + 3 + 4 + 5 的树结构就是一个很好的例子。下面是解析器逐步构建 1 + 2 + 3 + 4 + 5 这个表达式的AST的可视化表示：
为了帮助你更好地理解不同算术表达式的AST，我编写了一个小工具，它将算术表达式作为第一个参数，并生成一个DOT文件，然后通过dot工具处理该文件，实际上为你绘制出一个AST（dot是Graphviz 包的一部分，你需要安装该包才能运行dot命令）。以下是生成表达式 7 + 3 * (10 / (12 / (3 + 1) - 1)) 的AST图像的命令：
1 2 $ python genastdot.py "7 + 3 * (10 / (12 / (3 + 1) - 1))" > \ ast.dot && dot -Tpng -o ast.png ast.dot
genastdot.py
下面是表达式 2 * 7 + 3 的AST：
后序遍历AST以解释表达式 如何遍历树来正确地求值由树表示的表达式？我们使用后序遍历 ，它是一种深度优先遍历的特例。
后序遍历从根节点开始，递归地从左到右访问每个节点的子节点。后序遍历会尽可能快地访问离根节点最远的节点。
以下是后序遍历的伪代码，其中 <<postorder actions>> 是一个占位符，用于表示对 BinOp 节点的加、减、乘、除等操作，或者对于 Num 节点的简单操作，例如返回整数值。
我们将在解释器中使用后序遍历的原因是：首先，我们需要先计算树中较低位置的内部节点，因为它们代表优先级更高的操作符；其次，我们需要先计算操作数，然后再对这些操作数应用操作符。在下图中，你可以看到，通过后序遍历，我们首先计算表达式 2 * 7，然后才计算 14 + 3，这给出了正确的结果17。
为了完整起见，我提一下深度优先遍历有三种类型：前序遍历 、中序遍历 和后序遍历 。遍历方法的名称取决于你在访问代码中放置操作的位置。
有时你可能需要在所有这些点（前序、中序和后序）执行某些操作。你将在本篇文章的源代码库中看到一些这样的例子。
实现解释器以访问和解释AST 现在，让我们编写一些代码来访问和解释由解析器构建的抽象语法树。
这是实现访问者模式 的源代码：
1 2 3 4 5 6 7 8 class NodeVisitor (object ): def visit (self, node ): method_name = 'visit_' + type (node).__name__ visitor = getattr (self, method_name, self.generic_visit) return visitor(node) def generic_visit (self, node ): raise Exception('没有 visit_{} 方法' .format (type (node).__name__))
这是我们继承自 NodeVisitor 类的 Interpreter 类的源代码，它实现了形式为 visit_NodeType 的不同方法，其中 NodeType 被替换为节点的类名，如 BinOp、Num 等：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Interpreter (NodeVisitor ): def __init__ (self, parser ): self.parser = parser def visit_BinOp (self, node ): if node.op.type == PLUS: return self.visit(node.left) + self.visit(node.right) elif node.op.type == MINUS: return self.visit(node.left) - self.visit(node.right) elif node.op.type == MUL: return self.visit(node.left) * self.visit(node.right) elif node.op.type == DIV: return self.visit(node.left) / self.visit(node.right) def visit_Num (self, node ): return node.value
这里有两点值得一提：首先，访问者代码与AST节点本身是解耦的。你可以看到，BinOp 和 Num这两个AST节点类中没有提供任何用于操作存储在这些节点中的数据的代码。这些逻辑封装在实现 NodeVisitor 类的 Interpreter 类中。
其次，在 NodeVisitor 的 visit 方法中，
1 2 3 4 5 6 7 8 def visit (node ): node_type = type (node).__name__ if node_type == 'BinOp' : return self.visit_BinOp(node) elif node_type == 'Num' : return self.visit_Num(node) elif ...
或者
1 2 3 4 5 6 def visit (node ): if isinstance (node, BinOp): return self.visit_BinOp(node) elif isinstance (node, Num): return self.visit_Num(node) elif ...
访问方法是非常通用的，并根据传递给它的节点类型分派调用到适当的方法。正如我之前提到的，我们的解释器继承自 NodeVisitor 类，并实现了必要的方法。所以如果传递给 visit 方法的节点类型是 BinOp，那么 visit 方法将调用 visit_BinOp 方法；如果节点类型是 Num，那么 visit 方法将调用 visit_Num 方法，依此类推。
花些时间学习这种方法（标准Python模块 ast 使用相同的机制来遍历节点），因为我们将在未来的解释器中扩展许多新的 visit_NodeType 方法。
generic_visit 方法是一个备用方法，它会引发异常，指示遇到了实现类没有相应 visit_NodeType 方法的节点。
现在，让我们手动构建表达式 2 * 7 + 3 的AST，并将其传递给我们的解释器，看看 visit 方法在求值该表达式时的执行情况。你可以在Python shell中这样做：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 >>> from spi import Token, MUL, PLUS, INTEGER, Num, BinOp>>> >>> mul_token = Token(MUL, '*' )>>> plus_token = Token(PLUS, '+' )>>> mul_node = BinOp(... left=Num(Token(INTEGER, 2 )),... op=mul_token,... right=Num(Token(INTEGER, 7 ))... )>>> add_node = BinOp(... left=mul_node,... op=plus_token,... right=Num(Token(INTEGER, 3 ))... )>>> from spi import Interpreter>>> inter = Interpreter(None )>>> inter.visit(add_node)17
正如你所看到的，我将表达式树的根节点传递给了 visit 方法，这触发了对树的遍历，通过调用 Interpreter 类的正确方法（visit_BinOp 和 visit_Num），并生成了结果。
完整的解释器代码 以下是我们新解释器的完整代码，供你参考：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 """ SPI - Simple Pascal Interpreter """ INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF = ( 'INTEGER' , 'PLUS' , 'MINUS' , 'MUL' , 'DIV' , '(' , ')' , 'EOF' ) class Token (object ): def __init__ (self, type , value ): self.type = type self.value = value def __str__ (self ): """类实例的字符串表示。 示例: Token(INTEGER, 3) Token(PLUS, '+') Token(MUL, '*') """ return 'Token({type}, {value})' .format ( type =self.type , value=repr (self.value) ) def __repr__ (self ): return self.__str__() class Lexer (object ): def __init__ (self, text ): self.text = text self.pos = 0 self.current_char = self.text[self.pos] def error (self ): raise Exception('无效字符' ) def advance (self ): """前进 `pos` 指针并设置 `current_char` 变量。""" self.pos += 1 if self.pos > len (self.text) - 1 : self.current_char = None else : self.current_char = self.text[self.pos] def skip_whitespace (self ): while self.current_char is not None and self.current_char.isspace(): self.advance() def integer (self ): """返回从输入中提取的多位整数。""" result = '' while self.current_char is not None and self.current_char.isdigit(): result += self.current_char self.advance() return int (result) def get_next_token (self ): """词法分析器（也称为扫描器或标记器） 该方法负责将句子分解为token，每次一个。 """ while self.current_char is not None : if self.current_char.isspace(): self.skip_whitespace() continue if self.current_char.isdigit(): return Token(INTEGER, self.integer()) if self.current_char == '+' : self.advance() return Token(PLUS, '+' ) if self.current_char == '-' : self.advance() return Token(MINUS, '-' ) if self.current_char == '*' : self.advance() return Token(MUL, '*' ) if self.current_char == '/' : self.advance() return Token(DIV, '/' ) if self.current_char == '(' : self.advance() return Token(LPAREN, '(' ) if self.current_char == ')' : self.advance() return Token(RPAREN, ')' ) self.error() return Token(EOF, None ) class AST (object ): pass class BinOp (AST ): def __init__ (self, left, op, right ): self.left = left self.token = self.op = op self.right = right class Num (AST ): def __init__ (self, token ): self.token = token self.value = token.value class Parser (object ): def __init__ (self, lexer ): self.lexer = lexer self.current_token = self.lexer.get_next_token() def error (self ): raise Exception('语法错误' ) def eat (self, token_type ): if self.current_token.type == token_type: self.current_token = self.lexer.get_next_token() else : self.error() def factor (self ): """factor : INTEGER | LPAREN expr RPAREN""" token = self.current_token if token.type == INTEGER: self.eat(INTEGER) return Num(token) elif token.type == LPAREN: self.eat(LPAREN) node = self.expr() self.eat(RPAREN) return node def term (self ): """term : factor ((MUL | DIV) factor)*""" node = self.factor() while self.current_token.type in (MUL, DIV): token = self.current_token if token.type == MUL: self.eat(MUL) elif token.type == DIV: self.eat(DIV) node = BinOp(left=node, op=token, right=self.factor()) return node def expr (self ): """ expr : term ((PLUS | MINUS) term)* term : factor ((MUL | DIV) factor)* factor : INTEGER | LPAREN expr RPAREN """ node = self.term() while self.current_token.type in (PLUS, MINUS): token = self.current_token if token.type == PLUS: self.eat(PLUS) elif token.type == MINUS: self.eat(MINUS) node = BinOp(left=node, op=token, right=self.term()) return node def parse (self ): return self.expr() class NodeVisitor (object ): def visit (self, node ): method_name = 'visit_' + type (node).__name__ visitor = getattr (self, method_name, self.generic_visit) return visitor(node) def generic_visit (self, node ): raise Exception('没有 visit_{} 方法' .format (type (node).__name__)) class Interpreter (NodeVisitor ): def __init__ (self, parser ): self.parser = parser def visit_BinOp (self, node ): if node.op.type == PLUS: return self.visit(node.left) + self.visit(node.right) elif node.op.type == MINUS: return self.visit(node.left) - self.visit(node.right) elif node.op.type == MUL: return self.visit(node.left) * self.visit(node.right) elif node.op.type == DIV: return self.visit(node.left) / self.visit(node.right) def visit_Num (self, node ): return node.value def interpret (self ): tree = self.parser.parse() return self.visit(tree) def main (): while True : try : try : text = raw_input('spi> ' ) except NameError: text = input ('spi> ' ) except EOFError: break if not text: continue lexer = Lexer(text) parser = Parser(lexer) interpreter = Interpreter(parser) result = interpreter.interpret() print (result) if __name__ == '__main__' : main()
将上述代码保存为 spi.py 文件或直接从GitHub 下载。试试看，看看你基于树的解释器是否能正确地对算术表达式求值。
这是一个示例会话：
1 2 3 4 5 6 7 $ python spi.py spi> 7 + 3 * (10 / (12 / (3 + 1) - 1)) 22 spi> 7 + 3 * (10 / (12 / (3 + 1) - 1)) / (2 + 3) - 5 - 3 + (8) 10 spi> 7 + (((3 + 2 ))) 12
总结 今天你学到了关于解析树、AST、如何构建AST以及如何遍历它们来解释由这些AST表示的输入。你还修改了解析器和解释器，并将它们分开。词法分析器、解析器和解释器之间的当前接口现在看起来如下：
你可以理解为：“解析器从词法分析器获取token，然后返回生成的AST供解释器遍历并解释输入。”
今天的内容到此为止，但在结束之前，我想简要谈谈递归下降解析器，主要是给出它们的定义，因为我上次承诺要详细谈论它们。所以，这里是：递归下降解析器是一种自顶向下的解析器，它使用一组递归过程来处理输入。自顶向下反映了解析器从解析树的顶层节点开始，然后逐渐构建较低的节点。
练习 现在是时候做一些练习了 :)
编写一个翻译器（提示：节点访问器），该翻译器将一个算术表达式作为输入，并以后缀表示法（也称为逆波兰表示法，RPN）输出。例如，如果输入的表达式是 (5 + 3) * 12 / 3，则输出应为 5 3 + 12 * 3 /。答案在这里 ，但请先尝试自己解决。
编写一个翻译器（节点访问器），该翻译器将一个算术表达式作为输入，并以LISP风格的表示法输出，即 2 + 3 将变为 (+ 2 3)，而 (2 + 3 * 5) 将变为 (+ 2 (* 3 5))。你可以在这里 找到答案，但还是建议先自己尝试解决。
在下一篇文章中，我们将为不断扩展的Pascal解释器添加赋值和一元操作符。在那之前，祝你玩得开心，我们下次再见。
P.S. 我还提供了该解释器的Rust实现，你可以在GitHub 上找到。这是我学习Rust 的一种方式，所以请记住，代码可能还不够“规范”。欢迎对如何改进代码提出意见和建议。
以下是我推荐的几本书，它们将帮助你学习解释器和编译器：
