大神用Python编写虚拟机解释器

群内不定时分享干货,包括最新的python企业案例学习资料和零基础入门教程,欢迎初学和进阶中的小伙伴入群学习交流

环境介绍

环境采用带桌面的Ubuntu Linux环境,

LX终端(LXTerminal):Linux命令行终端,打开后会进入Bash环境,可以使用Linux命令

GVim:非常好用的编辑器,最简单的用法可以参考课程Vim编辑器

环境使用

众所周知,python语言作为一门超级人性化的语言越来越被受到重视。虚拟服务同样受到人们的重视,那么本次项目的目的就是让大家学会使用python制作一个虚拟解释器,这里的虚拟解释器指的是一定意义上的堆栈机。

构建堆栈机

堆栈机本身并不拥有寄存器,它的执行原理非常简单:将需要处理的值放入栈中,然后执行它们。尽管堆栈机的原理就是这么简单,但是不能不说它确实很强大,不然Python、Java等高级语言也不会将它作为它们的虚拟机。

无论如何,先来深入了解一下堆栈的原理。首先,我们需要一个指令指针栈,它能够储存返回地址。这个返回地址是当我们执行一个子例程(比如函数)的时候,需要用它跳回到开始调用该函数的地方。

那么有了这个神奇的堆栈,很多复杂难以理解的程序就变得非常简单。比如说,有这么一个数学表达式:(2+3)*4。在堆栈机中,这个数学表达式等价于2 3 + 4 * ——将'2'和'3'依次推入栈中,接下来要推入的指令是'+',将前面两个数字弹出,令他们执行加法运算后再将它们的和入栈。然后依次将'2'与'3'的和与4相乘的结果推入栈中。运算结束,so easy!

那么,让我们开始建立一个栈,由于Python这个语言拥有类似于C语言中数据结构的一个类collections.deque,因此可以在这个类的基础上定义出属于我们的栈。

from collections import deque

class Stack(deque):

push = deque.append

def top(self):

return self[-1

那么这里面既然定义了'push'、'top'方法,为什么没有定义'pop'?因为'deque'这个类本身就拥有方法'pop',除了'pop'还有'popleft'呢,有兴趣的同学可以研究一下这个类与'list'对象的区别和联系。

接下来,让我们建立一个虚拟机类——'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

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)

上面的代码非常浅显易懂,就是当输入一段指令,该函数就会根据这段指令在'dispatch_map'字典中找到对应的方法,比如:符号'*'对应的是'self.mul'函数。以上过程就类似于'Forth'语言的构建过程。

当输入指令'*',程序就会执行函数'self.mul',所以我们还需要定义对应的函数:

def mul(self):

self.push(self.pop() * self.pop())

其他的函数定义也是依次类推,根据它们的功能和名称定义不同的函数。

到这里,你可以定义你想要的函数了,一个虚拟机环境基本构成就是这样!

然而并没有完,环境搭建好了,最重要的'解释'还没有完成,一个语言解释器包括两部分:

解析:解析部分接受一个由字符序列表示的输入指令,然后将输入字符分解成一系列的词法单元

执行:程序内部的解释器根据语义规则进一步处理词法单元,进而执行原指令的实际运算。

为我们的指令创建一个简单的解析器

让我们使用'tokenize'模块为输入的指令构建一个解析器吧~

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

这个方法唯一的缺点是我们必须得更新跳转的地址,尤其是在遇到读取或者跳转等操作时需要不断的跳转。但是任何问题都有它对应解决的方案,有一个简单的例子就是在跳转的时候只允许调到指令的命名标签上,这样的话,在执行常量折叠之后就可以跳转到它们真正的地址上。

读取-求值-输出循环

我们可以通过以下代码实现一个简单的“读取-求值-输出循环”的交互式编程环境:

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(" KeyboardInterrupt")

源码小编不知道怎么上传到这个上面,截图也有点长,所以我就放到群里了

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20171230A0SJDJ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券