用Python 写一个虚拟解释器

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

所谓虚拟机器,就是一定意义上的堆栈机。
解释器能够执行其他计算机语言编写的程序的系统软件,他是一个翻译程序。它的执行方式是一边翻译一边执行,因此其执行效率一般比较低。解释器的实现比较简单,而且编写源程序的高级语言可以使用更加灵活和富于表现力的语法。
可参考本链接,开源项目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中,求一个以函数名开头的s-表达式意味着对接下来的参数调用那个函数。所以函数"+"被在参数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解释器

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,098评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,213评论 2 380
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,960评论 0 336
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,519评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,512评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,533评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,914评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,574评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,804评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,563评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,644评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,350评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,933评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,908评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,146评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,847评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,361评论 2 342

推荐阅读更多精彩内容

  • 编程派微信号:codingpy 本文约有 15000 字,读完可能需要 20 分钟。原文地址: 500lines。...
    罗义的夏天阅读 65,006评论 0 22
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,580评论 18 139
  • TITLE: 编程语言乱炖 码农最大的烦恼——编程语言太多。不是我不学习,这世界变化快! 有时候还是蛮怀念十几、二...
    码园老农阅读 5,286评论 2 35
  • 1、IP包头 在TCP/IP四层模型的最后,介绍了数据的封装与解封装过程,其中在数据封装进行到网络层时,提到在此时...
    黒猫阅读 1,675评论 0 10
  • 每天一小步,看得见的进步。 欢迎来到《漫画破词》。 这次要和各位聊聊relationship这个词汇。 21世纪,...
    Jack的英语世界阅读 180评论 0 0