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

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

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

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

通过前面的学习,我们了解了以下内容:

1、 如何把语句分解为记号。

这个过程叫做词法分析(lexical analysis)。

解释器的一部分被称作词法分析器(lexical analyzer或 lexer)、扫描器(scanner)或记录器(tokenizer)。

我们已经学会不借助正则表达式或其它任何工具(例如Lex)从底层编写我们的词法分析器。

2、 如何识别出记号流中的短语。

在记号流中识别一个短语的过程,或者说,在记号流中找到短语结构的过程称为解析(parsing)或语法分析(syntax analysis)。

解释器或编译器中,完成这项工作的部分称为解析器(parser)或语法分析器(syntax analyzer)。

3、 如何用语法图来表示编程语言的语法规则。

语法图是编程语言中语法规则的图形表示,它直观地表达了在我们的编程语言中哪些语句是允许的,哪些是不允许的。

4、 如何使用另一种广泛使用的表示法来指定编程语言的语法。

这里说的是上下文无关文法(context-free grammars),简称为文法(grammars)或BNF(Backus-Naur Form)。

5、 如何将文法映射到代码,以及如何编写递归下降解析器(recursive-descent parser)。

6、 如何编写一个真正的基本解释器(interpreter)。

7、 运算符的结合律(associativity)和优先级(precedence)如何工作,以及如何使用优先级表构造文法。

8、 如何构造一个解析语句的抽象语法树(Abstract Syntax Tree :AST),以及如何将Pascal的整个源程序表示为一个大的AST。

9、 如何访问AST,以及如何将我们的解释器作为AST节点访问器来实现。

正如上面所说的,凭借我们的知识和经验,我们已经建立了一个解释器,可以进行词法分析、语法分析和构建AST,并通过访问AST来解释我们的第一个完整的Pascal程序。

如果你一直没有松懈的学习完上面所说的内容,并已理解这些内容,那么收获一定是很多的。

不过,虽然我们已经覆盖了很多方面,但还有更令人兴奋的内容正在到来。

到目前为止,我们差不多已经准备好去处理以下内容:

  • 嵌套过程与函数
  • 过程与函数调用
  • 语义分析(类型检查,确保变量在使用之前声明,并且基本上检查程序是否有意义。)
  • 控制流程单元(例如if语句)
  •  聚合数据类型(Records)
  •  更多内置类型
  •  源代码级调试器(Source-level debugger)
  •  其它上面没有提到优点

但是,在我们接触这些内容之前,我们需要先建立坚实的基础以及必要设施。

这里所指的是符号、符号表和域这些超级重要的内容。

这些内容会涵盖几篇文章。

一、 符号(Symbol)

首先,我们要了解什么是符号,以及我们为什么要对符号进行追踪。

出于我们的目的,我们非正式地将符号定义为某些程序实体的标识符,例如变量、子程序或内置类型。

如果想符号有用,它们至少需要获取它们所识别的程序实体的以下信息:

  •  名称:例如“x”、“y”或“number”等。
  •  类别:例如变量、子程序或内置类型。
  •  类型:例如整数或实数。

这篇文章中,我们将处理变量符号和内置类型符号,因为我们以前已经使用过变量和类型。

提示:“内置类型”是指非自定义的类型,可以直接使用,例如之前的INTEGER和REAL类型。

我们来看一段Pascal程序,注意变量声明部分。

示例代码:

PROGRAM Part11;
VAR
   x : INTEGER;
   y : REAL;
BEGIN 
END.

我们能够看到,在上面这段代码中有4个符号:两个变量符号(x和y)和两个内置类型符号(INTEGER和REAL)。

1、如何在代码中表示符号?

我们可以创建一个基本符号类,类的参数为符号的名称“name”和类型“symbol_type”。

注意,并非所有符号都有与之关联的类型,所以符号类型是可选参数。

示例代码:

class Symbol:  # 添加符号类
    def __init__(self, name, symbol_type=None):
        self.name = name  # 符号名称
        self.symbol_type = symbol_type  # 符号类型

2、如何在代码中表示内置类型符号?

在符号类的代码中,我们没有看到类别的参数(注意类别和类型是两个概念)。

不同类别的符号,我们以类的类名来体现。

这意味着我们需要创建单独的类来表示不同的符号类别。

我们从基本的内置类型开始。

内置类型符号类继承自符号类,构造函数只需要类型的名称。

示例代码:

class BuiltinTypeSymbol(Symbol):  # 添加内置类型符号类
    def __init__(self, name):
        super().__init__(name)  # 调用基类构造函数初始化

    def __str__(self):
        return self.name  # 返回符号名称

    __repr__ = __str__

