Let's Build A Simple Interpreter 学习笔记(Part 10 ~ Part 15)

Tag: interpreter 学习笔记 Posted on 2020-03-16 11:40:26 Edited on 2020-04-12 19:14:07 Views: 16

Part 10

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

Lexer 部分

  1. 添加新的 Token 类型。

    VAR           = 'VAR'
    COLON         = 'COLON'
    COMMA         = 'COMMA'
  2. 更新保留字列表。

    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'),
    }
  3. 为添加的新的 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
  4. 更新 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 部分

  1. 为 AST 添加新的节点种类。

    class Program(AST):
     def __init__(self, name, block):
         self.name = name
         self.block = block
  2. 为新添加的产生式构造其相应的函数。

    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
  3. 更新发生了更改的产生式的相应的参数。

    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 部分

  1. 为新添加的节点构造其 visit 函数。
    def visit_Program(self, node):
     self.visit(node.block)
  2. 更新已有的 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

错误处理。

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