最新消息:欢迎光临 魔力 • Python!大家可以点开导航菜单中的【学习目录】,这个目录类似图书目录,更加方便学习!

一起来写个简单的解释器(10)

Python教程 小楼一夜听春语 1519浏览 0评论

本系列文章参考国外编程高手鲁斯兰的博客文章《Let’s Build A Simple Interpreter》。

还记得在第7部分提到的最终目标吗?

实现一个Pascal编程语言子集的全功能解释器。

这一篇文章,我们将朝着我们的最终目标更进一步。

我们将更新我们的解释器来解析和解释我们的第一个完整的Pascal程序。

我们先来看一下要解释的Pascal程序代码:

PROGRAM Part10;
VAR
   number     : INTEGER;
   a, b, c, x : INTEGER;
   y          : REAL;

BEGIN {Part10}
   BEGIN
      number := 2;
      a := number;
      b := 10 * a + 10 * number DIV 6;
      c := a - - b
   END;
   x := 11;
   y := 20 / 7 + 3.14;
   { writeln('a = ', a); }
   { writeln('b = ', b); }
   { writeln('c = ', c); }
   { writeln('number = ', number); }
   { writeln('x = ', x); }
   { writeln('y = ', y); }
END.  {Part10}

在上方代码中,出现了我们之前没有接触过的内容。

实际上这些内容比较简单易懂,主要包括:

  • 程序头
  • 变量声明
  • DIV关键字
  • 注释

这些实际上也是这一篇文章的学习目标:

  • 如何解析和解释Pascal程序头;
  • 如何解析Pascal的变量声明;
  • 如何让解释器支持DIV关键字的整数除法和斜杠“/”的浮点数除法;
  • 如何增加对注释的支持。

一、更新语法

1、Program

程序由保留字(PROGRAM)、程序名称(一个变量)、分号“;”以及语句块(block)和点“.”(DOT)组成。

program : PROGRAM variable SEMI block DOT

例如:

2、block

语句块由声明语句和符合语句组成。

block : declarations compound_statement

例如:

3、declarations

声明语句由保留字(VAR)、一个或多个变量声明(variable_declaration与分号组成)组成,当然也可以没有变量声明(empty)。

declarations : VAR (variable_declaration SEMI)+ | empty

例如:

4、variable_declaration

变量声明包括包括变量名称(ID)或者多个逗号(COMMA)分隔的变量名称、冒号(COLON)以及数据类型(type_spec)组成。

variable_declaration : ID (COMMA ID)* COLON type_spec

例如:

5、type_spec

变量声明时的类型。

本篇文章中不做类型检查,所以暂时先只有整数类型。

type_spec : INTEGER

6、没有变化的文法

以下文法较之前没有变化,放在这里帮助大家对文法整体的理解。

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)*    

7、term

在我们的程序中,除法将分为整数除法(INTEGER_DIV )和浮点数除法(FLOAT_DIV)。

term : factor ((MUL | INTEGER_DIV | FLOAT_DIV) factor)* 

例如:

15 / 6 = 2.5

15 DIV 6 = 2

8、factor

在我们的程序中数字因子将分为(INTEGER_CONST )和实数因子(REAL_CONST )。

提示:实数包含整数与小数。

factor : PLUS factor | MINUS factor | INTEGER_CONST | REAL_CONST | LPAREN expr RPAREN | variable

同时,因为规则的改变,常量也将去除INTEGER,而增加INTEGER_CONST(整数)和REAL_CONST(实数)。

二、更新代码

按以往的套路,有了更新的文法之后,我们就根据文法更新代码。

主要要更新以下内容:

  • 更新词法分析器(Lexer)
  • 更新语法分析器(Parser)
  • 更新解释器(Interpreter)

在进行这些代码更新之前,我们需要先将常量进行更新。包括:

  • 实数类型:REAL(之前的整数INTEGER作为整数类型,无需再添加)
  • 整数:INTEGER_CONST
  • 实数:REAL_CONST
  • 整数除法符号:INTEGER_DIV
  • 浮点数除法符号:FLOAT_DIV
  • 程序标记:PROGRAM
  • 变量声明标记:VAR
  • 逗号:COMMA
  • 冒号:COLON

