Let's Build A Simple Interpreter 学习笔记（Part 7 ~ Part8）
https://ruslanspivak.com/lsbasi-part8/
https://github.com/rspivak/lsbasi
Part 7
该部分主要是讲述将语法分析的输出变为抽象语法树（AST）。 具体的实现方法：
首先创建建一个树节点类：
class BinOp(AST):
def __init__(self, left, op, right):
self.left = left
self.token = self.op = op
self.right = right
其中 left 和 right 分别都指向一个树节点，每个树节点包含一个 token。
那么 expr(), term(), factor() 这些函数要怎么改呢？以下以 expr() 为例。
# 之前的版本
def expr(self):
# expr -> term ((PLUS | MINUS) term)*
result = self.term()
while self.current_token.type in (PLUS, MINUS):
token = self.current_token
if token.type == PLUS:
self.eat(PLUS)
result = result + self.term()
elif token.type == MINUS:
self.eat(MINUS)
result = result - self.term()
return result
# 改后的版本
def expr(self):
# expr -> term ((PLUS | MINUS) term)*
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
构建完 AST 后，我们使用后续遍历进行遍历。后续遍历是指对于树中的每一个节点，我们总是先执行其子节点然后执行父节点。后续遍历的迭代写法是使用一个 stack 协助完成的。
注意遍历的时候，我们需要使用专门为节点定制的 visit 方法。例如对于我们这里的二分操作节点，其访问函数即：
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)
考虑到我们之后会引入更多其他种类的节点，每个节点都要有自己的 visit 函数，因此我们需要使用多态，这就要求我们需要为节点类构建一个公共父类。
但是作者在这里并不是这样实现的，其另外引入了一个 NodeVisitor 类：
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 类中实现的。
Part 8
在这个部分，教程引入了一元操作符，其优先级比二元操作符 +，-，* 以及 \ 要高。
回顾我们之前的文法：
factor -> INTEGER | LPAREN expr RPAREN
term -> factor ((MUL | DIV) factor)*
expr -> term ((PLUS | MINUS) term)
更新后的文法，只有 factor 开头的产生式需要改变：
factor -> (PLUS | MINUS) factor | INTEGER | LPAREN expr RPAREN
我们改了产生式后，其对应的函数也需要进行更新。同时由于一元运算符所需要的树节点与之前的不一样，我们需要新加一个节点类：
class UnaryOp(AST):
def __init__(self, op, expr):
self.token = self.op = op
self.expr = expr
注意到其只有一个子节点。
def factor(self):
"""factor -> (PLUS | MINUS) factor | INTEGER | LPAREN expr RPAREN"""
token = self.current_token
if token.type == PLUS:
self.eat(PLUS)
node = UnaryOp(token, self.factor())
return node # 可以看到此处返回的就是我们新建的树节点
elif token.type == MINUS:
self.eat(MINUS)
node = UnaryOp(token, self.factor())
return node
elif token.type == INTEGER:
self.eat(INTEGER)
return Num(token)
elif token.type == LPAREN:
self.eat(LPAREN)
node = self.expr()
self.eat(RPAREN)
return node