提示:在前文已经有过详细的介绍,双下划线(double underscore:简称dunder)中的方法__str__()和__repr__()是特殊的Python方法(或者叫魔法方法),通过这两个方法我们已经让它们具有良好的格式化消息,通过print()函数打印符号对象或者在Python Shell中创建符号对象并输入这个对象名称后回车时即可看到。

启动Python Shell,我们查看一下:


3、如何在代码中表示变量符号?

按照前面所说的,类名表示不同类别的符号,我们需要创建一个VarSymbol类。

示例代码:

class VarSymbol(Symbol):  # 添加变量符号类
    def __init__(self, name, symbol_type):
        super().__init__(name, symbol_type)  # 调用基类构造函数初始化

    def __str__(self):
        return f'<{self.name}:{self.symbol_type}>'  # 返回符号信息

    __repr__ = __str__

在变量符号类中,变量的名称和类型都是必选参数,类名“VarSymbol”表明类的实例将标识一个变量符号(类别是变量)。

再次进入Python shell,我们手动构造变量符号的实例:

正如我们所看到的,首先创建一个内置类型符号的实例,然后将它作为参数传递给VarSymbol类的构造函数。

符号的层次结构如下图所示:

二、跟踪符号

跟踪符号的原因主要包括:

  • 为了确保当我们为变量赋值时,类型是正确的(类型检查);
  • 确保在使用变量之前声明变量;

下面是一个的错误Pascal程序代码:

PROGRAM Part11;
VAR
   x : INTEGER;
   y : REAL;
BEGIN
   y := 3.5;
   x := 2 + y;
   x := a;
END.

上面的程序代码有两个问题:

1、在赋值语句“x := 2 + y”中,我们给变量“x”声明为整数类型,但是赋值却是整数与实数之和(实数类型),因此导致类型不兼容,无法解释。

2、在赋值语句“x := a”中,我们引用了未声明的变量“a”。

为了能够在运行时,对程序的源代码解释或求值之前识别这样的情况,我们需要跟踪程序符号。

那么,在哪里存储我们追踪的符号呢?

大家应该还记得符号表(symbol table)。

符号表是一种抽象数据类型(Abstract Data Type:ADT),用于跟踪源代码中的各种符号。

与之前不同,在这篇文章中,我们将把符号表实现为一个单独的类,并使用一些辅助方法。

我们将用符号表来执行两个主要操作:存储符号并能够按名称查找。

因此,我们需要定义两个辅助方法:define()和lookup()。

define()方法以符号对象作参数,并以符号对象的名称为key和符号对象自身为value,将符号对象存储在内部的有序字典中。

lookup()方法将符号对象名称作为参数,如果找到符号对象,则返回一个符号对象,否则返回None。

示例代码:

class SymbolTable:  # 添加符号表类
    def __init__(self):
        self._symbols = OrderedDict()  # 存储符号的有序字典

    def __str__(self):
        return f'Symbols:{[value for value in self._symbols.values()]}'  # 返回符号列表信息

    __repr__ = __str__

    def define(self, symbol):  # 添加定义符号的方法
        print(f'定义:{symbol}')
        self._symbols[symbol.name] = symbol  # 符号添加到字典

    def lookup(self, name):  # 添加查询符号的方法
        print(f'查询:{name}')
        return self._symbols.get(name)  # 返回符号对象

 

我们尝试为下方的Pascal程序手动填充符号表,包括创建变量符号和内置类型符号:

PROGRAM Part11;
VAR
   x : INTEGER;
   y : REAL;
BEGIN
END.

再次启动Python shell:

如果你能够看到符号字典的内容,会像下图这样:

那么,如何让程序自动构建符号表呢?

我们编写另一个节点访问器类来访问由语法分析器构建的AST。

这是另一个拥有像AST这样的中间形式有用的例子。

我们不是扩展我们的语法分析器来处理符号表,而是分开关注点并编写一个新的节点访问器类。

在这样做之前,让我们在创建符号表实例时扩展符号表类来初始化内置类型。

下面是符号表类的全部源代码。

示例代码:

