对一个支持算术逻辑混合运算和短路的语言编译器的一点思考

三个多月没更新了。这个学期忙了不少东西,虽然结果如何还没见分晓。过往的五个学期不太理想的成绩直接让我在这个学期拼死拼活地争取保研名额。以上都是闲聊。

如标题所说,编译原理课程要求自己设计、编写出一个编译器。当然,具体支持的文法和功能并没有严格的规定。我自己写的编译器所支持的语言能够编译类似于C语言的算术和逻辑表达式。词法,句法分析还算顺利,也构建出了抽象语法树。然而,代码生成,尤其是针对支持逻辑运算短路、逻辑算术运算混合的表达式的语言生成代码,可能是一个细节非常繁杂的任务。

对于通常的算术和逻辑运算,它们多半是一些二元运算,比如算术的加减乘除运算,逻辑与,逻辑或,判断等于和不等的运算。比较特殊的是非运算,它是一元运算符。不过在观察过AST后,我们会发现它们都是依靠AST的Binop或Uniop(一元运算)节点实现——子节点的值给父节点,生成对应的运算代码。为了生成代码,我们可以选择对AST先序遍历,每个节点的运算结果压栈,然后父节点取出栈顶元素,生成父节点对应的二元运算的中间代码。这是一种简单有效的方案,可以很好地处理所有的二元和一元运算的代码生成问题。

问题在于——如何实现短路运算?考虑下面的算术逻辑混合表达式:

1
a = b + (0 > c + (e < 0 || f > 0));

在C语言中,逻辑运算和算术运算混合时,在语义上会有隐式的类型转换过程。算术运算结果参与逻辑运算时,非0为真,否则为假;逻辑运算参与算术运算时,真为1,假为0。加入了短路功能的代码不同在:逻辑运算的出口处需要把逻辑表达式真假的值赋予给一个临时变量,以方便外层(语法树高层)的算术运算的进行。在上式中有两个出口,一个是(e<0||f>0),还有一个是(0>c+(e<0||f>0))。我们观察到,这两项内部最后进行的是逻辑运算,外部最先参与的是算术运算。在内部进行的逻辑运算无需进行任何的二元逻辑运算,而应当使用条件跳转语句,根据不同的逻辑表达式值跳转到出口处的0或者1的位置。比如上面的代码可以翻译成如下的中间代码:

1
2
3
4
5
6
7
8
9
10
11
jlt,e,0,L1 // jump if less than
jgt,f,0,L1 // jump if greater than
=,0,,t1 // false exit
jmp,,,L2
L1: =,1,,t1 // true exit
L2: +,c,t1,t2
jgt,0,t2,L3
=,0,,t3 // false exit
jmp,,,L4
L3: =,1,,t3 // true exit
L4: +,b,t3,a

显然我们在遍历AST生成类似于上面的中间代码时,如果采用一趟式的代码生成,需要进行拉链-回填操作。为此我们需要维护AST各个节点的truelistfalselist属性,它们都是存储了需要跳转到真假出口的跳转语句的位置的列表。在一趟生成时,首先需要完成跳转代码的生成,目标跳转地址由于后续代码还未生成完,所以待填。在生成到指定的出口位置时,再将出口的行号或者标签回填至节点的truelistfalselist记录的跳转语句的位置。

这意味着,在生成中间代码时,需要识别逻辑运算出口的位置,在适当的时候生成逻辑运算的值存入临时变量中。所谓适当的时刻就是,逻辑运算的父节点如果是算术运算的话,需要生成出口代码。如果是连续的逻辑运算,只需要根据需要传递truelistfalselist属性即可。

相应的,如果一个变量没有参与任何逻辑运算,那么所有的真假出口跳转都是多余的,典型的例子有:a = (a && b) + c;。在这个例子中,由于ab参与了逻辑运算,所以需要产生通往真假出口的跳转语句,但是c只参与的算术运算,如何不生成跳转语句呢?一种方案是,检查该节点和父节点,仅当父节点是算术运算而本节点是逻辑运算时,则生成出口代码并回填行号。

上述的逻辑可以总结为:在遍历AST的节点时,检查该节点和父节点,如果父节点是算术运算而本节点是逻辑运算,则生成出口代码并回填行号;如果都是逻辑运算,那么传递列表属性即可;如果该节点是算术运算,那么直接生成算术运算代码即可。

对于a = b && c;中的bc,它们实际的行为等价于a == (b != 0) && (c != 0);中的对应的变量。在翻译时应当注意。

上面就是一点关于编写编译器生成代码的部分的思考。