更新后的常量如下:

INTEGER = 'INTEGER'  # 整数类型
REAL = 'REAL'  # 实数类型
INTEGER_CONST = 'INTEGER_CONST'  # 整数(因子)
REAL_CONST = 'REAL_CONST'  # 实数(因子)
PLUS = 'PLUS'  # 加
MINUS = 'MINUS'  # 减
MUL = 'MUL'  # 乘
INTEGER_DIV = 'INTEGER_DIV'  # 整数除法
FLOAT_DIV = 'FLOAT_DIV'  # 浮点数除法
LPAREN = 'LPAREN'  # 左括号
RPAREN = 'RPAREN'  # 右括号
ID = 'ID'  # 变量名称
ASSIGN = 'ASSIGN'  # 赋值符号
BEGIN = 'BEGIN'  # 开始标记
END = 'END'  # 结束标记
SEMI = 'SEMI'  # 分号
DOT = 'DOT'  # 点(程序结束符)
PROGRAM = 'PROGRAM'  # 程序
VAR = 'VAR'  # 变量声明标记
COLON = 'COLON'  # 冒号
COMMA = 'COMMA'  # 逗号
EOF = 'EOF'  # 结束符号

另外,还有保留字需要添加:

  • VAR:变量声明
  • DIV:整数除法
  • PROGRAM:程序
  • 整数类型:INTEGER
  • 实数类型:REAL

更新后的保留字代码如下:

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'),
}

接下来,我们完成代码的更新。

1、更新词法分析器(Lexer)

首先,需要添加跳过注释的方法。

注释以大括号“{”开头和大括号“}”结尾。

所哟,当读取到的字符为大括号“{”时,需要跳过注释内容,当读取到大括号“}”时结束。

示例代码:

def skip_comment(self):  # 添加跳过注释内容到的方法
    while self.current_char != '}':  # 如果当前字符不是注释结束符号
        self.advance()  # 提取下一个字符
    self.advance()  # 提取下一个字符(跳过注释结束符号)

然后,我们的程序需要支持整数和浮点数。

当读取到整数字符时,需要向后依次读取字符,如果读取到小数点“.”,就将小数点加入数字字符串中,并继续读取小数点右侧的所有整数,否则直接读取完所有的整数字符。

示例代码:

def number(self):  # 添加处理整数和实数的方法
    result = ''  # 定义保存数字字符串的变量
    while self.current_char is not None and self.current_char.isdigit():  # 如果当前字符不是None并且为整数
        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():  # 如果当前字符不是None并且为整数(小数点后均为整数)
                result += self.current_char  # 连接已有数字字符串
                self.advance()  # 提取下一字符
            return Token(REAL_CONST, float(result))  # 遍历完小数点右侧所有整数后,返回存储了小数数值的实数记号。
    return Token(INTEGER_CONST, int(result))  # 没有小数点时,遍历完所有整数后,返回存储了整数数值的整数记号。

最后,我们更新get_next_token()方法,根据新的常量和词法分析规则更新代码。

def get_next_token(self):
    while self.current_char is not None:
        if self.current_char == '{':  # 如果当前字符为注释起始标记
            self.advance()  # 跳过当前字符
            self.skip_comment()  # 跳过注释内容
            continue  # 继续获取下一记号
        ...省略部分代码...
        if self.current_char.isdigit():  # 当前字符为整数时
            return self.number()  # 获取整数或实数记号
        if self.current_char == ':':  # 当前字符为冒号时
            self.advance()  # 提取下一字符
            return Token(COLON, ':')  # 返回冒号记号
        if self.current_char == ',':  # 当前字符为逗号时
            self.advance()  # 提取下一字符
            return Token(COMMA, ',')  # 返回逗号标记
        ...省略部分代码...
        if self.current_char == '/':  # 当前字符为斜杠时
            self.advance()  # 提取下一字符
            return Token(FLOAT_DIV, '/')  # 返回浮点数除法记号
        ...省略部分代码...
    return Token(EOF, None)