class SymbolTable:  # 添加符号表类
    def __init__(self):
        self._symbols = OrderedDict()  # 存储符号的有序字典
        self.__init_builtins()  # 初始化内置类型符号

    def __init_builtins(self):  # 添加初始化内置类型符号的方法
        self.define(BuiltinTypeSymbol('INTEGER'))  # 定义整数类型符号
        self.define(BuiltinTypeSymbol('REAL'))  # 定义实数类型符号

    def __str__(self):
        return f'Symbols:{[value for value in self._symbols.values()]}'  # 返回符号列表信息

    __repr__ = __str__

    def define(self, symbol):  # 添加定义符号的方法
        print(f'定义:{symbol}')
        self._symbols[symbol.name] = symbol  # 符号添加到字典

    def lookup(self, name):  # 添加查询符号的方法
        print(f'查询:{name}')
        return self._symbols.get(name)  # 返回符号对象

下面实现符号表生成器(AST节点访问器)的源代码。

需要注意,符号表的创建是为了跟踪符号,所以也需要对AST进行访问,这一点和解释器很像,方法代码有很多相同之处。

不过符号表不负责解释工作,只是对符号的定义与赋值进行验证。

当符号表完成验证之后,解释器才会对AST进行访问,执行解释过程。

基于上面所说的内容,我们添加符号表生成器类中的方法,这些方法都应与访问AST中的符号有关(注意注释中括号部分)。

示例代码:

class SymbolTableBuilder(NodeVisitor):  # 添加符号表生成器类
    def __init__(self):  # 初始化
        self.symbol_table = SymbolTable()  # 创建符号表对象

    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):  # 添加访问变量声明节点方法
        type_name = node.type_node.value  # 获取变量类型名称
        symbol_type = self.symbol_table.lookup(type_name)  # 获取变量类型
        var_name = node.var_node.value  # 获取变量名称
        var_symbol = VarSymbol(var_name, symbol_type)  # 创建变量符号对象
        self.symbol_table.define(var_symbol)  # 变量符号对象添加到符号表

    def visit_Compound(self, node):  # 添加访问复合语句节点的方法
        for child in node.children:  # 遍历语句节点列表
            self.visit(child)  # 访问语句节点(语句中可能包含符号)

    def visit_NoOperator(self, node):  # 添加访问空语句的节点
        pass  # 不做任何处理(空语句之后的语句可能包含符号,需要跳过空语句)

def visit_BinaryOperator(self, node):  # 添加访问二元运算符方法(二元运算中可能包含符号)
    self.visit(node.left)  # 访问左侧节点
    self.visit(node.right)  # 访问右侧节点

def visit_Num(self, node):  # 添加访问数字的方法
    pass  # 不做任何处理(数字节点之后的内容可能包含符号,需要跳过数字,因为不进行解释,也无需返回数字的值)

def visit_UnaryOperator(self, node):  # 添加访问一元运算符方法
    self.visit(node.expr)  # 访问表达式节点(表达式中可能包含符号)

我们以前在解释器类中见过大多数方法,但是visit_VarDecl()方法值得特别注意。

该方法负责访问(或者叫walking)一个VarDecl(变量声明)的AST节点并将相应的变量符号存储到符号表中。

首先,该方法在符号表中按名称查找内置类型符号,然后创建VarSymbol类的实例,并将其存储(或者叫定义)在符号表中。

我们用符号表生成器(AST 访问器)进行测试,查看运行中的动作。

测试代码:

PROGRAM Part11;
VAR
   x : INTEGER;
   y : REAL;
BEGIN
END.

测试结果:

在上面的交互会话中,您可以看到“定义:…”和“查询:…”消息的序列,这些消息指示符号在符号表中定义和查找的顺序。

会话中的最后一个命令打印符号表的内容,我们可以看到它与我们以前手动构建的符号表的内容完全相同。

AST访问器的好处在于他们几乎自动完成了所有的工作。

我们可以很好的利用符号表和符号表生成器,使用它们来验证变量在赋值和表达式中使用之前完成了声明。

需要做的是在访问器中再添加两个两个方法:visit_Assign()和 visit_Variable()。

示例代码:

def visit_Assign(self, node):  # 添加访问赋值节点的方法
    var_name = node.left.name  # 获取变量名称
    var_symbol = self.symbol_table.lookup(var_name)  # 查询变量符号
    if var_symbol is None:  # 如果变量未声明
        raise NameError(f'错误的标识符:{repr(var_name)}')  # 抛出名称错误异常
    self.visit(node.right)  # 访问右侧节点(赋值语句右侧可能包含符号)

def visit_Variable(self, node):  # 添加访问变量节点的方法
    var_name = node.name  # 获取变量名称
    var_symbol = self.symbol_table.lookup(var_name)  # 查询变量符号
    if var_symbol is None:  # 如果变量未声明
        raise NameError(f'错误的标识符:{repr(var_name)}')  # 抛出名称错误异常

