鸿 网 互 联 www.68idc.cn

针对解释器的优化——语法分析与执行分离

来源:互联网 作者:佚名 时间:2015-10-09 05:53
此内容出现在SICP4.1.7节,主要目的是 优化 解释 器,提升效率。书中所采取了类于编译技术的 优化 方式。 主要 优化 思想可以如下简单表述: 首先我们使用A语言写出了B语言的 解释 器。对于B语言的 解释 器,你所输入的B语言代码将会被逐步分解为B语言中的元

此内容出现在SICP4.1.7节,主要目的是优化解释器,提升效率。书中所采取了类似于编译技术的优化方式。

        主要优化思想可以如下简单表述:

        首先我们使用A语言写出了B语言的解释器。对于B语言的解释器,你所输入的B语言代码将会被逐步分解为B语言中的元操作,原操作被求值后通过树形积累向上求值,直到得到表达式的值。优化方式是,将B语言表达式转换为对应A语言表达式,求值时直接执行A语言代码。如果我们将A语言变成汇编语言,那么整个过程就是编译了。书中所描述的优化是将我们自己所写的Lisp求值器对应的表达式,转换为本地Lisp(即上面所指的A语言)的函数调用。

        那么,到底优化后的解释器比优化前的解释器效率高在什么地方呢?书中虽也有说明,但是并未着墨太多。在这篇文章当中我力求清楚表述。

        先放上一张树的图片。


        为了要优化解释器,我们首先需要清楚原始解释器的执行过程,同时发现不足之处。

        对于优化前的解释器,每次输入新的表达式时,都会分析分解该表达式,并根据分析结果来求出此表达式的值。整个过程可以看成生成一棵由上到下的语法分析树,每一个表达式都会被分解成更小的表达式,直至不能变成不能再分的叶子节点,接着会对这些叶子节点求值,然后向上回溯,直到根节点,从而得到整个表达式的值。严格地说,此棵语法分析树,是以后序遍历的顺序生成,并且每一个分支下到最低点的时候,都会完成对分支的求值。最后,通过解释器,我们得到了表达式的值。但是整棵语法分析树的建立过程已经被抛弃。后面如果调用同一表达式,会经历和之前同样的过程。

        那么,是什么问题导致了解释器的效率下降呢?

        答案是语法分析树的建立过程被抛弃。我们以函数调用作为最主要的例子。假设我们定义了一个函数f,它接受一个参数x。当我们连续调用(f 1),(f 2),(f 3)时会发现,连续三次的调用要求每次都必须对f进行一次重新的分析与求值。当我们把f调用所产生的语法分析树画出来的时候就会恍然大悟,它们几乎完全相同,唯一不同之处仅仅在于传入的实际参数值。倘若我们能够只分析一次f,并且将这棵语法分析树以某种特定的方式保存,传入不同的数据时它会按照语法分析树所指定的顺序进行求值,那么将会节省生成语法分析树的时间

       优化解释器,其实做了这么一件事情。它发现,对于同一个表达式,每次生成的语法分析树都是一样的,只是数据会偶尔改变。或者说原操作的执行序列是一样的,而每一个原操作又对应着特定的父语言语句(实现解释器的语言),我们如果能够用一种特定的形式保存原操作执行序列,每次赋予一个值的时候就会启动执行序列,得到表达式的值。那么,我们就将求值过程分成这样的两个步骤:生成树的步骤和树形求值的步骤。优化后,我们只需要一次分析,就可以进行多次求值。比如对于函数f来说,每一次调用不用再对f进行分析,因为此时f已经分析好并且被表达为相应的指令序列,我们参数时,便会启动序列求值。这个指令序列即对应原操作执行序列。

所以说,效率提升之处在于大大减少了不必要的语法分析树重复生成的问题。      

       现在,我们已经有一个初步的概念,那我们具体的实现方式又是怎么样的呢?

       书上的实现方式,是通过analyze将所有表达式转换为父语言的函数。当传入env时,启动函数调用,求得表达式值。analyze将返回成为执行过程的函数,形式为(lamda (env) <body>),即接受env参数的函数。这里值得一提的是关于analyze-sequence的实现,书中采用的方式为不断的嵌套函数调用。这样的方式固然可行,但是实现起来并不太方便,我在这里采取了循环来替代嵌套。在此处我们只需要把握一个原则:analyze所生成的是父语言中的函数,此函数接受env之后会产生与未优化解释器同样的值。analyze所完成的工作是将表达式转换为父语言的函数调用,并且和定义变量的操作相结合可以储存此序列,也就是一棵已经分析好,等待传入数据的语法分析树。

       我这里放一份源码,大家有兴趣可以参考。点击这里   

       后面我会在建立好自己的汇编语言的基础上,完成真正的编译器。

网友评论
<