[译]Let’s Build A Simple Interpreter. Part 7.

Posted on | Comments:

原文地址：Let’s Build A Simple Interpreter. Part 7.

像我上次承诺的那样，今天我会讨论一个本系列余下文章中都会用到的重要数据结构，系好 安全带让我们出发。

直到现在，我们都把 interpreter 的代码和 parser 的代码混在一起，且 interpreter 在 parser 识别出一个如加减乘除之类的语言结构之后会立刻对它进行求值。这种 interpreter 被称为 语法导向解释器 (syntax-directed interpreter)。他们通常在输 入上做一个 pass 且只适合基础的语言应用。为了分析更复杂的编程语言 Pascal 的结构， 我们需要建立一个 中间表示 (intermediate representation, IR)。我们的 parser 会 负责构建 IR 而 interpreter 会用来解释由 IR 所代表的输入。

事实证明树是一个表示 IR 非常合适的数据结构。

Figure 1: realtree

让我们快速讨论一下术语树。

  • 树是一个包含一个或多个结点组成的层次数据结构。
  • 树有一个根结点，就是顶部结点。
  • 除根结点外的所有结点有唯一一个父结点。
  • 下图中标签为*的是一个父结点。标签为 2 和 7 的是它的子结点；子结点从左到右排序。
  • 没有子结点的结点称为叶子结点。
  • 有一个或多个子结点的非根结点被称为中间结点。
  • 子结点也可以是完全子树。下图中结点＋的左子树（标签为*）就是一个有自己子结点的 完全子树。
  • 在计算机科学中我们把树倒过来画，根结点在最上边，分枝向下生长。

下面是表达式 2 * 7 + 3 的带有解释的树形表示：

Figure 2: tree terminology

本系列中我们会用到的 IR 被称为 抽象语法树 (abstract-syntax tree, AST)。但在深 入了解 AST 之前让我们简单聊聊 解析树 (parse tree)。尽管我们不会在解释器和编译 器中用到解析树，但它会通过可视化 parser 执行轨迹的方法，加深你对 parser 如何解释 输入的理解。我们也会将它和 AST 做比较，来表明为什么 AST 比解析树更适合用来做 IR。

那么，什么是解析树呢？解析树（有时叫做 具体语法树 ）是一个根据我们的语法定义来 表示一门语言的句法结构的树形结构。它基本上展示了你的 parser 如何识别语言结构或者， 换句话说，它展示了你语法的开始符号怎么派生出该编程语言中一个特定的字符串的。

parser 的调用栈隐式地代表了一个解析树，且它在谋略识别一个特定的语言结构时被自动 地在内在中构建出来。

让我们看一眼表达式 2 * 7 + 3 的解析树：

Figure 3: parsetree01

在上面的图片中可以看到：

  • 解析树记录了 parser 用来识别输入的一系列规则。
  • 解析树的根结点的标签是语法的开始符号。
  • 每个中间结点表示一个非终结符，代表应用了一条语法规则，像我们的情况里的 expr, term 和 factor.
  • 每个叶子结点代表了一个 token.

如我前面所说，我们不会手动构建解析树且在我们的解释器中用到它，但解析树可以通过可视化 调用过程帮助我们理解 parser 怎么解释输入。

你可以使用一个名为 genptdot.py 的小应用（我很快写完用来帮助你的），来查看不同的 算术表达式看起来什么样。要使用这个应用你首先需要安装 Graphviz 包，然后运行下面的 命令，你可以打开生成的图片文件 parsetree.png 查看你从命令行传入的表达式的解析树： 

1
$ python genptdot.py "14 + 2 * 3 - 6 / 2" > \
  parsetree.dot && dot -Tpng -o parsetree.png parsetree.dot

下面是由表达式 14 + 2 * 3 - 6 / 2 生成的图片 parsetree.png:

Figure 4: genptdot01

传入不同的算术表达式试用一下该程序，看看那个表达式对应的解析树是什么样的。

现在我们来聊聊抽象语法树(AST)。它是在余下的文章中会大量用到的中间表示(IR)。它是 我们的解释器和未来编译器项目的中心数据结构。

让我们以把表达式 2 * 7 + 3 的 AST 和解析树放在一起看来开始我们的讨论：

Figure 5: ast01

从上面的图片中可以看出，AST 抓住了输入的精髓且更小。

AST 和解析树最主要的区别有：

  • AST 使用操作/操作符作为根结点，操作数作为它们的子结点。
  • 不像解析树，AST 不使用中间结点来表示语法规则。
  • AST 并不把真实句法中的所有结节都表示出来（这就是为什么它是抽象的）──例如，没有 规则结点和括号。
  • 对于相同的语言结构来说，AST 相比于解析树更紧凑。

