ShyaruIII

正如前文提到的,这篇是Shyaru语法翻译的实现部分。

不过,随着实现的深入,我越来越发现目前的设计并不是良构的。我期望的设计,应该能让扩展变得容易,而且理解起来也不难 —- 正如我一开始期待的那样。

但是,实践表明,目前的设计存在着一些问题,而且是在写这部分Syntax-Directed Translation的时候就存在。直接导致的结果就是,增加新语法并非随意,甚至有些扩展必须改动前面的代码才行 —- 很明显不符合我的期望。

总而言之,设计高于代码,这是我最近真正理解到的一件事实。毕竟,码代码是再简单不过的活计。

后面我会重构一版Shyaru —- 正如对待ShojoA那样。

不过如果您有兴趣,大概看看我走的坑也不错。

以下的内容均假设您有已经有了一个漂亮的文法分析器。

Shyaru的语法翻译的原理,其实只是对给定的AST(抽象语法树),进行eval求值。或者,加个限定条件:在给定的上下文中,对一个确定的AST进行eval求值。

那么,什么是确定的AST?(给定的上下文这个,恩,都懂的?)

确定的AST就是,当前处理的那一行语句直接翻译过来的AST。

所谓解释执行,当然就是对当前语句先翻译成AST,然后求值。当然,类似python这样不是特别准确,因为python实际有个编译的过程,所以你的文件夹下会有一个.pyc文件。

于是,一个很自然的推论是,实现两个函数。其中一个对单个AST求值,另外一个调用前者,来对多行或者一个文件进行求值。

这也是shyaru中sh_eval文件所展示的内容。

当然,为了满足第二个限定条件"给定的上下文",所以我另外写了一个interpreter函数,这个函数很简单: 1. 读入一个文件 2. 产生一个环境(这个就是所谓的全局作用域) 3. 扔给sh_eval_list去求值。

那么,最关键的函数就是对单个AST求值的那个。我叫它sh_eval。

先说说原有的设计。

sh_eval本身不做任何动作。考虑到对任意一个AST,叶子结点都是终结字符,父结点都是非终结字符。那么,自底而上,根据父节点的类型对该父结点的子结点进行求值。最终能执行完这棵树。

所以,sh_eval只需要做两件事。第一,取父结点。第二,调用对应父节点的eval方法,对子结点求值。

当然,如何取到对应的eval方法,有很多实现。通用的,对每个不同类型建模,构造类。或者是我一开始使用的,对不同的ast.id,比如 (name), (string),均去索引一个字典。该字典是动态生成的,其中包含需要用到的方法。这样的好处……好吧,我没想到什么好处,比如充满了hack?当然通篇全是函数也算一个好处?

其实不推荐非主流方法,用类比较好。不仅是方便调试,也方便阅读,还容易理清思路。如果您非要知道非主流的方法的话,shyaru的commit回退到40左右,应该能看到。当时已经完成了一个能对任意算式进行求值的东西,但是再往下拓展就很困难了。不过这个版本说到没用类好像也不对,我记得我用了一个Node来包装返回值。

ok,现在讨论另一个问题。我们知道,操作符一定是父结点(负号直接和数字合并放叶子结点),现在,如果这个操作符是+,1+1和'hello'+'world'执行的操作当然不一样,但是接口可都是唯一的+.eval()。借鉴一下python的思路,+操作实际上是去执行left结点的__add__操作,于是继续下放逻辑到叶子结点。

但是基于以上前提,我们发现了,现在所有的元素都必须是对象而不可能是立即数。原因是,比如1+2,由于eval操作实质调用了left的add,所以1这个元素,必然实现了__add__操作,所以它必然是对象。

但是这样everything is object的思路其实一部分也简化了思考,因为,立即数和对象相加还是很麻烦的。

这样的话,我们还能统一规定,对任意元素,eval方法必须实现。操作符的话,eval方法就是下放的逻辑,而number,string等,eval就是本身。

基于以上的讨论,我们能容易地实现一个对算式进行运算的解释器。

然后讨论name。

Shyaru对name的实现是值传递而不是引用传递,虽然这看起来很诡异我知道。

但是是有原因的。因为python屏蔽了对内存的直接操作,然后曲线救国的方案是用字典包一层,然后传字典的引用。但是我觉得这个更诡异了,所以干脆全部使用值传递。

name的含义就是在context下持有一个名称,这个名称我们叫变量名。另外这个名称索引一个值,这个值我们叫做变量的值……我觉得这解释挺多余的?

