博客|刀背藏身
先来看看这篇文章 怎样写一个解释器

所谓虚拟机器，就是一定意义上的堆栈机。
解释器能够执行其他计算机语言编写的程序的系统软件，他是一个翻译程序。它的执行方式是一边翻译一边执行，因此其执行效率一般比较低。解释器的实现比较简单，而且编写源程序的高级语言可以使用更加灵活和富于表现力的语法。
可参考本链接，开源项目Crianza。
当然，解释器要从最基础的最简单的语言开始，然后逐步增加语言的复杂度，才能构造出正确的解释器。而最基础的一个解释器，其实就是一个高级的计算器，下面我们一起来创建一个解释器吧。

0. 解释器到底是什么

前边解释了一些，但解释的并不清楚，在怎样写一个解释器中，做一个比较不错的解释。

首先我们来谈一下解释器是什么。说白了解释器跟计算器差不多。它们都接受一个“表达式”，输出一个 “结果”。比如，得到 '(+ 1 2) 之后就输出 3。不过解释器的表达式要比计算器的表达式复杂一些。解释器接受的表达式叫做“程序”，而不只是简单的算术表达式。从本质上讲，每个程序都是一台机器的“描述”，而解释器就是在“模拟”这台机器的运转，也就是在进行“计算”。所以从某种意义上讲，解释器就是计算的本质。当然，不同的解释器就会带来不同的计算。

需要注意的是，我们的解释器接受的参数是一个表达式的“数据结构”，而不是一个字符串。这里我们用一种叫“S-expression”的数据结构来表示表达式。比如表达式 '(+ 1 2) 里面的内容是三个符号：'+, '1 和 '2，而不是字符串“(+ 1 2)”。从结构化的数据里面提取信息很方便，而从字符串里提取信息很麻烦，而且容易出错。

从广义上讲，解释器是一个通用的概念。计算器实际上是解释器的一种形式，只不过它处理的语言比程序的解释器简单很多。也许你会发现，CPU 和人脑，从本质上来讲也是解释器，因为解释器的本质实际上是“任何用于处理语言的机器”。

1. 学习写一个解释器的另一个原因

在《编程珠玑》的第十章，提到代码空间技术，如何节省足够的空间，讲到了解释程序。他说，远古时代，有时候空间的瓶颈不在于数据，而在于程序本身的规模。比如一开始一个图形程序，有如下代码：

for i = [17, 43] set(i, 68)
for i = [18, 42] set(i, 69)
for j = [81, 91] set(30, j)
for j = [82, 92] set(31, j)

其中，set(i,j)表示点亮屏幕（i, j）处的像素，也就是说这实际上是一个绘制直线的程序。而当我们使用了适当的函数，比如用于绘制水平线的hor函数和垂直线的ver函数，就可以替代上述代码：

hor(17, 43, 68)
hor(18, 42, 69)
ver(81, 91, 30)
ver(82, 92, 31)

而上述代码又可以利用一个解释器来替换，这个解释程序可以从下面的数组中读取命令。

h 17, 43, 68
h 18, 42, 69
v 81, 91, 30
v 82, 92, 31

至此，我们已经将空间减小了很多了，但如果你还想减少，那么就可以为命令h 或 v分配两个位，为后边的三个数字，每个数字，分配10个位置，这样一个32位的数字，表示一行命令了。这就是代码空间技术的运用。

当然，今天我们谈起节省空间，好像已经成了笑话，但是，当我们面对巨量数据，也就是我们今天所说的大数据的时候，空间，时间，效率的话题又一次被提起来。当我们面对着像混乱电流一样的数据时，尝试将自己的头脑想象成计算机，学会用更加底层的方式去思考，对对理解数据处理将有更深刻的认识。

为什么我们时常提起像机器一样思考呢？那是因为机器远比我们人类严谨，也是所有检验逻辑最严格的关卡，他不容许一点点错误，一个毫不起眼的bug，都会让程序完全崩溃。而程序是写给计算机的语言，所以，程序的严谨性就应当像计算机一样严谨。所以我们时常劝告自己要像计算机一样思考。

正如『正义的花生』在数学与编程中提到的一样：

普通程序员使用的编程语言，就算是C++这样毛病众多的语言，其实也已经比数学家使用的语言好很多。用数学的语言可以写出含糊复杂的证明，在期刊或者学术会议上蒙混过关，用程序语言写出来的代码却无法混过计算机这道严格的关卡。因为计算机不是人，它不会迷迷糊糊的点点头让你混过去，或者因为你是大师就不懂装懂。代码是需要经过现实的检验的。如果你的代码有问题，它迟早会导致出问题。

诚然，大牛作者在思想上有很多偏执的地方，但是往往他的观点我都有着不小的认同感。前边那篇『怎样写一个解释器』也是他的文章。

