Let's Build A Simple Interpreter 学习笔记(Part 9)

Tag: interpreter 学习笔记 Posted on 2020-03-15 16:38:10 Edited on 2020-04-12 19:13:20 Views: 14

概述

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

  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 添加新的节点类型以及相应的访问函数

节点名称 描述
class Compound(AST) 用于表示 BEGIN END 代码块,考虑到代码块中的表达式的个数不定,因此其存储一个列表
class Assign(AST) 用于记录赋值关系
class Var(AST) 变量节点
class NoOp(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)

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