一起来写个简单的解释器（7）
本文是Ruslan Spivak的《一起来写个简单的解释器》系列的第7篇（前6篇）。
如果你对kotlin感兴趣，可以参考我的spi-kotlin。
上一章的末尾提到过，今天我们要学习后续文章的核心数据结构。准备好了吗？Let’s go！
到现在为止，我们的解释器（interpreter）和分析器（parser）的代码都是合在一起的，每当分析器识别出一个语言结构（比如加、减、乘、除）时，解释器就执行相应的运算。这种解释器称为语法制导解释器（syntax-directed interpreter)。这类解释器通常只遍历一遍输入，用来实现那些基本语法比较合适，但是要分析语法更加复杂的Pascal语言的语言结构，就得借助中间语言（Intermediate Representation, IR）的帮助了。分析器负责构造IR，解释器使用IR来解释输入。
IR通常使用树结构来表示。
先来复习一下关于树的知识点：
- 树是一种由一个或多个节点按层次组合而成的数据结构。
- 树的顶层节点称为根。
- 除根节点外的所有节点都有唯一的父节点。
- 下图中的 * 是一个父节点。2 和 7 是它的子节点；子节点从左到右排列。
- 没有子节点的节点称为叶子节点。
- 有一个或多个子节点的非根节点称作内部节点。
- 子节点也可以是一个完整的子树。下图中 + 节点的左孩子 * 就是一个有自己的子孙节点的完整子树。
- 在计算机科学中，树通常是倒着画的，根节点在最上方，枝杈则向下生长。
下图是表达式 2 * 7 + 3 的树形表示：
本系列中使用的IR是抽象语法树（Abstract Syntax Tree, AST）。在深入学习抽象语法树之前，我们要先简要的了解一下分析树。虽然我们的解释器和编译器不会用到分析树，不过借助分析树的帮助，能够让你更好的理解分析器是怎么把输入翻译成抽象语法树的。我们还会比较分析树和抽象语法树各自的特点，看看为什么抽象语法树比分析树更适合表示中间语言。
什么是分析树？分析树（有时也叫具体语法树）是一棵根据语法定义来表示语言的语法结构的树。它展示了分析器是如何识别语言结构的。换句话说，分析树展示了语法的开始符号是怎么扩展成编程语言的具体语句的。
分析器的调用栈就是一个隐式的分析树，在分析器识别特定语言结构时，它会自动在内存里构造出一棵分析树来。
下图是表达式 2 * 7 + 3 的语法树：
可以看到：
- 分析树记录了分析器用来识别输入的规则序列。
- 分析树的根节点是语法的开始符号。
- 每个内部节点表示一个非终结符，也就是表示一个语法规则，比如 expr, term, factor 等。
- 每个叶子节点表示一个token。
我们不会手工构造分析树，也不会把它用在我们的解释器里。不过分析树可以帮助你理解分析器是怎么翻译输入的。
我写了一个叫做genptdot.py的小工具，你可以用它生成表达式的分析树，看看不同的表达式的分析树有什么不同。要使用这个工具你需要先安装Graphviz，然后运行下面的命令，工具会把你写在参数里的表达式生成成一张分析树的图片。 用Windows的同学可能得折腾一下Graphviz…
$ python genptdot.py "14 + 2 * 3 - 6 / 2" > \
parsetree.dot && dot -Tpng -o parsetree.png parsetree.dot
下图是程序生成的 14 + 2 * 3 - 6 / 2 的分析树：
用工具生成几个不同表达式的分析树，看看特定表达式的分析树都长什么样子。
现在我们再来看看抽象语法树(AST)，后续文章里我们会大量使用这种中间语言。它是我们的解释器以及未来的编译器的核心数据结构。
先来看看表达式 2 * 7 + 3 的抽象语法树和分析树有什么不一样：
从上图可以看出，抽象语法树在抓住输入的本质的同时比分析树更小。
抽象语法树和分析树的区别如下：
- 抽象语法树把操作符/操作作为根节点和中间节点，操作数作为它们的子节点。
- 和分析树不同，抽象语法树不把语法规则表示成中间节点。
- 抽象语法树没有把语法的每个细节都表示出来（这也是“抽象”的来历）。比如，抽象语法树里面没有规则节点和括号。
- 对于同样的语言结构来说，抽象语法树比分析树更加紧凑。
什么是抽象语法树？抽象语法树是表示语言的抽象语法结构的一棵树，它的每个中间节点和根节点表示一个操作符，这些节点的子节点表示该操作符的操作数。
之前说过，抽象语法树比分析树更加紧凑。以表达式 7 + ((2 + 3)) 为例，它的抽象语法树比分析树小的多，但仍然保留了输入中的关键信息：
到目前为止还不错，但是在抽象语法树里操作符的优先级怎么表示？在抽象语法树中，要表示操作符的优先级，即“X先于Y发生”，只要把X放在树中比Y低的位置就可以了。之前的图片中的抽象语法树就是这么做的。
再看几个例子。
下面的图片中，左边是表达式 2 * 7 + 3 的抽象语法树。现在我们把 7 + 3 放到括号里来改变优先级，右图就是修改后的表达式 2 * (7 + 3) 的抽象语法树。
下面是表达式 1 + 2 + 3 + 4 + 5 的抽象语法树。
从上面的图片里可以看出，优先级更高的操作符处于抽象语法树中更低的位置。
OK，是时候写点儿代码了。下面我们先实现几个AST节点类型，然后修改分析器，让它生成由这几种节点组成的抽象语法树。
首先，创建抽象语法树节点的基类 AST，然后从它派生出其他类：
class AST(object):
pass
AST类的内容就是这些。AST表示操作符-操作数模型，到目前为止，我们一共有4种操作符，和1种操作数（整型）。操作符有加、减、乘和除。我们可以为每种操作符分别创建一种类型，比如 AddNode, SubNode, MulNode 和 DivNode。不过这样太麻烦了，我们用一种类型BinOp来表示这四种二元操作符（二元操作符是接收两个操作数的操作符）：
class BinOp(AST):
def __init__(self, left, op, right):
self.left = left
self.token = self.op = op
self.right = right
BinOp的构造器接收3个参数，其中left和right分别指向节点的左操作数节点和右操作数节点。op保存操作符自身的token：对于加法操作符就是Token(PLUS, ‘+’)，对减法操作符就是Token(MINUS, ‘-‘)，等等。
要在我们的抽象语法树里表示整型，需要定义一个类Num。Num中保存有INTEGER的token和它的值。
class Num(AST):
def __init__(self, token):
self.token = token
self.value = token.value
聪明的读者可能已经注意到了，每个节点都保存了它的token。这主要是为了以后用起来方便。
再回到表达式 2 * 7 + 3 的例子上来。我们用代码创建它的抽象语法树：
>>> 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对象并返回：
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
# set current token to the first token taken 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:
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节点的方法是，每个BinOp节点将当前变量的值作为它的左子节点，term或factor的调用结果作为它的右子节点。从效果上看，解析器是在把节点往左下方推，表达式 1 + 2 + 3 + 4 + 5 的抽象语法树就是一个很好的例子。下图是分析器构造该语法树的过程：
我写了一个可以可视化不同数学表达式的AST的小工具，它从第一个参数里读取数学表达式，并生成相应的DOT文件，然后用dot工具生成实际的AST图像（dot是Graphviz包的一部分，要运行dot命令你需要先安装Graphviz）。下面是生成表达式 7 + 3 * (10 / (12 / (3 + 1) - 1)) 的AST图像的命令：
$ python genastdot.py "7 + 3 * (10 / (12 / (3 + 1) - 1))" > \
ast.dot && dot -Tpng -o ast.png ast.dot
写几个数学表达式，手工画出它的抽象语法树，然后跟genastdot.py工具生成的抽象语法树对比验证一下。这能帮你更好的理解分析器是怎样构建不同的数学表达式的抽象语法树的。
Ok，这是表达式 2 * 7 + 3 的抽象语法树：
你会如何遍历这棵树，来计算它表示的表达式的值？答案是后序遍历——深度优先遍历的一种特殊形式。后序遍历从根节点开始，从左到右递归地遍历每个节点的子节点。后序遍历尽可能快地遍历离根节点最远的节点。
下面是后续遍历的伪代码，其中«postorder actions»是操作占位符，对于BinOp节点就是加减乘除，对于Num节点就是简单地返回它的整型值。
使用后序遍历的原因是：首先，我们应该先计算树中更靠下的中间节点，因为它们代表优先级更高的操作符；其次，在执行一个操作符的操作前，我们得先计算它的操作数的值。从下图可以看到，根据后序遍历，我们先计算表达式 2 * 7 的值，然后才能计算 14 + 3，最终得到正确结果 17：
完整地说，一共有3种深度优先遍历：前序遍历，中序遍历，后序遍历。它们的名字来源于遍历代码中操作的位置：
有时候你在3个位置（前序，中序，后序）都需要执行操作。这篇文章的repository里就有这样的例子。
OK，现在让我们用代码遍历并翻译分析器生成的抽象语法树吧。 Here is the source code that implements the Visitor pattern: 下面是访问者模式的实现代码：
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('No visit_{} method'.format(type(node).__name__))
下面是我们的翻译器类的实现代码。它继承了NodeVisitor类，实现了形如visit_NodeType的访问方法，其中NodeType是BinOp、Num等节点类的名字：
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语句来实现：
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 ...
# ...
或者这样：
def visit(node):
if isinstance(node, BinOp):
return self.visit_BinOp(node)
elif isinstance(node, Num):
return self.visit_Num(node)
elif ...
NodeVisitor的访问方法很通用地根据参数的类型将调用分发到了相应的方法。前面提到，为了确保这一点，我们的翻译器继承了NodeVisitor类，并实现了必要的方法。如果传给visit方法的参数是BinOp类型，visit方法会把调用分发到visit_BinOp方法，如果节点了类型是Num，visit方法就会把调用分发到visit_Num方法，等等。
花点时间研究一下这种方法（Python的标准模块ast也是用了同样的机制进行节点遍历），为了我们会给解释器添加许多新的visit_NodeType方法。
generic_visit是一个fallback，它抛出一个异常，表明翻译器遇到了一个还没有实现相应的visit_NodeType方法的节点。
现在，我们手动构造一个表达式 2 * 7 + 3 的AST对象，把它传给解释器，看看visit方法能不能得到表达式的正确结果。在Python shell里执行下面的代码：
>>> 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方法，visit方法通过把调用分发给Interpreter类中正确的方法（visit_BinOp和visit_Num）触发遍历并生成计算结果。
OK，下面是我们的新翻译器的完整代码：
""" 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(object):
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 'Token({type}, {value})'.format(
type=self.type,
value=repr(self.value)
)
def __repr__(self):
return self.__str__()
class Lexer(object):
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) - 1:
self.current_char = None # Indicates end of input
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):
"""Return a (multidigit) integer consumed from the input."""
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):
"""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
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)
###############################################################################
# #
# PARSER #
# #
###############################################################################
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
# set current token to the first token taken 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:
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()
###############################################################################
# #
# INTERPRETER #
# #
###############################################################################
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('No visit_{} 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:
try:
text = raw_input('spi> ')
except NameError: # Python3
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下载。运行试试，看看基于树的新翻译器能不能正确地计算出数学表达式的结果。
下面是一些示例测试：
$ 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
今天你学到了分析树、抽象语法树，学到了怎样构造和遍历抽象语法树，怎样翻译抽象语法树表示的输入。你还修改并分离了分析器和翻译器。现在分词器、分析器和翻译器之间的接口是这样的：
这张图可以读作“分析器从分词器中得到token，将生成的AST返回给翻译器，翻译器使用AST遍历并翻译输入”。
今天的内容就到这里了。不过在合上书本之前，我还想再说一说递归下降分析器，给它下一个准确的定义，因为我在上一章里说过我会更详细的介绍它。递归下降分析器是一种自上而下的分析器，它使用一系列的递归过程处理输入。自上而下说明分析器从从根节点开始构建分析树，然后逐步构造更低层的节点。
然后就是练习时间了 :)
- 编写一个翻译器（提示：node visitor），输入一个数学表达式，并以后缀表达式（也就是逆波兰表达式，RPN）的形式输出它。例如，如果翻译器的输入是 (5 + 3) * 12 / 3，那么输出应该是 5 3 + 12 * 3 /。答案在这里，不过一点先自己尝试解决再看答案。
- 编写一个翻译器（node visitor），输入一个数学表达式，并以LISP风格输出它，也就是 2 + 3 应该变成 (+ 2 3)，(2 + 3 * 5) 应该变成(+ 2 (* 3 5))。答案可以在这里找到，不过还是那句话，看答案之前先自己试着解决一下。
下篇文章里，我们会给我们成长中的Pascal解释器增加赋值和一元运算。最后，祝你身体健康，再见。
P.S. 我还提供了一个翻译器的Rust实现，你可以在GitHub上找到它。我写这个版本是为了学习Rust，所以代码里可能会有一些不那么“理想”的地方。欢迎提出评论和建议，来帮助改善这些代码。
译者的kotlin版本也是为了同样的目的写的，欢迎大家批评指正
下面是我推荐的一些书籍列表，它们对你学习解释器和编译器有帮助：
- Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages (Pragmatic Programmers)
- Writing Compilers and Interpreters: A Software Engineering Approach
- Modern Compiler Implementation in Java
- Modern Compiler Design
- Compilers: Principles, Techniques, and Tools (2nd Edition)
顺便，我正在写一本叫做“Let’s Build A Web Server: First Steps”的书，主要内容是关于怎么从零开始编写一个简单的web服务器。想要先睹为快的话可以点击这里，这里，和这里。想知道这本书的最近更新和出版日期的话，可以到邮件列表里询问。 ⤧ Next post 一起来写个简单的解释器（8）