所以，学习写一个解释器，可以带给我更多的思考，从效率，空间，机器等等方面进一步认识程序运行的本质，将这种认识正反馈到实际编程中，将潜移默化的带来影响。当然，这篇文章试着依葫芦画瓢的写完一个解释器，显然仅仅算是摸了摸门道，想要继续探索，还有更多的事情可以做。做更多的事情，可以参考上边提到的开源项目Crianza。

2. 构建堆栈机

堆栈机的执行原理很简单，将需要处理的值放进堆栈中，然后执行。Python， Java这些高级语言将它作为自己的虚拟机。

所以我们利用了堆栈的方式存放指令。首先，我们需要一个指令指针栈，它能够储存返回地址。这个返回地址就是当我们执行一个子程序（如函数）的时候，需要用它跳回到开始调用该函数的地方。

我们将这个复杂的问题简洁化。比如有一个数学表达式：（2+3）*4 ，这个表达式的意思就是依次推入2 3 + 4 *, 将2 和3 依次推入栈中，接下来要推入的指令是 +， 将两个数字弹出，令他们执行加法运算，然后将结果入栈。然后继续进行下去，直到计算出结果。

依靠这个原理，我们开始建立一个栈，我们使用python 中的一个类 collections.deque。

from collections import deque
class Stack(deque): # 定义一个栈
    push = deque.append  # 添加元素
    # 返回最后一个元素
    def top(self):
        return self[-1]

deque 中自带pop 方法，所以我们就不用再定义 pop .

接下来我们继续构建一个虚拟机的类 Machine。 我们需要两个栈和一段储存代码的内存空间。一个栈储存数据，一个栈储存地址。得益于Python 动态类型，因此我们可以往列表里面存储任何东西，但是我们不能区分列表里面的内置函数和字符串，正确的做法是将Python 内置函数单独存放在一个列表。这里我们使用字典方法，键值分别对应字符串和函数。另外，我们需要一个指令指针，用来指向代码中下一个需要被执行的模块。

class Machine:
    def __init__(self, code): # 预先定义一个初始化函数
       self.data_stack = Stack()
       self.return_addr_stack = Stack()
       self.code = code
       self.instruction_pointer = 0 
    # 再创建一些栈结构中必备的函数
    def pop(self):
        return self.data_stack.pop()
    def push(self, value):
        self.data_stack.push(value)
    def top(self):
        return self.data_stack.top()

为了执行操作码，而这个操作码并非实际意义上的操作码，它只是一种动态类型，所以我们建立一个dispatch 函数，在这之前，我们创建一个解释器的循环。

def run(self):   # 代码运行的条件
    while self.instruction_pointer < len(self.code):
         opcode = self.code[self.instruction_pointer]
         self.instruction_pointer += 1
         self.dispatch(opcode)

它的原理很简单： 获取下一个指令，指令指针自增1 然后基于操作码执行dispatch 函数，下面就是dispatch函数的定义。而对解释器的扩展增强基本在这个函数中实现。

def dispatch(self, op):
    dispatch_map = {
        "%":        self.mod,
        "*":        self.mul,
        "+":        self.plus,
        "-":        self.minus,
        "/":        self.div,
        "==":       self.eq,
        "cast_int": self.cast_int,
        "cast_str": self.cast_str,
        "drop":     self.drop,
        "dup":      self.dup,
        "if":       self.if_stmt,
        "jmp":      self.jmp,
        "over":     self.over,
        "print":    self.print_,
        "println":  self.println,
        "read":     self.read,
        "stack":    self.dump_stack,
        "swap":     self.swap,
        }
    if op in dispatch_map:
        dispatch_map[op]()
    elif isinstance(op, int):  # 如果指令是整形数据，就将数据存放到数据栈中
        self.push(op)
    elif isinstance(op, str) and op[0]==op[-1]=='"':
        # 如果是字符串类型，就将字符串内容存放到数据栈中
        self.push(op[1:-1])
    else:
        raise RuntimeError( "Unknown opcode: '%s'" % op)

上边的指令的意思是，当输入一段指令后，该函数就会根据这段指令在字典中找到对应的方法。比如符号*对应的是self.mul 。而这个self.mul 也是我们定义的函数：

def mul(self):
    self.push(self.pop() * self.pop())

其他的函数定义也如此。

搭建好环境之后，下面继续进行。一个语言解释器包括两个部分：

1. 解析：解析部分接受一个由字符序列表示的输入指令，然后将输入字符分解成一系列的词法单元
2. 执行： 程序内部的解释器根据语义规则进一步处理词法单元，进而执行原指令的实际运算。

这是流程图：

st=>start: 指令
op1=>operation: 解析器
op2=>operation: 词法单元
op3=>operation: 执行运算
e=>end: 结果

st->op1->op2->op3->e

3. 下面我们创建一个简单的解析器

