一个解释器

在军训的闲暇写下这个文章。

几个星期前的时候,我突然想做一个Scheme 解释器,然后就去做了,尽管我《SICP》第二章还没仔细看完。在经过这辈子第一次天昏地暗的专心Coding 了以后,成品出来了。也是我第一次做出能拿得出手的东西。

但其实这东西技术含量不高,关键的代码只占用了编码时间的20% 剩下的时间都用来写配套的代码,重构和修改代码还有收拾自己的愚蠢Bug。

时间不多,简单说一下结构和核心代码。

repl.py 是对人的界面,用来获取输入的命令并且调用后面这些东西进行解析,也可以输入一个文件。


parser.py
顾名思义,将代码解析成词法树,然后转化成链表以便后续使用。关于链表以及其它解释器要用到的对象,都在 objects.py 中,里面的对象都是用非常Pythonic 的方法写的,也就是说这些对象能轻松的像一个Python 本来的数据类型一样使用,这里面对于迭代器的使用非常重要。

function.py
自然是内置的一些函数,但是注意的是,这些函数有两种形式,其中一种,参数在传入前并不进行求值(看过SICP 的应该知道,一般情况下传入参数,参数优先求值),在函数内部再进行选择性的求值,这样子就能确保诸如if 语句的选择性求值之类的了,在Scheme 中这类求值顺序特殊的函数叫做特殊形式

很容易可以看出来,(define (foobar x y) (...))(define foobar (lambda (x y) (...))) 的语法糖,在解释器中就是这样处理的。另外lambda 定义函数的时候支持了词法闭包,也就是说在lambda 生成一个函数的时候,lambda 会递归地搜索变量环境,如果有需要的变量直接和自己的环境绑定。

evaluator.py 是灵魂,其中有两个循环是求值器的灵魂,其中一个循环不断地将尾递归转化成迭代,也就是俗称的蹦跳床函数,另一个循环是不断归约函数体中的控制语句——比如说if 这种,这样归约到最后,就能将尾递归的函数交给上一个循环处理了。

这就是大致上这个解释器的骨干了,写这篇文章的目的之一就是为了避免以后维护的时候看不懂以前自己写得代码……虽然我觉得自己写得代码很容易理解。

一个解释器》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注