中间代码生成（Intermediate Code Generation）

本文主要是对 哈工大编译原理课件 的学习和总结。

在语法制导翻译过程中，将生成中间代码的代码（抽象语法树的代码）嵌入到语义动作中，即可完成中间代码（抽象语法树）的生成。

经典的中间代码通常包括以下几种：

• 树和有向无环图（DAG）：是比较 high level 的表示形式。例如抽象语法树。
• 三地址码（3-address code）：是比较 low level 的表示形式，接近目标机器代码。
• 控制流图（CFG）：是更精细的三地址码，程序的图状表示，图中的每个节点是一个基本快（BB），基本块内的代码是三地址码。适合做程序分析。
• 静态单赋值形式（SSA）：更精细的CFG，同时包含控制流和数据流的信息。可以简化程序分析算法。

本文将分别介绍各种类型的语句的翻译。

申明语句的翻译

介绍申明语句的翻译前，需要先了解下类型表达式。

类型表达式

首先，基本类型是类型表达式。例如：

• integer
• real
• char
• boolean
• type_error（出错类型）
• void（无类型）

再者，将类型构造符 (type constructor) 作用于类型表达式可以构成新的类型表达式。例如：

• 数组构造符array：若T是类型表达式,则array ( I, T )是类型表达式( I是一个整数)。

  类型	类型表达式
  int[3]	array(3, int)
  int[2][3]	array(2, array(3, int))

• 指针构造符pointer：若T 是类型表达式,则 pointer ( T ) 是类型表达式,它表示一个指针类型。
• 笛卡尔乘积构造符×：若T1 和T2 是类型表达式,则笛卡尔乘积 T1 × T2 是类型表达式。
• 函数构造符→：若T1 、T2 、…、Tn 和R是类型表达式，则 T1×T2×…×Tn → R 是类型表达式。
• 记录构造符record：若有标识符N1、N2 、…、Nn 与类型表达式T1、T2、…、Tn ，则 record ( (N1 × T1) × (N2 × T2)× …× ( Nn × Tn )) 是一个类型表达式。

例如，下面的C程序片段：

struct stype {
  char[8] name;
  int score;
};

stype[50] table;
stype* p;
1
2
3
4
5
6
7

• 和stype绑定的类型表达式：record((name×array(8, char)) × (score×integer))
• 和table绑定的类型表达式：array (50, stype)
• 和p绑定的类型表达式：pointer (stype)

申明式语句翻译

对于声明语句，语义分析的主要任务就是收集标识符的类型等属性信息，并为每一个名字分配一个相对地址：

• 从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度 (width)
• 在编译时刻，可以使用类型的宽度为每一个名字分配一个相对地址

而名字的类型和相对地址信息保存在相应的符号表记录中。

下面看一个变量申明语句的SDT：

对于上述文法，可以计算出有相同左部产生式的可选集：

可见，具有相同左部产生式的可选集是正交的，因此该文法是LL(1)文法，可以采用自顶向下的文法进行分析。分析过程如下：

简单赋值语句的翻译

赋值语句翻译的主要任务是生成对表达式求值的三地址码。例如：

x = ( a + b ) * c ;

// 翻译成三地址码
t1 = a + b
t2 = t1 * c
x  = t2
1
2
3
4
5
6

下面看一个简单赋值语句的翻译过程：

符号的属性为：

这个文法是LR文法，可以采用自底向上的LR语法分析方法。语义动作中函数说明如下：

• lookup(name)：查询符号表返回 name 对应的记录
• gen(code)：增量地生成三地址指令 code
• newtemp( )：生成一个新的临时变量t，返回 t 的地址

数组引用的翻译

将数组引用翻译成三地址码时要解决的主要问题是确定数组元素的存放地址，也就是数组元素的寻址。

• 一维数组。假设每个数组元素的宽度是 w，则数组元素 $a[i]$ 的相对地址是：$base+i\ast w$。其中，base是数组的基地址，i*w 是偏移地址
• 二维数组。假设一行的宽度是 w1，同一行中每个数组元素的宽度是w2，则数组元素 $a[i1][i2]$ 的相对地址是：$base+i_1\ast w_1+i_2\ast w_2$
• k维数组。数组元素$a[i_1][i_2]...[i_k]$的相对地址是：$base+i_1\ast w1+i_2\ast w_2+...+i_k\ast w_k$

例如：ype(a)= array(3, array(5, array(8, int) ) )，一个整型变量占用4个字节。则：
$$\begin{gathered} addr(a[i_1][i_2][i_3])=base+i_1\ast w_1+i_2\ast w_2+i_3\ast w_3 \\ =base+i_1\ast 160+i_2\ast 32+i_3\ast 4 \end{gathered}$$

$c=a[i_1][i_2][i_3]$ 对应的三地址码为：

t1 = i1 * 160;
t2 = i2 * 32;
t3 = t1 + t2;
t4 = i3 * 40;
t5 = t3 + t4;
t6 = a[t5]
c = t
1
2
3
4
5
6
7

为数组L定义综合属性如下：

• L.type：L生成的数组元素的类型
• L.offset：指示一个临时变量，该临时变量用于累加公式中的 $i_j\times w_j$ 项，从而计算数组引用的偏移量
• L.array：数组名在符号表的入口地址