2、更新语法分析器(Parser)

根据新的文法,添加AST类。包括:Program、Block、VarDecl和Type。

示例代码:

class Program(AST):  # 定义程序节点
    def __init__(self, name, block):  # 程序由名称和语句块组成
        self.name = name
        self.block = block

class Block(AST):  # 定义语句块节点
    def __init__(self, declarations, compound_statement):  # 语句块由声明和符合语句组成
        self.declarations = declarations
        self.compound_statement = compound_statement

class VarDecl(AST):  # 定义变量声明节点
    def __init__(self, var_node, type_node):  # 变量声明由变量和类型组成
        self.var_node = var_node
        self.type_node = type_node

class Type(AST):  # 定义类型节点
    def __init__(self, token):
        self.token = token
        self.name = token.value

然后,在语法分析器中添加4个新的方法,用于解析新的语言结构,构造新的AST节点。

这些新的方法包括:block()、declarations()、variable_declaration()和type_spec()。

示例代码:

def block(self):  # 构造块节点的方法
    declarations = self.declarations()
    compound_statement = self.compound_statement()
    node = Block(declarations, compound_statement)  # 块节点由声明节点和符合语句节点组成
    return node

def declarations(self):  # 构造声明节点的方法
    declarations = []  # 声明节点包含多个变量声明节点
    if self.current_token.value_type == VAR:  # 如果当前记号为变量
        self.eat(VAR)  # 验证记号
        while self.current_token.value_type == ID:  # 遍历变量名称
            declarations.extend(self.variable_declaration())  # 声明列表中添加变量声明
            self.eat(SEMI)  # 验证分号
    return declarations  # 返回声明节点列表

def variable_declaration(self):  # 构造变量声明节点的方法
    var_nodes = [Variable(self.current_token)]  # 第一个变量声明节点添加到变量声明节点列表
    self.eat(ID)  # 验证变量名称记号
    while self.current_token.value_type == COMMA:  # 遍历逗号
        self.eat(COMMA)  # 验证逗号
        var_nodes.append(Variable(self.current_token))  # 添加变量节点到变量节点列表
        self.eat(ID)  # 验证变量名称记号
    self.eat(COLON)  # 验证冒号
    type_node = self.type_spec()  # 一组变量声明的类型节点
    var_declarations = [VarDecl(var_node, type_node) for var_node in var_nodes]  # 生成变量声明列表
    return var_declarations  # 返回变量声明节点列表

def type_spec(self):  # 构造变量类型节点的方法
    token = self.current_token  # 获取当前记号
    if token.value_type == INTEGER:  # 如果是整数类型
        self.eat(INTEGER)  # 验证整数记号
    else:  # 否则
        self.eat(REAL)  # 验证实数记号
    node = Type(token)  # 创建类型节点
    return node  # 返回类型节点

除此之外,根据新的文法,我们还要修改program()方法、term()方法和factor()方法。

示例代码:

def program(self):
    self.eat(PROGRAM)  # 验证程序开始标记
    var_node = self.variable()  # 获取变量节点
    program_name = var_node.name  # 获取程序名称
    self.eat(SEMI)  # 验证分号
    block_node = self.block()  # 获取块节点
    node = Program(program_name, block_node)  # 创建程序节点
    self.eat(DOT)  # 验证程序结束符号
    return node  # 返回程序节点

def term(self):
    node = self.factor()
    while self.current_token.value_type in (MUL, INTEGER_DIV, FLOAT_DIV):  # 除法修改为整数除法和浮点数除法
        token = self.current_token
        if token.value_type == MUL:
            self.eat(MUL)
        elif token.value_type == INTEGER_DIV:  # 整数除法
            self.eat(INTEGER_DIV)
        elif token.value_type == FLOAT_DIV:  # 浮点数除法
            self.eat(FLOAT_DIV)
        node = BinaryOperator(node, token, self.factor())
    return node

