编译原理与实践：三地址代码详解

三地址代码最多包含3个地址，两个用来表示操作数，一个用来存放结果，具有如下的一般形式：

x:=y op z

其中，y和z表示名字、常数或编译时产生的临时变量，x表示名字或临时变量；op表示定点运算符、浮点运算符、逻辑运算符等各种运算符号，且每个语句的右边只能有一个运算符。

三地址代码可以看成是抽象语法树或DAG的一种线性表示，图6-10给出了图6-8中的抽象语法树和图6-9中的DAG所对应的三地址代码。

图6-9　a：=b*-c+b*-c的DAG

图6-10　三地址代码

其中，T1～T5为编译时产生的临时变量。在实际实现时，如果操作数为用户定义的名字，则用指向符号表中该名字入口的指针来代替操作数。

下面列出本书所使用的三地址语句的种类：

（1）赋值语句x：=y op z，其中，op为二元算术运算符或逻辑运算符。

（2）赋值语句x：=op y，其中，op为一元运算符，如一元减uminus、逻辑非not、移位运算符、转换运算符等。

（3）赋值语句x：=y。

（4）无条件转移语句goto L，其中，L标记下一条将被执行的三地址语句。

（5）条件转移语句if x relop y goto L或if a goto L。在第一种形式的语句中，relop代表关系运算符（如＜、==、＞等），若x和y满足关系relop，则执行标号为L的语句，否则继续按顺序执行；在第二种形式的语句中，a为布尔变量或常量，若a为真，则执行标号为L的语句，否则继续按顺序执行。

（6）索引赋值x：=y[i]和x[i]：=y。前者把地址y后第i个单元里的值赋给x，后者则把y的值赋给地址x后的第i个单元。

（7）地址和指针赋值x：=&y、x：=*y和*x：=y。前者把y的地址赋给x，即将y的左值赋给x的右值；中间的赋值语句是把y所指向的地址单元里存放的内容赋给x；后者则是把y的右值赋给x所指向对象的右值。

表6-6给出了使赋值语句生成三地址代码的S-属性文法(www.xing528.com)

表6-6　使赋值语句产生三地址代码的属性文法

其中，综合属性code表示三地址代码序列，E.place表示存放E值的名字，函数newtemp用来返回一个不同的临时变量名，如T1、T2等，而函数gen（x‘：=’y‘+’z）则用来生成三地址代码x：=y+z。在实际实现中，三地址代码序列往往是被存放在一个输出文件中，而不是赋给code属性。

三地址代码可看成是中间代码的一种抽象形式，一般有3种方式来表示三地址语句，分别是四元式、三元式以及间接三元式，这里仅对较为常用的四元式和三元式作一介绍。

1.四元式

一个四元式是具有四个域的记录结构，形如：其含义是：对arg1和arg2执行op指定的操作并将结果放到result中。其中，op代表运算符，arg1和arg2表示操作数，result是结果。例如，x：=y op z的四元式为（：=，y，z，x），x：=y的四元式为（：=，y，_，x），而if x relop y goto L的四元式则为（jrelop，x，y，L）。

（序号）（op，arg1，arg2，result）

再有，以赋值语句a：=b*-c+b*-c为例，其四元式如表6-7（a）所示，对应于图6-10（a）中的三地址代码。通常，四元式中的arg1、arg2和result的内容都是指针，该指针指向符导表中相关名字的入口。同样，临时变量名也要填入符号表。

表6-7　三地址语句的四元式和三元式表示

2.三元式

为了避免临时变量带来的时空开销，可以通过计算临时变量值的代码的位置来引用该临时变量，从而使得表示三地址代码的记录只需3个域，即op、arg1和arg2，这种表示方式称为三元式，形如：

（序号）（op，arg1，arg2）

其中，op代表运算符，arg1和arg2表示操作数，可以是用户定义的变量、常量或临时变量，也可以是指向三元式表中的某一个三元式的编号。

例如，赋值语句a：=b*-c+b*-c的三元式如表6-7（b）所示。表中括号内的数表示指向三元式表的某一项的指针，而指向符号表的指针则由名字本身来表示，如三元式（0）代表-c的运算结果，三元式（1）中的（0）指第0个三元式的结果，依此类推。若op为一元运算符，则arg1和arg2只需选用其一即可。

总而言之，四元式和三元式各具特点，四元式之间是通过临时变量联系起来的，而三元式之间则是通过三元式的编号联系起来的。显然，就优化而言，调整四元式的相对位置只需改变临时变量就能达到目的，而改动一张三元式表则意味着必须改变表中一系列的指示器的值，因此，对四元式进行优化要比三元式方便得多。