CPCC 抽象语法树的三地址码生成

龙源期刊网

CPCC 抽象语法树的三地址码生成

作者：刘奔 王亚刚 韩俊刚

来源：《电脑知识与技术》2013年第34期

摘要：为了便于代码优化及指令生成，在并行C语言编译器CPCC（Concordia Parallel C

Compiler）将源程序的抽象语法树（Abstract Syntax Tree， AST）转换成目标机PAAG

（Parallel Array Architecture GPU）处理器的汇编代码时，采用了三地址码作为中间表示形式。

基于CPCC AST的结构特点，将AST到三地址码的转换分为三类，即一般表达式的翻译、布

尔表达式的翻译以及语句的翻译，并给出了其详细设计思路及是实现方法。实验结果表明，该

方案实现了从源码的抽象语法树到三地址码的转换。

关键词：编译器；中间表示；抽象语法树；三地址码

中图分类号：TN911 文献标识码：A 文章编号：1009-3044（2013）34-7753-06

PAAG（Parallel Array Architecture GPU）是西安邮电大学自主开发的高性能图形、图像处

理器[1]。为了给PAAG处理器实现并行C语言编译系统，采用移植已有的并行C语言编译器

CPCC[2]的方法。CPCC产生的是针对堆栈机器的伪代码（其作用相当于目标机器的汇编

码），堆栈机代码是一种单地址码[3]，但目标处理器PAAG的汇编指令是三地址形式。为了

将CPCC移植到目标机PAAG上，我们以CPCC编译产生源代码的AST形式为基础，将其转

换为PAAG的汇编码。首先将AST转换成一种更接近PAAG汇编码的线性中间表示形式——

三地址码，再经过代码生成模块实现从三地址码到汇编码的转换。三地址码不仅在形式上与目

标机器的汇编指令集更加接近，从三地址码生成汇编码要更容易些；更重要的是，目前有很多

成熟的与机器无关的编译优化技术都是在程序的三地址码这种线性中间表示形式上来处理的

[4]，在生成三地址码后，可以利用这些技术进行与机器无关的优化，以生成更加紧凑高效的

代码，这对于提高编译器的性能是非常有意义的。

本文一共分为四个部分，第一部分和第二部分分别介绍CPCC的中间表示—AST和所要翻

译成的三地址码及其格式；第三部分介绍从AST到三地址码的翻译；第四部分是实验结论。

1 CPCC的AST

抽象语法树（Abstract Syntax Tree，AST）是对被编译源程序语法分析的图表示[5]。CPCC

的AST由4类节点构成，分别是SYMBOL、LINK、VALUE和STMT节点。其中SYMBOL

节点用来描述源程序中声明部分出现的标识符；以VALUE节点为根的子树描述源程序中对应

的表达式，通常它可以求得一个值；LINK节点用来描述SYMBOL节点以及VALUE节点的类

型；以STMT节点为根的子树表示源程序中出现的由各种表达式按照某种语法规则组成的语

句，如各种控制流语句（if_else等）。各个节点连接起来形成的AST实现对源程序的语法描

述。

龙源期刊网

2 三地址码

三地址码包含一个操作符，两个源操作数跟一个目的操作数。目的操作数用来存放源操作

数经过操作符对应操作处理后生成的结果，或者对于转移操作，目的操作数代表要转移的目的

地址。三地址码中源操作数的数目可以小于两个[3-6]。所谓“地址”就是三地址码的操作数，它

可以是源码中变量的名字；可以是一个整型常量；也可以是一个带下标的t，如t3。这些t表

示由编译器计算产生的临时变量。

在本文出现的三地址码主要有以下形式：

3 AST到三地址码的翻译

CPCC的AST将C程序分为两种语法范畴：表达式（对应AST中以VALUE节点为根的

子树）以及由表达式组成的语句（对应AST中以STMT节点为根的子树）。因此我们很自然

的将程序的翻译分为两类：表达式的翻译和语句的翻译。但是，当表达式作为决定程序流向的

判断条件时，如在关键词while后充当判断循环结束的条件，其作用只是实现程序的跳转，此

时它的翻译又不同于在其它地方的处理，这类通过判断真假来控制程序流向的表达式称为布尔

表达式。因此我们将表达式的翻译又分为一般表达式的翻译和布尔表达式的翻译。下面将分别

阐述对一般表达式、布尔表达式和语句等三类翻译的设计方案。