def factor(self):
    current_token = self.current_token

    if current_token.value_type == PLUS:
        ...省略部分代码...
    elif current_token.value_type == INTEGER_CONST:  # 整数
        self.eat(INTEGER_CONST)
        return Num(current_token)
    elif current_token.value_type == REAL_CONST:  # 实数
        self.eat(REAL_CONST)
        return Num(current_token)
    elif current_token.value_type == LPAREN:
        ...省略部分代码...

到这里,我们就完成了语法分析器部分的代码更新。

以下方这段Pascal程序为例:

PROGRAM Part10AST;
VAR
   a, b : INTEGER;
   y    : REAL;

BEGIN {Part10AST}
   a := 2;
   b := 10 * a + 10 * a DIV 4;
   y := 20 / 7 + 3.14;
END.  {Part10AST}

这段程序使用抽象语法树表示,如下图所示:(引用自鲁斯兰博客)

3、更新解释器(Interpreter)

对应着新添加的的4个AST类,我们需要在解释器中添加相应的访问方法:

  • visit_Program
  • visit_Block
  • visit_VarDecl
  • visit_Type

示例代码:

def visit_Program(self, node):  # 添加访问程序的方法
    self.visit(node.block)  # 访问语句块

def visit_Block(self, node):  # 添加访问语句块的方法
    for declaration in node.declarations:  # 遍历声明列表
        self.visit(declaration)  # 访问声明
    self.visit(node.compound_statement)  # 访问复合语句

def visit_VarDecl(self, node):  # 添加访问变量声明的方法
    pass  # 无需处理

def visit_Type(self, node):  # 添加访问类型的方法
    pass  # 无需处理

最后,我们还需要修改visit_BinaryOperator()方法来解释整数除法和浮点数除法。

def visit_BinaryOperator(self, node):
    if node.operator.value_type == PLUS:
        return self.visit(node.left) + self.visit(node.right)
    elif node.operator.value_type == MINUS:
        return self.visit(node.left) - self.visit(node.right)
    elif node.operator.value_type == MUL:
        return self.visit(node.left) * self.visit(node.right)
    elif node.operator.value_type == INTEGER_DIV:  # 如果是整数除法
        return self.visit(node.left) // self.visit(node.right)  # 返回整数除法运算结果
    elif node.operator.value_type == FLOAT_DIV:  # 如果是浮点数除法
        return self.visit(node.left) / self.visit(node.right)  # 返回浮点数除法运算结果

当我们完成以上全部代码,就可以对文章开始的Pascal程序进行解释了。

最终显示输出的符号表为:{‘number’: 2, ‘a’: 2, ‘b’: 23, ‘c’: 25, ‘x’: 11, ‘y’: 5.997142857142857}

让我们总结一下,在这一篇文章中都做了什么来完成了Pascal解释器的扩展:

  • 文法中添加了新规则并更新了现有规则;
  • 将新的记号和相关方法添加到词法分析器中,并更新和修改了现有的方法;
  • 将新的AST节点类添加到语法分析器中,以构建新的语言结构;
  • 将新的文法规则对应的新方法添加到了语法分析器中,并更新现有的方法;
  • 将新的访问方法添加到了解释器中,并更新现有访问方法。

通过这些变化,我们也解决了上一篇文章中提到的一些程序缺陷,实现了以下内容:

  • 解释器现在可以处理程序头;
  • 变量现在可以使用VAR关键字来声明;
  • DIV关键字用于整数除法,斜杠“/”用于浮点数除法。

练习:重新实现解释器而不看源代码,并使用文章开头的Pascal程序进行测试。

在下一篇文章中,我们将更深入的学习关于符号表的管理。

项目源代码下载:【点此下载

转载请注明:魔力Python » 一起来写个简单的解释器(10)

头像
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网站 (可选)