JustSong Archive Link About
Projects
Categories
Others

Let's Build A Simple Interpreter 学习笔记(Part 7 ~ Part8)

Tag: interpreter 学习笔记 Posted on 2020-03-14 20:53:08 Edited on 2020-04-12 19:14:00 Views: 144

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

image.png

图片来源:https://ruslanspivak.com/lsbasi-part7/

构建完 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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/