3.1一般表达式的翻译

一般表达式能够计算出一个值，对表达式的翻译应该完成两个功能：1生成表示该表达式

语义动作的三地址码；2返回表达式的计算结果，该结果可能被用于更高一层表达式的运算。

这种处理由int spit_expr（VALUE *v， int rlv）函数完成。参数VALUE类型指针v代表要处

理的表达式；参数rlv表示表达式是被当做左值还是右值处理的。spit_expr（）函数的流程图

如图1所示（图中v→code代表表达式的类型，逗号表达式中相邻两个子表达式对应的

VALUE节点用next指针相连）。

一般表达式中最难翻译的是数组引用的翻译，在此我们以数组引用的翻译来说明处理的方

法。要访问（引用）某个数组元素，就要确定该元素的地址。如何由AST来获得数组的起始

地址和偏移量，进而计算出该元素的绝对地址是问题的关键。首先来看数组引用在CPCC中的

AST表示，以三维数组为例说明。已知整型数组a[2][2][3]和表达式b = a[1][0][2]，该表达式在

CPCC中的AST如图2所示。

图中V_ARRAY_ACCESS类型节点的size字段记录该维上一个单位的大小是数组类型大

小的倍数。如图中跟a相连的V_ARRAY_ACCESS节点的size值是6，表示该层上一个单位的

大小等于6个整型的大小。expr2指针对应的VALUE节点的值与size之积表示该维上地址的

偏移量，因6*1+3*0+1*2即为总的偏移量，总偏移量乘以数组类型对应的字节数就是偏移量的

字节数。其中数组类型的字节数由连接最上层V_ARRAY_ACCESS节点的LINK节点的

龙源期刊网

字段得出。数组引用的绝对地址即为数组基地址（此处为数组名a）与总偏移量字

节数之和。图3为数组引用翻译出的三地址码。

3.2布尔表达式的翻译

在CPCC中布尔表达式的形式化描述为：

产生跳转三地址码时还不能确定要跳转到哪里，翻译时需要先记录下这两条跳转三地址

码，当生成跳转目的对应的程序段时，将该程序段第一条三地址码的索引号（生成的三地址码

是从零号地址开始顺序存放的）回填（Backpatch）至跳转三地址码要跳转的目的操作数中

去。从布尔表达式的形式化描述可以看出布尔表达式是可以递归定义的，如B → B1‖B2，因

此在一个复合布尔表达式中会存在多条跳转三地址码跳转到同一目的地址的情况。为了一次回

填多条具有相同目的地址的跳转三地址码，将返回值设计为含有两个链表的结构体[7]。返回

值的结构体定义为：

结构体中data字段记录跳转三地址码的索引号。假设当整个复合布尔表达式为假时，将要

执行程序的第一条三地址码序号为F；为真时，将要执行的第一条三地址码的序号为T。那么

falselist指向的链表记录了复合表达式对应三地址码中所有跳转到F的三地址码的索引号；同

理truelist指向的链表记录了所有跳转到T的三地址码的索引号。例如B = B1‖ B2 && B3的翻

译如图4所示，其中B1，B2，B3都为E rel E形式。

3.3语句的翻译

语句的翻译与布尔表达式的翻译是不可分割的，下面是CPCC中几种语句的形式化定义：

其中S为语句，B为布尔表达式，E为表达式，定义中允许语句的嵌套。

常见的分支和循环语句翻译产生三地址码的结构举例如图6所示：（for，while，if-

else）。

图（a）中从代码块的“真”出发的箭头指向代码块S1表示当布尔表达式B为真

时，程序将执行S1的第一条三地址码。同理，从“假”出发和break_list合并的箭头指向整个

for循环之后，表示当B为假时，或遇到break语句时程序跳出循环。其中break_list表示S1中

所有break语句对应跳转代码组成的链表；continue_list跟s1_nextlist发出的箭头指向

代码段表示在执行完s1或者遇到continue语句时，程序将执行E2的第一条三地址码。类似

break_list，continue_list是continue语句对应跳转代码组成的链表；goto连接的箭头表示程序

要跳转到测试条件处。图（b）图（c）的解释类似。

语句的翻译是由Link *trace_stmt（STMT *s）函数来完成的。参数为指向STMT结构体的

指针，由于不同类型的语句本身就是程序中各种控制流的抽象表示（如C_IF_ELSE类型语句

