用 Python 从零开始写一个简单的解释器（4）
（点击上方公号，可快速关注)
在本系列的前三篇文章中，我们已经为IMP语言建立了词法分析器、解析器 和 抽象语法树AST。我们甚至写了自己的解析器组合库。在这最后一篇文章中，我们将会实现解释器的最后一个组件：求值器。
一起来了解一下通常一个程序是如何进行求值的。在任意给定的时间，有一些“控制点”，表明了程序下一步将要求值的语句。当下一个语句求值完毕，它通过推进“控制点”和改变变量值来修正程序状态。
为了给一个IMP程序求值，我们需要三样东西：
控制点—我们需要知道要求的值的下一条语句或表达式。
环境—我们需要一种调整“程序状态”的方法。
求值函数—我们需要知道如何调整每个语句或表达式的状态和控制点。
至少对IMP而言，控制点是最简单的。我们已经将中间表示都安排在一棵树状结构中了。只需要为高级语句调用求值函数，该函数将为其中的语句和表达式递归调用求值函数。我们基本上使用Python的控制点来作为我们自己的控制点。对于具有更复杂的控制结构像函数或异常之类的语言来说，这样做可能不那么简单，但对于IMP我们可以让它简单一些。
环境也很简单。IMP只有全局变量，所以我们可以用一个简单的Python字典塑造环境。不论什么时候，只要赋值发生了，我们就去更新字典里的变量值。
求值函数是我们唯一真正需要考虑的事情。每一种表达式都有一个求值函数，它将根据当前的环境返回一个值。算术表达式会返回一个整数，布尔表达式会返回真（true）与假（false）。表达式没有副作用，所以不会修改环境。每种声明语句也会有一个求值函数。声明语句的行为是修改环境，所以没有结果返回。
定义求值函数
我们会把求值函数定义为AST类的方法。这样一来，每个函数都能直接访问到它所求值的结构。这里是算术表达式的函数集：
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，所以在实际中我们不用担心这个。
这里是布尔表达式的函数：
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内置的关系和逻辑运算符。
这里是每种语句对应的求值函数：
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中，我们对开头的条件求值以检测循环体是否应该再执行一遍。
每次循环迭代结束后都应该对条件求值，以检查它是否为真。
组合
我们已经建立好解释器的每一个主要部分。只需要一个驱动程序来将它们集成起来：
#!/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不能在终端输出任何值，我们只能在程序完成后，打印环境中的所有值，以此确认整个过程的实际发生。
这里是一个典型的阶乘实例：
n := 5;
p := 1;
while n > 0 do
p := p * n;
n := n - 1
end
总结
在前面的四篇文章中，我们从头开始为一门简单语言构建了一个解释器。尽管语言本身不是非常有用，但解释器是可扩展的，而且它的主要组件（词法分析器和解析器组合库）都是可重用的。
我希望这能给尝试语言设计的人们提供一个很好的起点。这里有一些实践建议：
尽量定义局部变量（比如，循环外面不应使用循环内的变量）；
添加一个for循环结构；
为用户输入输出添加scan和print声明；
添加函数。
Python开发者
微信号：PythonCoder
可能是东半球最好的 Python 微信号
--------------------------------------
投稿网址：top.jobbole.com
商务合作QQ：2302462408