[译]自己动手编写一个简单的解释器 Part 7
原文：Let’s Build A Simple Interpreter. Part 7.
C++代码：https://github.com/msly/compiler/tree/master/second
应上次之约，今天我将讲一个在以后的章节会经常使用的，重要的数据结构。所以大家系好安全带（做好准备），让我们开始吧。
到目前为止，我们把解释器和解析器的代码混在一起，一旦解析器构建好某种语法结构，比如加法、减法、乘法或除法,解释器就计算该表达式的结果(译者:通过parser来触发interpreter执行).这种解释器被称为语法导向的解释器.他们通常是单一的输入，适用于基本的语言的应用程序。为了分析更复杂的Pascal程序语言结构，我们需要建立一个中间表示(IR)。我们的解析器负责构建IR，解释器将用来解释这个IR输入。
事实证明，树是一个非常合适的数据结构用来表示IR。
让我们来快速了解下树的一些特性：
- 树是由一个或多个节点组成的层次关系的集合。
- 树有一个根节点，就是最顶层的那个。
- 每一个非根节点有且只有一个父节点。
- 下图中标记 * 的节点是父节点，标记2和7的是他的子节点，按左到右的顺序排列。
- 没有子节点的节点被称为叶节点。
- 除了根节点和叶节点，其他节点被称为内部节点。
- 子节点也是一颗完整的子树，在下图中左节点（标记 * 的节点）相对 + 节点就是一颗完整的子树。
- 在计算机科学中，树结构像一颗倒挂着的树，根朝上，树枝是往下生长的。
下面是表达式2 * 7 + 3用树的表示：
我们把这个系列文章中使用的IR（中间表示）叫做抽象语法树（AST）。在我们深入研究AST之前，先简单的谈谈分析树（parse trees）。虽然我们不在解释器和编译器中使用分析树，他可以帮助你了解你的解析器通过可视化的执行轨迹来解析输入。我们也将与AST进行比较，从而明白为什么AST比分析树更适合中间表示。
那么，什么是分析树？分析树（有时也称具体语法树）根据我们的语法定义来构建语言的语法结构。他基本说明了解析器是如何识别语言的，换句话说，他表示了你的语法起始符怎样从编程语言中提取一个特定的字符串。
解析器的调用堆栈隐式的表示了一颗分析树，他在当你的解析器试图去识别一个特定的语言结构时，自动的构建在内存中。
让我们看一下表达式 2 * 7 + 3 的分析树。
在上图中能看到:
- 分析树记录了一系列解析器用于识别输入的规则。
- 分析树的根标记为语法起始符。
- 每个内部节点代表一个非终结符，他在这个例子中，代表了类似exp、term或factor等语法规则应用。
- 每个叶节点代表一个token。
我已经提过，我们不打算手动构建分析树，并用于我们的解释器，但是分析树可以帮助你理解解析器是如何通过可视化解析调用序列来解释输入的。
我很快写了一个小工具genptdot.py，你可以用它来看各种不同的数学表达式的分析树。使用这个工具前，需要安装Graphviz，然后运行下面的命令，打开生成的图片文件parsetree.png，你就能看到你在命令行输入的表达式的分析树。
$ python genptdot.py "14 + 2 * 3 - 6 / 2" > \
parsetree.dot && dot -Tpng -o parsetree.png parsetree.dot
下面是工具生成的表达式 14 + 2 * 3 -6 / 2 的分析树图片。
你可以试试不同的表达式，看看表达式对应的分析树是什么样子的。
现在，我们来谈谈抽象语法树（AST）。他就是我们接下来的系列都使用的中间表示（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，右边修改了优先级，把 7 + 3 放到括号里，表示 2 * (7 + 3)：
下面是表达式 1 + 2 + 3 + 4 + 5 的AST：
从上面的图片可以看到，优先级越高的操作符最终在树中的位置更低。
好吧，让我们写一些代码来实现不同的AST节点类型，并修改我们的解析器来生成这些节点组成的AST树。
首先，我们将创建一个名为AST的基类，其他类将继承他：
class AST(object):
pass
实际上没有太多代码。回想一下，AST表示的是操作符-操作数模式。目前我们有4个操作符和整数型操作数。操作符包括加、减、乘和除。我们可以创建单独的类来分别表示每个操作符，例如AddNode、SubNode、MulNode和DivNode，但是我们这里只使用一个BinOp类来表示所有的4个二元操作符（二元操作符就是一个操作符有两个操作数）。
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的值。
class Num(AST):
def __init__(self, token):
self.token = token
self.value = token.value
你注意到了没有，所有的节点存储了token用来创建节点。这主要是为了方便，他在将来会派上用场。
回想下表达式 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，图片遵循上面的手动创建过程：
下面是我们修改的解析器代码，识别输入（算术表达式）并返回一个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就是一个很好的例子。这里是一个可视化表示解析器如何逐步建立了表达式1 + 2 + 3 + 4 + 5的AST：
为了帮助你看到各种的算术表达式的AST，我写了一个小工具genastdot.py，把算数表达式作为第一个参数，最后会通过dot工具生成一个画着AST的dot文件（dot是Graphviz的一部分，需要安装Graphviz才能运行）。下面是生成AST的一个命令：
$ python genastdot.py "7 + 3 * (10 / (12 / (3 + 1) - 1))" > \
ast.dot && dot -Tpng -o ast.png ast.dot
这是值得你花时间来写一些算术表达式，手动画出他们的AST，然后用工具genastdot.py生成的进行验证，这将帮助你更好的理解解析器是如何构建AST的。
好了，下面是表达式 2 * 7 + 3 的AST:
如何来遍历树从而正确计算树所代表的表达式呢？你可以使用postorder traversal（后序遍历）-深度优先遍历的一个特例，从根节点开始，按从左到右的方式递归的访问子节点。后序遍历访问节点尽可能快的速度远离根节点。
下面是后序遍历的伪代码，<< postorder actions >>代表一个BinOp节点的运算符操作（进行+-*/运算）或一个Num节点的求值操作(返回Num节点的值)：
我们的解释器使用后序遍历的原因，第一，我们需要先计算更低层的节点，因为他们有更高的优先级；第二，我们需要先计算操作数，才能使用操作符计算结果。在下面的图片，你可以看到，后序遍历我们首先计算表达式 2 * 7，然后才计算 14 + 3，得到正确的结果，17：
为了完整起见，我提一下树的三种深度优先遍历：preorder traversal（前序遍历）, inorder traversal（中序遍历）, 和 postorder traversal（后序遍历）。名字的来源于你在遍历代码放actions（具体运算）的位置。
有时你可能需要在上图所示的三个位置都需要执行某些操作。你会看到这样的一些例子在本文的源码库。
好吧，让我们写一些代码来访问和解释由我们的解析器构建的抽象语法树，我们可以吗？
下面是源代码，使用了访问者模式：
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__))
下面是Interpreter类的代码，继承了NodeVisitor类并根据visit_NodeType实现了不同方法，NodeType会被具体的节点类名字代替，如：BinOp，Num等等（见下面的visit_BinOp， visit_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的visit方法中没有像下面这样使用了大量的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类的visit方法是非常通用的，他根据节点的类型把调用转发到合适的方法。我们前面提过，为了使用他，我们的解释器继承了NodeVisitor类并实现了必要的方法。如果传递给visit方法的类型是BinOp，他就会调用visit_BinOp方法；如果传递的类型是Num，他就会调用visit_Num方法，以此类推。
花一些时间学习这一方法（python标准库模块ast使用了相同的机制来访问节点），我们可以在将来用更多新的visit_NodeType方法来扩展我们的解释器。
generic_visit方法是抛出一个异常，表明它遇到一个节点，在实现类有没有相应的visitNodeType方法（No visit{} method）。
现在，我们来手动构建 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方法，他会触发树的遍历，分发调用到Interpreter类中相应的方法，并生成结果。
好了，为了方便，下面给出解释器的完整代码：
""" 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
今天，你学了分析树，AST，如何构建AST，如何遍历表达式AST。你还修改了解析器和解释器的代码，并将他们拆分开了。当前的lexer（词法分析器），parer（解析器），interpreter（解释器）的接口像下面这样：
从上图可以看到，解析器从词法分析器获取token，生成AST作为解释器的输入，解释器遍历和解释AST。
这些就是今天的内容，在结束前我简单的说下recursive-descent parsers（递归下降分析器），这里只给他一个定义，我在后面的系列会详细的来讨论。所以，这里就是他的定义：一个递归下降分析器是一个自顶向下的解析器，使用递归来处理输入。自顶向下表示先构建分析树的顶部节点，然后逐步的构建较低层的节点。
下面是练习时间 :)
在下篇文章，我们将增加赋值和一元操作符正在成长的Pascal解释器。在那之前，好好生活，再见。
P.S. 我给出了一个Rust实现的解释器在GitHub。这是我学习Rust的一种方法，所以你得注意代码可能不那么老到。欢迎提出如何写的更好的评论和建议。