用 Python 从零开始写一个简单的解释器（4），python解释器,未经许可，禁止转载！英文

用 Python 从零开始写一个简单的解释器（4），python解释器,未经许可，禁止转载！英文

本文由 编橙之家 - fzr 翻译，JustinWu 校稿。未经许可，禁止转载！
英文出处：Jay Conrod。欢迎加入翻译组。

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

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

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

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

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

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

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

定义求值函数

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

Python

class IntAexp(Aexp):
    ...
    def eval(self, env):
        return self.i

class VarAexp(Aexp):
    ...
    def eval(self, env):
        if self.name in env:
            return env[self.name]
        else:
            return 0

class BinopAexp(Aexp):
    ...
    def eval(self, env):
        left_value = self.left.eval(env)
        right_value = self.right.eval(env)
        if self.op == '+':
            value = left_value + right_value
        elif self.op == '-':
            value = left_value - right_value
        elif self.op == '*':
            value = left_value * right_value
        elif self.op == '/':
            value = left_value / right_value
        else:
            raise RuntimeError('unknown operator: ' + self.op)
        return value

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

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

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

Python

class RelopBexp(Bexp):
    ...
    def eval(self, env):
        left_value = self.left.eval(env)
        right_value = self.right.eval(env)
        if self.op == '<':
            value = left_value < right_value
        elif self.op == '<=':
            value = left_value <= right_value
        elif self.op == '>':
            value = left_value > right_value
        elif self.op == '>=':
            value = left_value >= right_value
        elif self.op == '=':
            value = left_value == right_value
        elif self.op == '!=':
            value = left_value != right_value
        else:
            raise RuntimeError('unknown operator: ' + self.op)
        return value

class AndBexp(Bexp):
    ...
    def eval(self, env):
        left_value = self.left.eval(env)
        right_value = self.right.eval(env)
        return left_value and right_value

class OrBexp(Bexp):
    ...
    def eval(self, env):
        left_value = self.left.eval(env)
        right_value = self.right.eval(env)
        return left_value or right_value

class NotBexp(Bexp):
    ...
    def eval(self, env):
        value = self.exp.eval(env)
        return not value

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

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

Python

 class AssignStatement(Statement):
    ...
    def eval(self, env):
        value = self.aexp.eval(env)
        env[self.name] = value

class CompoundStatement(Statement):
    ...
    def eval(self, env):
        self.first.eval(env)
        self.second.eval(env)

class IfStatement(Statement):
    ...
    def eval(self, env):
        condition_value = self.condition.eval(env)
        if condition_value:
            self.true_stmt.eval(env)
        else:
            if self.false_stmt:
                self.false_stmt.eval(env)

class WhileStatement(Statement):
    ...
    def eval(self, env):
        condition_value = self.condition.eval(env)
        while condition_value:
            self.body.eval(env)
            condition_value = self.condition.eval(env)

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

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

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

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

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

组合

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

Python

#!/usr/bin/env python

import sys
from imp_parser import *
from imp_lexer import *

def usage():
    sys.stderr.write('Usage: imp filenamen')
    sys.exit(1)

if __name__ == '__main__':
    if len(sys.argv) != 2:
        usage()
    filename = sys.argv[1]
    text = open(filename).read()
    tokens = imp_lex(text)
    parse_result = imp_parse(tokens)
    if not parse_result:
        sys.stderr.write('Parse error!n')
        sys.exit(1)
    ast = parse_result.value
    env = {}
    ast.eval(env)

    sys.stdout.write('Final variable values:n')
    for name in env:
        sys.stdout.write('%s: %sn' % (name, env[name]))

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

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

Python

n := 5;
p := 1;
while n > 0 do
  p := p * n;
  n := n - 1
end

求值结果如下：

Python

$ ./imp.py hello.imp
Final variable values:
p: 120
n: 0

总结

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

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

• 尽量定义局部变量（比如，循环外面不应使用循环内的变量）；
• 添加一个for循环结构；
• 为用户输入输出添加scan和print声明；
• 添加函数。