那么，什么是抽象语法树？抽象语法树(AST)是表示一个语言结构的抽象句法结构的树形表 示，它的中间结点和根结点代表了一个操作符，子结点代表了该操作符的操作数。

我已经提到过 AST 比解析树更紧凑。让我们看一眼表达式 7 + ((2 + 3)) 的 AST 和解析 树。可以看到下面的 AST 比解析树要小很多，但仍然保留了输入的精髓：

Figure 6: ast02

到现在为止还不错，但你怎么把操作符优先级编码进 AST 呢？为了把操作符优先级编码进 AST，即，为了表示“X 在 Y 之前发生”你只需要在树中把 X 放在低于 Y 的位置。你在前面 的图片中已经见过到了。

让我们再多看一些例子。

在下面的图片中，左边是表达式 2 * 7 + 3 的 AST。让我们用括号把 7 + 3 围起来以改变 它的优先级。在右边是修改后的表达式 2 * (7 + 3) 的 AST：

Figure 7: astprecedence01

下面是表达式 1 + 2 + 3 + 4 + 5 的 AST：

Figure 8: astprecedence02

从上面的图片中可以看出更高优先级的操作符在树中的位置更低。

好了，让我们写些代码来实现不同的 AST 结点类并修改我们的 parser 来生成包含这些结 点的 AST 树：

首先，我们会新建一个基本结点类叫做 AST，其他类会从它继承： 

1
2
class AST():
    pass

没有太多代码。回忆一下 AST 表示了操作符-操作数模型。到现在为止，我们有 4 个操作 符和整型操作数。操作符有加减乘除。我们原本可以新建单独的类来表示每个操作符如 AddNode, SubNode, MulNode 和 DivNode，但相反我们只会新建一个 BinOp 类来表示所有 4 个二元操作符（二元操作符就是作用在两个操作数的操作符）： 

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 和该 token 的值： 

1
2
3
4
class Num(AST):
    def __init__(self, token):
	self.token = token
	self.value = token.value

和你注意到的一样，所有的结点保存了 token 以前则是创建结点(all nodes store the token used to create the node)。这主要是为了方便，将来会派上用场。

回忆一下表达式 2 * 7 + 3 的 AST。我们会在代码中手工创建该表达式： 

>>> 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 的样子。下面的图片也遵循了上面手工创建的过程：

Figure 9: astimpl01

下面是我们修改过的 parser 代码，在识别输入（算术表达式）时建立和返回一个 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
class AST():
    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():
    def __init__(self, lexer):
	self.lexer = lexer
	# set current token to the first token from the input
	self.current_token = self.lexer.get_next_token()

    def error(self):
	raise Exception('Invalid syntax')

    def eat(self, token_type):
	# compare the current token type with the passed token
	# type and if they match then "eat" the current token
	# and assign the next token to the self.current_token,
	# otherwise raise an exception.
	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:
	    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 的构建过程。

如果你看了上面的 parser 代码，可以看到它建立一个 AST 中的结点的时，把变量 node 的当前值做为 BinOp 结点的左子结点，把对 term 或 factor 调用的返回结果做为它 的右子结点，这实际上就是把结点推向左边，下面表达式 1 +2 + 3 + 4 + 5 的树结构就是 这种情况的一个好例子。下面是 parser 如何一步步地构建表达式 1 + 2 + 3 + 4 + 5 的 AST 的图形表示：

Figure 10: astimpl02

为了帮助你将不同的算术表达式的 AST 可视化，我写了一个小程序，它接收一个算术表达 式作为第一个参数并生成一个 DOT 文件，该文件随后被程序 dot 处理并真的为你画一个 AST（dot 是 Graphviz 包的一部分，你需要安装它才能运行 dot 命令）。下面的命令可以 为表达式 7 + 3 * (10 / (12 / (3 + 1) - 1)) 生成 AST 图片： 

1
$ python genastdot.py "7 + 3 * (10 / (12 / (3 + 1) - 1))" > \
  ast.dot && dot -Tpng -o ast.png ast.dot

Figure 11: genastdot01

值得花一些时间来写一些算术表达式，手工画出 AST，然后使用工具 genastdot.py 生成 AST 图片来验证它们。这会帮助你更好地理解 parser 如何为不同的算术表达式构建 AST。

好了，下面是表达式 2 * 7 + 3 的 AST：

Figure 12: ast walking 01