是S→if （B） S1 else S2分支结构的表示），由语句翻译出的程序也会出现跳转三地址码（以

龙源期刊网

下简称跳转代码）。处理所有跳转代码的方法都是统一的：生成该跳转代码时先用链表记录下

它的索引号，待到跳转目的对应的第一条三地址码生成前，用next_index（表示三地址码索引

号的全局静态变量，每生成一条三地址码后其值加一）来回填对应的跳转代码。

注意，S生成的一部分跳转代码的跳转目的在S内部，此种情况下，一旦生成跳转目的程

序段，便用其第一条三地址码的索引号回填对应它的跳转代码；另一部分跳转代码的跳转目的

在整个S语句之后，包括由S中包含的break语句生成的跳转代码，这时将所有以S语句后第

一条三地址码为跳转目的的跳转代码构成一条Link型的链表，称该链表为s_nextlist，作为

trace_stmt（）函数的返回值。若S的s_nextlist不为空，且S之后仍有未处理的语句。在处理

S的后继语句前，用next_index回填链表s_nextlist。trace_stmt（）函数的整体流程如图7所

示。

跟其他分支循环语句不同，switch语句的翻译要更加复杂些，下面来单独分析switch语句

的翻译过程。图8为例程中方框中程序对应的AST。

下面是针对图8中例程和AST对switch语句翻译的阐述：

扫描到SWITCH节点时，处理switch后的表达式a。接着产生一条无条件跳转代码用于跳

转到test_table处（该跳转代码的索引为1，记录在jump2table_list中，该跳转代码在产生

test_table时被回填），test_table对应的代码用于测试应该执行哪个case分支。

遇到case 0：对应的节点，先将常量0压入队列case_queue，再将下一条三地址码的索引

号（例子中为2）压入case_queue中，接着为表达式b=0生成三地址码，之后的break语句产

生一条无条件跳转代码，建立break_list链表记录下它的索引号（为3）。break_list记录所有

跳出switch结构的跳转代码。之后处理下面case 1：b=0；break；与上面过程完全相同，即常

量1及下一条代码的索引号4进入队列case_queue中。break_list记录索引号为5的无条件跳转

代码，对应该case后的break语句。然后处理default对应的语句：先用default_index记录下一

条代码的索引（为6），即default对应的第一条代码。再为default后的表达式b=-1生成三地

址码，最后产生一条无条件跳转代码（索引号为8），将其记录在break_list中。

此后，生成test_table代码段：先将第一条代码的索引号回填到jump2tabel_list里记录的跳

转代码中。接着从队列case_queue拿出两个元素0和2，产生一条条件跳转指令2 = a if = =

goto 0 ，之后又从case_queue读出两个值1和4，产生4 = a if == goto 1，此时case_queue为

空，读default_index，产生6 = goto。test_table生成完毕。

最后用下一条代码索引号（为12）来回填break_list链表中的跳转代码。

图9是例程中用到的队列以及链表等数据结构和对switch结构翻译的结果：

4 实验结论

龙源期刊网

以C语言源程序对应的三地址码为基础，结合PAAG处理器的指令集，很容易实现编译

器代码生成模块。至此，整套C语言编

译系统已经完成了从C语言源程序到PAAG汇编程序的转换。整个编译系统对输入的图

形算法生成的汇编文件，经过在PAAG仿真环境下的调试和运行后，结果正确。证明从AST

到三地址码的转换是正确的。

参考文献：

[1] 李涛，肖灵芝.面向图形和图像处理器的轻核阵列机结构[J].西安邮电学院学报，2012，

17（3）：41-45.

[2] Ai dia Parallel C：Design and Implementation[D].Montréal，Québec，

Canada：The Department of Computer Science，Concordia University，2000：43-70.

[3] Keith ，Linda ering a Compiler [M].2end Kaufmann

Publishers Inc，2007.

[4] Alfred ， Monica ，Ravi Sethi，Jeffrey . Compilers Principles，

Techniques，and Tools[M]. 2end ed. Addison-Wesley，2008.

[5] 陈火旺，刘春林.程序设计语言编译原理[M].北京：国防工业出版社，2000.

[6] 张艳红，康月兵. LS MPP编译系统中间代码的设计与实现[J].计算机应用， 2002， 22

（8）：77-79.

[7] 琚小明.面向媒体处理器可重定目标编译器的设计研究[D].杭州：浙江大学信息科学与

工程学院，2004：25-50.