控制流语句的翻译

控制流语句及其SDT

控制流语句的基本文法：

P → S S → S 1 S 2 S → i d = E ;             ∣   L = E ; S → i f   B   t h e n   S 1             ∣   i f   B   t h e n   S 1   e l s e   S 2             ∣   w h i l e   B   d o   S 1

​P→SS→S1​S2​S→id=E;           ∣ L=E;S→if B then S1​           ∣ if B then S1​ else S2​           ∣ while B do S1​​

控制流语句的代码结构：

很容易得到控制流语句的SDT：

布尔表达式及其SDT

布尔表达式的基本文法：

B → B   o r   B         ∣   B   a n d   B         ∣   n o t   B         ∣   ( B )         ∣   E   r e l o p   E         ∣   t r u e         ∣   f a l s e

​B→B or B       ∣ B and B       ∣ not B       ∣ (B)       ∣ E relop E       ∣ true       ∣ false​

其中，relop（关系运算符）分别为 <、 <=、 >、 >=、==、 ! = 。

在跳转代码中，逻辑运算符 &&、|| 和 ! 被翻译成跳转指令。运算符本身不出现在代码中，布尔表达式的值是通过代码序列中的位置来表示的。例如：

// C 源码
if (x<100 || x>200 && x!=y)
  x = 0;

// 三地址代码：
	if x<100 goto L2;
	goto L3;
L3: if x>200 goto L4;
    goto L1;
L4: if x != y goto L2;
    goto L1;
L2: x = 0;
L1:  
1
2
3
4
5
6
7
8
9
10
11
12
13

则比较容易得出布尔表达式的SDT：

控制流语句翻译的例子

任何SDT都可以这样实现：首先建立一棵语法分析树（比如使用LR语法分析构建），然后按照从左到右的深度优先顺序来执行这些动作。

布尔表达式和控制流表达式的回填

上面在生成跳转指令的时候，目标指令的标号还不确定，是通过将存放标号的地址作为继承属性传递到跳转指令生成的地方，这样做会增加一趟处理：将标号同具体的地址绑定起来。

这里介绍一种称为回填的技术来解决这个问题。它的基本思想为：生成一个跳转指令时，暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令具有相同的目标标号。等到能够确定正确的目标标号时,才去填充这些指令的目标标号。

增加非终结符B的综合属性：

• B.truelist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号
• B.falselist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号

使用到的函数：

• makelist( i )：创建一个只包含i的列表,i是跳转指令的标号，函数返回指向新创建的列表的指针
• merge( p1 , p2 )：将 p1 和 p2 指向的列表进行合并，返回指向合并后的列表的指针
• backpatch( p, i )：将 i 作为目标标号插入到 p 所指列表中的各指令中

布尔表达式的回填：

$B\to E_{1}relop{E}_2$，对应的语义动作为：

{
	B.truelist = makelist(nextquad);
	B.falselist = makelist(nextquad+1);
	gen(‘if ’ E 1 .addr relop E 2 .addr ‘goto _’);
	gen(‘goto _’);
}
1
2
3
4
5
6

$B\to true$，对应的语义动作为：

{
	B.truelist = makelist(nextquad);
	gen(‘goto _’);
}
1
2
3
4

$B\to false$，对应的语义动作为：

{
	B.falselist = makelist(nextquad);
	gen(‘goto _’);
}
1
2
3
4

$B\to (B_1)$，对应的语义动作为：

{
	B.truelist = B1.truelist ;
	B.falselist = B1.falselist ;
}
1
2
3
4

$B\to not{B}_1$，对应的语义动作为：

{
	B.truelist = B1.falselist ;
	B.falselist = B1.truelist ;
}
1
2
3
4

$B\to B_{1}or{B}_2$，需要转换为$B\to B_{1}orM{B}_2$。标记终结符M的任务是用于记录B2第一条指令的标号。类似地，$B\to B_{1}and{B}_2$，需要转换为$B\to B_{1}andM{B}_2$。

下面看一个例子：

注：1、假设指令从100号开始执行。2、生成的指令中剩余标号待B的真假出口确定即可回填。

控制流语句的回填：

为控制语句增添综合属性：

• S.next1ist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是按照运行顺序紧跟在S代码之后的指令的标号

$S\to ifBthen{S}_1$ 语句和 $S\to ifBthen{S}_{1}else{S}_2$ 语句的SDT：

$S\to whileBdo{S}_1$ 语句和 $S\to S_1{S}_2$ 语句的SDT：

例：

while a < b do
  if c < 5 then
    while x > y do z = x + 1;
  else
    x = y;
1
2
3
4
5

switch语句的翻译

过程调用语句的翻译

过程调用语句的文法：

S → c a l l   i d   ( E l i s t ) E l i s t → E l i s t , E E l i s t → E

​S→call id (Elist)Elist→Elist,EElist→E​

过程调用语句的SDT：

用一个队列 q 存放 E1.addr、E2.addr、…、En.addr。

例：

// 源码
f ( b*c-1, x+y, x, y )

// 对应的三地址代码
t1 = b*c;
t2 = t1 - 1;
t3 = x + y;
param t2
param t3
param x
param y
call f, 4
1
2
3
4
5
6
7
8
9
10
11
12

参考

• 哈工大编译原理课件