你怎么遍历这个树并恰当地对它所代表的表达式进行求值呢？你可以使用后序遍历──深度优 先遍历的一个特例──这种方式由根结点开始，递归由左至右访问每个结点的子结点。后序遍 历从根结点开始尽可能快地访问离根结点远的结点(The postorder traversal visits nodes as far away from the root as fast as it can)。

下面是后序遍历的伪代码，其中 <<postorder actions>> 是一些操作的占位符，如 BinOp 结点的加减乘除操作或 Num 结点返回整数的简单操作：

Figure 13: ast visit postorder

1
2
3
4
5
def visit(node):
    # for every child node from left to right
    for child in node.children:
	visit(child)
    <<postorder actions>>

我们在解释器中使用后序遍历的原因是，第一，我们需要对在树中更低的中间结点进行求值， 因为它们代表了优先级更高的操作符，第二，我们在对操作数应用对应操作符之前需要对操 作数进行求值。在下面的图片中，可以看到使用后序遍历时我们会首先对表达式 2*7 进行 求值，而只有在对 14 + 3 求值之后，我们才会得到正确答案 17:

Figure 14: ast walking02

为了完整起见，我会提到有三种深度优先遍历的方式：先序遍历，中序遍历和后序遍历。这 些遍历方式名字的来自于遍历代码中操作的位置：

Figure 15: ast visit generic

1
2
3
4
5
6
def visit(node):
    << preorder actions >>
    left_val = visit(node.left)
    << inorder actions >>
    right_action = visit(node.right)
    << postorder actions >>

有时你可能需要在所有地方（先序，中序和后序）都执行一些操作。你会在本文的源代码仓 库中找到一些例子。

好了，让我们写一些代码来遍历和解释由 parser 建立的抽象语法树，好吗？

下面是实现了访问者模式的源代码： 

1
2
3
4
5
6
7
8
class NodeVisitor():
    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('No visit_{} method'.format(type(node).__name__))

下面是 Interpreter 类的源代码，它继承自 NodeVisitor 类且实现了形式为 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 结点的访问者的代码和 AST 结点 自身解耦了。可以看到没有一个 AST 结点类(BinOp 和 Num)提供了操作存储在这些结点中 数据的代码。该逻辑被封装在了实现 NodeVisitor 的 Interpreter 类中。

第二，相比于在 NodeVisitor 中实现一个包含超长的 if 语句的 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 方法非常通用，能根据传入的结点类型来调度适当的方法。正如我 前面提到的，为了利用这一点，我们的解释器继承了 NodeVisitor 类并实现了必要的方法。 因此如果传递给 visit 方法的结点是 BinOp, visit 方法就会调用 visit_BinOp 方法，如果传递给 visit 方法的结点是 Num, visit 方法就会调用=visitNum= 方 法，等等。

花此时间研究一下这个方法（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
""" SPI - Simple Pascal Interpreter """

###############################################################################
#                                                                             #
#  LEXER                                                                      #
#                                                                             #
###############################################################################

# Token types
#
# EOF (end-of-file) token is used to indicate that
# there is no more input left for lexical analysis
INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF = (
    'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'EOF'
)

class Token():
    def __init__(self, type, value):
	self.type = type
	self.value = value

    def __str__(self):
	"""String representation of the class instance.

	Examples:
	    Token(INTEGER, 3)
	    Token(PLUS, '+')
	    Token(MUL, '*')
	"""
	return f'Token({self.type}, {repr(self.value)})'

    def __repr__(self):
	return self.__str__()

class Lexer():
    def __init__(self, text):
	# client string input, e.g. "4 + 2 * 3 - 6 / 2"
	self.text = text
	# self.pos is an index into self.text
	self.pos = 0
	self.current_char = self.text[self.pos]

    def error(self):
	raise Exception('Invalid character')

    def advance(self):
	"""Advance the `pos` pointer and set the `current_char` variable."""
	self.pos += 1
	if self.pos < len(self.text):
	    self.current_char = self.text[self.pos]
	else:
	    self.current_char = None  # Indicates end of input

    def skip_whitespace(self):
	while self.current_char is not None and self.current_char.isspace():
	    self.advance()

    def integer(self):
	"""Return a (multidigit) integer consumed from the input."""
	value = ''
	while self.current_char is not None and self.current_char.isdigit():
	    value += self.current_char
	    self.advance()
	return int(value)

    def get_next_token(self):
	"""Lexical analyzer (also known as scanner or tokenizer)

	This method is responsible for breaking a sentence
	apart into tokens. One token at a time.
	"""
	while self.current_char is not None:
	    if self.current_char.isspace():
		self.skip_whitespace()
		continue
	    elif self.current_char.isdigit():
		return Token(INTEGER, self.integer())
	    elif self.current_char == '+':
		self.advance()
		return Token(PLUS, '+')
	    elif self.current_char == '-':
		self.advance()
		return Token(MINUS, '-')
	    elif self.current_char == '*':
		self.advance()
		return Token(MUL, '*')
	    elif self.current_char == '/':
		self.advance()
		return Token(DIV, '/')
	    elif self.current_char == '(':
		self.advance()
		return Token(LPAREN, '(')
	    elif self.current_char == ')':
		self.advance()
		return Token(RPAREN, ')')
	    else:
		self.error()
	return Token(EOF, None)

