Let's Build A Simple Interpreter 学习笔记（Part 9）

概述

在此之前我们所构建的仅仅是一个计算器，在这部分我们要做出重大改进：

1. 加入 BEGIN END 语句。
2. 加入 赋值运算符 :=。
3. 引入了符号表。

文法的改变

改变后的文法：

program -> compound_statement DOT
compound_statement -> BEGIN statement_list END
statement_list -> statement | statement SEMI statement_list
statement -> compound_statement | assignment_statement | empty
assignment_statement -> variable ASSIGN expr
empty -> ε
expr -> term ((PLUS | MINUS) term)*
term -> factor ((MUL | DIV) factor)*
factor -> PLUS factor | MINUS factor | INTEGER | LPAREN expr RPAREN | variable
variable -> ID

开始符号为 program，Pascal 程序需要以 DOT 结尾。

文法设计要注意避免二义性，同时要消除可能的左递归。左递归消除的通用方法：对于 A -> Aα|β，将其变为 A -> βA', A' -> αA' | ε。 消除文法中的左递归的算法：

提醒：文法中全大写的项都是终结符号。

程序实现上发生的改变

peek() 工具函数的加入

由于诸如 ==，=> 等符号的出现，仅凭当前字符有时我们无法判断具体的 Token 种类，这个时候我们就需要得知下一个字符但又不能将其消耗，也即我们不能使用 advance()。 这里我们引入了新的工具函数 peek()：

def peek(self):
    peek_pos = self.pos + 1
    if peek_pos > len(self.text) - 1:
        return None
    else:
        return self.text[peek_pos]

为保留字和标识符定义对应的 Token

首先要扩增原来的 Token 类型：

(INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, ID, ASSIGN,
 BEGIN, END, SEMI, DOT, EOF) = (
    'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'ID', 'ASSIGN',
    'BEGIN', 'END', 'SEMI', 'DOT', 'EOF'
)

其次要有用于构建保留字以及标识符类型的 Token 的工具函数：

def _id(self):  # 类别之前用于构建数字的 integer() 工具函数
    """Handle identifiers and reserved keywords"""
    result = ''
    while self.current_char is not None and self.current_char.isalnum():
        result += self.current_char
        self.advance()

    token = RESERVED_KEYWORDS.get(result, Token(ID, result))
    return token

相应的，函数 get_next_token()也需要进行更新：

def get_next_token(self):
    while self.current_char is not None:
        ...
        if self.current_char.isalpha():
            return self._id()

        if self.current_char == ':' and self.peek() == '=':
            self.advance()
            self.advance()
            return Token(ASSIGN, ':=')

        if self.current_char == ';':
            self.advance()
            return Token(SEMI, ';')

        if self.current_char == '.':
            self.advance()
            return Token(DOT, '.')
        ...

上述更新针对词法分析器，以下的更新针对语法分析器。

为 AST 添加新的节点类型以及相应的访问函数

其相应的访问函数：

def visit_Compound(self, node):
    for child in node.children:
        self.visit(child)

def visit_Assign(self, node):
    var_name = node.left.value
    self.GLOBAL_SCOPE[var_name] = self.visit(node.right)

def visit_Var(self, node):
    var_name = node.value
    val = self.GLOBAL_SCOPE.get(var_name)
    if val is None:
        raise NameError(repr(var_name))
    else:
        return val

def visit_NoOp(self, node):
    pass

在何处调用这些访问函数呢？

def interpret(self):
    tree = self.parser.parse()
    if tree is None:
        return ''
    return self.visit(tree)

产生式所对应的函数的增添与更新

具体的方式和之前一样，这里仅以 compound_statement 对应的函数为例：

def compound_statement(self):
    """
    compound_statement -> BEGIN statement_list END
    """
    self.eat(BEGIN)
    nodes = self.statement_list()
    self.eat(END)

    root = Compound()  # 构造并最终返回一个 Compound 节点
    for node in nodes:
        root.children.append(node)

    return root

Memory

Memory 用于存储变量的值。 此处作者直接使用了 python 的字典数据结构来实现 Memory。

声明：GLOBAL_SCOPE = {}

赋值：self.GLOBAL_SCOPE[var_name] = self.visit(node.right)

取值：val = self.GLOBAL_SCOPE.get(var_name)

Links: Lets-Build-A-Simple-Interpreter-学习笔记-3

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