使用tokenize模块。

import tokenize
from StringIO import StringIO

def parse(text):
    # 将text以StringIO的形式读入内存
    # 以字符串形式返回刀generate_tokens()函数中。
    tokens = tokenize.generate_tokens(StringIO(text).readline)
    # generate_tokens 生成器生成一个5元组：标记类型、标记字符串、标记开始位置二元组、标记结束位置二元组以及标记所在的行号
    # 下面大写的单词都属于token模块的常量
    for toknum, tokval, _, _, _ in tokens:
        if toknum == tokenize.NUMBER:
            yield int(tokval)
        elif toknum in [tokenize.OP, tokenize.STRING, tokenize.NAME]:
            yield int(tokval)
        elif tokun == tokenize.ENDMARKER:
            break
        else:
            raise RuntimeError("Unknown token %s: '%s'" % (tokenize.tok_name[toknum], tokval))

关于token常量，查看官方文档。

其中还有一个关键字 yield，它是用来定义生成器(Generator)，具体功能是可以当return 使用，从函数理返回一个值，不同之处是用yield 返回之后，可以让函数从上回yield 返回的地点继续执行。也就是说，yield 返回函数，交给调用者一个返回值，然后再移动回去，让函数继续运行下去，知道下一个yield语句再返回一个新的值。举个简单的例子：

>>> def test_yield():
...     yield 1
...     yield 2
...     yield (1,2)
...
>>> a = test_yield()
>>> a.next()
1
>>> a.next()
2
>>> a.next()
(1, 2)
>>> a.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
StopIteration

我们用生成器产生一个Fibonacci数列的函数就会更加直观：

def fab(max):
    a,b = 0,1
    while a < max:
        yield a
        a, b = b, a+b
 
>>> for i in fab(20):
...     print i,",",
...
0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 ,

4. 简单优化： 常量折叠

常量折叠是其中一种被很多现代编译器使用的编译器最优化技术。常量折叠是在编译时间简单化常量表达的一个过程。简单来说就是将常量表达式计算求值，并用求得的值来替换表达式，放入常量表。可以算作一种编译优化。

也就是我们最早举例子的时候说的，将2，3放入栈中，+ 进来的时候，2 3取出来进行运算，然后将运算结果放入栈中。

def constant_fold(code):
    while True:
        # 指令中找到两个连续的数字以及一个运算符
        for i, (a, b, op) in enumerate(zip(code, code[1:], code[2:])):
            if isinstance(a, int) and isinstance(b, int) and op in {"+", "-", "*", "/"}:
                m = Machine((a, b, op))
                m.run()
                code[i:i+3] = [m.top()]
                print("Constant-folded %s%s%s to %s" % (a, op, b, m.top()))
                break
        else:
            break
    return code

5. 读取-求值-输出循环

“读取-求值-输出”循环（英语：Read-Eval-Print Loop，简称REPL）是一个简单的，交互式的编程环境。这个词常常用于指代一个Lisp的交互式开发环境，但也能指代命令行的模式和例如APL、BASIC、Clojure、F#、Haskell、J、Julia、Perl、PHP、Prolog、Python、R、Ruby、Scala、Smalltalk、Standard ML、Tcl、Javascript这样的编程语言所拥有的类似的编程环境。这也被称做交互式顶层构件（interactive toplevel）。

read-eval-print loop
这个名字来自于以下几个Lisp用来实现这种机制的内置函数：

• 读入函数接收一个来自于用户的表达式，将其解析成数据结构并存入内存。例如，用户可能会输入一个s-表达式　(+ 1 2 3)，这句话会被解析成一个包含四个元素的链表。
• 求值函数　负责处理内部的数据结构并对其求值。在Lisp中，求一个以函数名开头的ｓ－表达式意味着对接下来的参数调用那个函数。所以函数"+"被在参数1 2 3上调用，产生结果6。
• 输出函数接受求值结果，并呈现将其给用户。尽管当前的结果“6”并不具有复杂的格式，但如果是一个较为复杂的表达式，那么它将会被精心处理，以便于更方便地被理解。

代码应当这样写：

def repl():
    print('Hit CTRL+D or type "exit" to quit.')

    while True:
        try:
            source = raw_input("> ")
            code = list(parse(source))
            code = constant_fold(code)
            Machine(code).run()
        except (RuntimeError, IndexError) as e:
            print("IndexError: %s" % e)
        except KeyboardInterrupt:
            print("\nKeyboardInterrupt")

再思考

这样，基本上的我们就完成了一个简单的解释器，实际上它的能力很弱小，但是作为一个锻炼思考的方式，是一个不错的实践。接下来，可以给这个解释器添加更多的功能。

另外，推荐几个其他的文章：
用 Python 从零开始写一个简单的解释器
一起来写个简单的解释器
如何使用Python编写一个Lisp解释器