用 Python 从零开始写一个简单的解释器(4)

在本系列的前三篇文章中,我们已经为IMP语言建立了词法分析器解析器 和 抽象语法树AST。我们甚至写了自己的解析器组合库。在这最后一篇文章中,我们将会实现解释器的最后一个组件:求值器。

一起来了解一下通常一个程序是如何进行求值的。在任意给定的时间,有一些“控制点”,表明了程序下一步将要求值的语句。当下一个语句求值完毕,它通过推进“控制点”和改变变量值来修正程序状态。

为了给一个IMP程序求值,我们需要三样东西:

  1. 控制点—我们需要知道要求的值的下一条语句或表达式。
  2. 环境—我们需要一种调整“程序状态”的方法。
  3. 求值函数—我们需要知道如何调整每个语句或表达式的状态和控制点。

至少对IMP而言,控制点是最简单的。我们已经将中间表示都安排在一棵树状结构中了。只需要为高级语句调用求值函数,该函数将为其中的语句和表达式递归调用求值函数。我们基本上使用Python的控制点来作为我们自己的控制点。对于具有更复杂的控制结构像函数或异常之类的语言来说,这样做可能不那么简单,但对于IMP我们可以让它简单一些。

环境也很简单。IMP只有全局变量,所以我们可以用一个简单的Python字典塑造环境。不论什么时候,只要赋值发生了,我们就去更新字典里的变量值。

求值函数是我们唯一真正需要考虑的事情。每一种表达式都有一个求值函数,它将根据当前的环境返回一个值。算术表达式会返回一个整数,布尔表达式会返回真(true)与假(false)。表达式没有副作用,所以不会修改环境。每种声明语句也会有一个求值函数。声明语句的行为是修改环境,所以没有结果返回。

定义求值函数

我们会把求值函数定义为AST类的方法。这样一来,每个函数都能直接访问到它所求值的结构。这里是算术表达式的函数集:

你会注意到,当程序员使用了一个尚未定义的变量(不在环境字典中)时,我们添加了一些额外的逻辑。为了尽量简单,避免再写一个错误处理系统,我们给所有未定义的变量赋值为0。

BinopAexp中我们通过抛出一个RuntimeError来处理“未知操作符”。解析器不能使用未知操作符创建一个AST,所以在实际中我们不用担心这个。

这里是布尔表达式的函数:

这些都比较简单直观。它们只是使用了Python内置的关系和逻辑运算符。

这里是每种语句对应的求值函数:

对于AssignStatement,我们只是对右边的算术表达式求值,然后用结果值更新环境。程序员可以自由地重新定义已分配的变量。

在 CompoundStatement中,我们只是挨个对每个语句求值。要记住, CompoundStatement可以用于任何可以使用语句的地方,所以比较长的语句链会被编码为嵌套复合语句。

IfStatement中,我们首先求值条件布尔表达式。如果结果为真,就对真分支的语句求值。如果结果为假,而且假分支的语句又存在,就对假分支的语句求值。

WhileStatement中,我们对开头的条件求值以检测循环体是否应该再执行一遍。

每次循环迭代结束后都应该对条件求值,以检查它是否为真。

组合

我们已经建立好解释器的每一个主要部分。只需要一个驱动程序来将它们集成起来:

程序只需要一个参数:要解释的文件名。它读入文件并传给词法分析器和解析器,如果发现错误会报告出来。我们从解析结果中抽象出AST,然后以一个空字典作为起始环境对AST求值。由于IMP不能在终端输出任何值,我们只能在程序完成后,打印环境中的所有值,以此确认整个过程的实际发生。

这里是一个典型的阶乘实例:

求值结果如下:

总结

在前面的四篇文章中,我们从头开始为一门简单语言构建了一个解释器。尽管语言本身不是非常有用,但解释器是可扩展的,而且它的主要组件(词法分析器和解析器组合库)都是可重用的。

我希望这能给尝试语言设计的人们提供一个很好的起点。这里有一些实践建议:

  • 尽量定义局部变量(比如,循环外面不应使用循环内的变量);
  • 添加一个for循环结构;
  • 为用户输入输出添加scan和print声明;
  • 添加函数。
1 2 收藏 评论

关于作者:fzr

微博:@fzr-fzr) 个人主页 · 我的文章 · 25

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部