Let's Build A Simple Interpreter 学习笔记（Part 10 ~ Part 15）

    
        标签：
        
            interpreter
        
            学习笔记
        
    发布于：2020-03-16 11:40:26
    编辑于：2022-11-15 12:19:14
    浏览量：31257

Part 10

第十部分主要是加入新的文法，并对词法分析器，语法分析器以及解释器做出相应的更改。在此总结一下添加文法我们要做的事情：

Lexer 部分

添加新的 Token 类型。

VAR           = 'VAR'
COLON         = 'COLON'
COMMA         = 'COMMA'

更新保留字列表。

RESERVED_KEYWORDS = {
    'PROGRAM': Token('PROGRAM', 'PROGRAM'),
    'VAR': Token('VAR', 'VAR'),
    'DIV': Token('INTEGER_DIV', 'DIV'),
    'INTEGER': Token('INTEGER', 'INTEGER'),
    'REAL': Token('REAL', 'REAL'),
    'BEGIN': Token('BEGIN', 'BEGIN'),
    'END': Token('END', 'END'),
}

为添加的新的 Token 类型增添相应的构造函数（如果需要的话）。

def number(self):
    """Return a (multidigit) integer or float consumed from the input."""
    result = ''
    while self.current_char is not None and self.current_char.isdigit():
        result += self.current_char
        self.advance()

    if self.current_char == '.':
        result += self.current_char
        self.advance()

        while (
            self.current_char is not None and
            self.current_char.isdigit()
        ):
            result += self.current_char
            self.advance()

        token = Token('REAL_CONST', float(result))
    else:
        token = Token('INTEGER_CONST', int(result))

    return token

更新 get_next_token() 使其支持新的 Token 类型。

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

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

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

Parser 部分

为 AST 添加新的节点种类。

class Program(AST):
    def __init__(self, name, block):
        self.name = name
        self.block = block

为新添加的产生式构造其相应的函数。

def declarations(self):
    """declarations : VAR (variable_declaration SEMI)+
                    | empty
    """
    declarations = []
    if self.current_token.type == VAR:
        self.eat(VAR)
        while self.current_token.type == ID:
            var_decl = self.variable_declaration()
            declarations.extend(var_decl)
            self.eat(SEMI)

    return declarations

更新发生了更改的产生式的相应的参数。

def term(self):
    """term : factor ((MUL | INTEGER_DIV | FLOAT_DIV) factor)*"""
    node = self.factor()

    while self.current_token.type in (MUL, INTEGER_DIV, FLOAT_DIV):
        token = self.current_token
        if token.type == MUL:
            self.eat(MUL)
        elif token.type == INTEGER_DIV:
            self.eat(INTEGER_DIV)
        elif token.type == FLOAT_DIV:
            self.eat(FLOAT_DIV)
        node = BinOp(left=node, op=token, right=self.factor())
    return node

Interpreter 部分

为新添加的节点构造其 visit 函数。

def visit_Program(self, node):
    self.visit(node.block)

更新已有的 visit 函数当需要时。

# 此处我们添加了浮点除法，由于除法属于二元操作，因此我们需要更新 BinOp 节点对应的 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 == INTEGER_DIV:
        return self.visit(node.left) // self.visit(node.right) 
    elif node.op.type == FLOAT_DIV:
        return float(self.visit(node.left)) / float(self.visit(node.right))

Part 11

本部分引入符号表。符号表用于记录标识符的类型信息，在语义分析阶段识别程序的语义错误。

具体的实现方式为针对 AST 的各个节点构建访问函数，后续遍历 AST，检查程序是否存在类型错误。

Part 12

本部分使我们的解释器支持嵌套的 PROCEDURE 语法。

declarations -> VAR (variable_declaration SEMI)+
                    | (PROCEDURE ID SEMI block SEMI)*
                    | empty

Part 13

本部分介绍了符号表，其用于语义分析阶段发现程序的语法错误。

为什么不在语法分析阶段处理错误呢？将 AST 的构建和错误检查分开有助于简化 Parser 的设计。

符号表存储一下以下信息：符号名称，符号种类（category，例如变量，函数）以及类型（type，例如对于变量，其具体的变量类型；对于函数则是其返回类型）。

Part 14

嵌套的符号表。

Part 15

错误处理。

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