###############################################################################
#                                                                             #
#  PARSER                                                                     #
#                                                                             #
###############################################################################

class AST():
    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():
    def __init__(self, lexer):
	self.lexer = lexer
	# set current token to the first token taken from the input
	self.current_token = lexer.get_next_token()

    def error(self):
	raise Exception('Invalid syntax')

    def eat(self, token_type):
	# compare the current token type with the passed token
	# type and if they match then "eat" the current token
	# and assign the next token to the self.current_token,
	# otherwise raise an exception.
	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
	self.error()

    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()

###############################################################################
#                                                                             #
#  INTERPRETER                                                                #
#                                                                             #
###############################################################################

class NodeVisitor():
    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):
	raise Exception('No visitor_{} method'.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:
	    text = input('spi> ')
	except EOFError:
	    print()
	    break

	if len(text.strip()):
	    parser = Parser(Lexer(text))
	    interpreter = Interpreter(parser)
	    result = interpreter.interpret()
	    print(result)

if __name__ == '__main__':
    main()

将以上代码保存到名为 spi.py 的文件中，或者直接从 GitHub 下载。自己试一试，确认 你的新的基于树的解释器可以正确地对算术表达式进行求值。

下面是某次运行过程： 

$ 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 并解释执行。你 还修改了 parser 和 interpreter 并将这两部分解耦了。现在 lexer, parser 和 interpreter 之间的接口看起来像这样：

Figure 16: pipeline

你可以把它读作“parser 从 lexer 中 得到 token 然后返回生成的 AST 给 interpreter 进行遍历并解释执行所给输入”。

这就是今天的所有内容，但在总结之前我还想简单地聊一聊递归下降 parser，即是仅仅给 出它的定义，因为我上次承诺会多说一些它的细节。定义就是：一个 递归下降parser 就 是一个自顶向下的 parser，它使用一组递归过程来处理输入。自顶向下反映了 parser 从 构建解析树的顶部结点开始逐渐构建更低的结点这一事实。

现在是练习时间：）

Figure 17: exercise

  • 写一个翻译器（提示：node visitor），它接收一个算术表达式作为输入并打印出它的后 缀形式，即逆波兰式(Reverse Polish Notation, RPN)。例如，如果翻译器接收的输入是 表达式 (5 + 3) * 12 / 3 则输入应该是 5 3 + 12 * 3 / 。答案在这儿，不过要先 自己解决再看啊。
  • 写一个翻译器（node visitor），它接收一个算术表达式作为输入并将它打印为 LISP 风 格的记法，即 2 + 3 变成 (+ 2 3) 及 (2 + 3 * 5) 变成 (+ 2 (* 3 5)) 。你 可以在这儿打到答案，但在查看之前还是要先尝试自己解决。

下一篇文章中，我会向我们不断成长的 Pascal 解释器添加赋值和一元操作符。在那之前， 玩得开心，再见。

附：我还提供了一个解释器的 Rust 实现，你可以在 GitHub 打到它。这是我学习 Rust 的 一种方式，所以记得这些代码可能还不符合“惯用法”。随时欢迎提出如何使该代码更好的意 见和建议。

下面是我推荐的帮助你学习解释器和编译器的一些书：

  1. Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages (Pragmatic Programmers)
  2. Writing Compilers and Interpreters: A Software Engineering Approach
  3. Modern Compiler Implementation in Java
  4. Modern Compiler Design
  5. Compilers: Principles, Techniques, and Tools (2nd Edition)

顺便说一下，我还在写一本书“et’s Build A Web Server: First Steps”，解释了怎么从头 写一个基本的 Web 服务器。你可以从这里， 这里 和 这里 来感受一下这本书。

本系列的所有文章：

Last Updated 2018-05-26 Sat 14:12.
Render by hexo-renderer-org with Emacs 25.2.2 (Org mode 9.1.13)
0%