name的基本操作就是复制的时候,在当前的context中增加一个项目或者更改一个项目的值。其他时候,需要这个值就从context里面去取出来。

但是其实实现起来意外比较麻烦,因为涉及了另外一个问题,name的eval怎么处理。

回到前面,比如1+1,因为1实现了add方法,所以能调用成功然后计算。

但是如果是a+1呢?1+a呢?a上我会去实现一个add方法么?如果a在后面的赋值中类型发生了更改,比如变成了一个string,这个add还能用么?

这也就是为什么我对每个元素都去实现了eval。

name的eval操作是返回所储存的那个值。但是这也直接导致了,原本简单的操作,被重写成了这样(我用Add类来展示):

class Add(Base):
    def __init__(self):
        super(Add, self).__init__()

    def eval(self, env):
        result = self.left.eval(env).__add__(self.right.eval(env))
        return result

注意到eval操作,现在由于name的存在,所以需要各增加一次求值操作。毕竟您不会知道left或者right分别是什么。

其实这都算好,稍微看一下代码,您会发现很多地方都有isinstance(xx, Name)的判断。所以,最根本的影响,其实是name带来了不一致。另外一说,现在有个bug,name不可以被重赋值,原因正是赋值前的这次eval操作,导致左值变成了储存的那个值而不是name本身,于是赋值异常。这个bug现在我还没想好怎么改可以更漂亮些。

讨论完了上面那些,再来讨论if,while。

上面的代码不能用来支持if和while操作。原因是,以上的算式计算不是“有前提的”,或者说先验的。

说得清楚一些就是,如果我发现操作符是if,我会去计算if的codition,然后是block。而不是,直接对if eval。算式是没有这个逻辑的,直接算就好。

所以,还需要有flag去标明哪些表达式,或者说出现了哪些操作符,需要有和通常不一致的行为。

当然,只要有了这个标识符,基本上还是容易的,不过大概需要实现或者定义boolean?block的话,按需执行sh_eval_list也就行了。

这里说一下sh_eval_list。

def sh_eval_list(ast_list, env=None, args=None):
    if not type(ast_list) == list:
        ast_list = [ast_list]
    final_result = None
    if env is None:
        env = Environment()
    else:
        env = env.fork()
    if args is not None:
        for key in args:
            env.set(key, args[key])
    for ast in ast_list:
        final_result = sh_eval(ast, env)
        print "{}->{}".format(ast, final_result)
    env.delete()
    return final_result

sh_eval_list接受一个传入的env。我默认认为,传入的这个env是父环境,因为我需要sh_eval_list的环境是干净的,所以我fork出来一个子环境来容纳这个sh_eval_list的上下文。

sh_eval_list的另一个参数args是用来处理函数调用的,等会我会说。

剩下就是,sh_eval_list的返回值是最后一个sh_eval的返回值……我知道这有些不合理。sh_eval的返回值是对应的AST的求值结果,这倒是没什么问题。

sh_eval_list执行完毕,当前环境被弹出,恩,清理环境是个好习惯。

然后就是函数调用的实现。

这个比较恶心一点。函数调用有两部分,一部分是函数定义,另一部分才是函数调用。虽然不太难,但是您也思考一下实现如何?

当前Shyaru并不支持任意定义。也就是说,函数定义必须在那个函数调用的前面才行。python之所以行,是因为它的编译过程,这部分会把定义函数什么的,提前跑到env里面(我猜的)。

Shyaru的实现是这样,解析出来函数调用,以函数名为键,把参数和解析出来的block(这个block是一个AST的list)存在当前的环境里面。从这里可以看出,shyaru的函数不支持重载,如果要支持重载的话,大概用来索引的键就是函数名+参数长度吧。比如sum#2这样。

但是,函数定义里面,参数是形参,怎么处理计算呢?

我的解决思路是,把形参按照参数顺序,逐一把实参的值灌进去,然后在函数体执行之前,先把这部分参数灌入context中。

不好理解?

假设有这样一个函数

function sum(x,y){
    c = x + y;
}

调用的时候是sum(3,4)。在真正执行函数体之前,我把x=3,y=4灌入上下文这样就能找到了不是么。

另外说起来,shyaru并不支持return……当然并不是说我们不能把函数执行结果导出来了。还记得sh_eval的结果就是最后一行语句的计算结果么?所以,比如上面那个函数,最后也会返回c的值,也就是计算结果的。

就是这样,表达式计算,if,while,函数调用。真是一门无趣而又充满bug的语言(算么?)。

感谢阅读。

以上。