如果无法从符号表中查询到符号对象,这些方法将引发名称错误。

下面我们通过错误的程序代码,进行验证。

错误代码:(代码中引用了未声明的变量“b”)

PROGRAM NameError1;
VAR
   a : INTEGER;

BEGIN
   a := 2 + b;
END.

我们来看一下,如果我们为程序构造一个AST并将它传递给我们的符号表生成器去访问,将会怎么样?

打开Python Shell进行测试:

结果符合我们的预期。

再来看另外一个错误的示例。

错误示例:(给尚未声明的变量“a”赋值)

PROGRAM NameError2;
VAR
   b : INTEGER;

BEGIN
   b := 1;
   a := b + 2;
END.

打开Python Shell进行测试:

通过测试,我们的新访问器同样发现了这个问题。

再次强调一下:我们的符号表生成器(AST访问器)所做的所有检查都是在运行时之前进行的,也就是在我们的解释器解释源程序之前完成的。

我们通过解释下面的程序,彻底把这个概念了解清楚:

PROGRAM Part11;
VAR
   x : INTEGER;
BEGIN
   x := 2;
END.

在程序退出之前,符号表和运行时GLOBAL_MEMORY的内容将是这样的:

我们能够看到符号表不会为变量“x”保存它的值“2”。

因为保存变量值是由解释器完成。

还记得第9部分中符号表用作全局存储的图片吗?

现在,我们已经我们有效地去掉了符号表作为全局存储的双重任务。

接下来,我们修改一下解释器和主程序,并通过测试代码进行测试。

测试代码:

PROGRAM Part11;
VAR
   number : INTEGER;
   a, b   : INTEGER;
   y      : REAL;

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

示例代码:(Interpreter)

class Interpreter(NodeVisitor):  # 修改解释器
    def __init__(self, tree):  # 修改构造方法
        self.tree = tree  # 获取参数AST
        self.GLOBAL_MEMORY = OrderedDict()  # 创建全局存储字典
    ...省略访问方法...
    def interpret(self):  # 修改解释方法
        tree = self.tree  # 获取AST
        if tree is None:  # 如果AST不存在
            return ''  # 返回空字符串
        return self.visit(tree)  # 否则访问AST

示例代码:(主程序)

def main():
    text = '''
        PROGRAM Part11;
        VAR
           number : INTEGER;
           a, b   : INTEGER;
           y      : REAL;
        
        BEGIN {Part11}
           number := 2;
           a := number ;
           b := 10 * a + 10 * number DIV 4;
           y := 20 / 7 + 3.14
        END.  {Part11}
    '''
    lexer = Lexer(text)
    parser = Parser(lexer)
    tree = parser.parser()
    symtab_builder = SymbolTableBuilder()
    symtab_builder.visit(tree)
    print('符号表中的内容:\n', symtab_builder.symbol_table)
    print('-----------------------------------------------')
    print('开始解释代码...')
    interpreter = Interpreter(tree)
    interpreter.interpret()
    print('全局存储中的内容:')
    for k, v in interpreter.GLOBAL_MEMORY.items():
        print(f'{k}:{v}')

运行程序代码的结果如下:

定义:INTEGER
定义:REAL
查询:INTEGER
定义:<number:INTEGER>
查询:INTEGER
定义:<a:INTEGER>
查询:INTEGER
定义:<b:INTEGER>
查询:REAL
定义:<y:REAL>
查询:number
查询:a
查询:number
查询:b
查询:a
查询:number
查询:y
符号表中的内容:
Symbols:[INTEGER, REAL, <number:INTEGER>, <a:INTEGER>, <b:INTEGER>, <y:REAL>]
-----------------------------------------------
开始解释代码...
全局存储中的内容:
number:2
a:2
b:25
y:5.997142857142857

这里再强调一下,解释器类与构建符号表无关,它依赖于符号表生成器,以确保源代码中的变量在被解释器使用之前已经正确的声明。

最后,检查一下自己对概念的理解:

  • 符号是什么?
  • 为什么我们需要跟踪符号?
  • 符号表是什么?
  • 定义符号和解析/查找符号有什么区别?
  • 下面给定的Pascal小程序,符号表和全局存储(解释器中的全局存储字典字典)分别是什么内容?
PROGRAM Part11;
VAR
   x, y : INTEGER;
BEGIN
   x := 2;
   y := 3 + x;
END.

下一篇文章中,我们继续学习解析嵌套过程的内容。

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

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

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

表情

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

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