第六章 中间代码生成

值语句S生成三地址代码。属性S.code和E.code分别表示S和E对应的三地址代码。属性E.addr则表示被用于存放E的值的地址。回顾6.2.1节，一个地址可以是变量名字、常量或编译器产生的临时量。

PRODUCTION SEMANTIC RULES 产生式 语义规则 图6.19 表达式的三地址代码

考虑图6.19中语法制导定义的最后一个产生式E→id。若表达式只是单个的标识符，比如说x，那么x本身就保存了这个表达式的值。这个产生式对应的语义规则把E.addr定义位为指向该id的实例对应的符号表条目的指针。令top表示当前的符号表。当函数top.get被做用于id的这个实例的字符串表示id.lexeme时，它返回对应的符号表条目。E.code被设置为空串。

当规则为E→(E1)时，对E的翻译等同于对子表达式E1的翻译。因此，E.addr等于E1.addr，E.code等于E1.code。

图6.19中运算符+和单目-是典型语言中的运算符的代表。E→E1+E2的语义规则生成了根据E1和E2的值计算E的值的代码。计算得到的值被存放在新生成的临时变量中。如果E1的值计算后被放入E1.addr，E2的值被放到E2.addr中，那么E1+E2就可以被翻译为t=E1.addr+E2.addr，其中t是一个临时变量。E.addr被设为t。连续执行new Temp( )会产生一系列互不相同的临时变量t1，t2….。

为方便起见，我们使用记号gen（x ?=? y ?+? z）来表示三地址指令x=y+z。当被传递给gen时，变量x、y、z的位置上出现的表达式将首先被求值，而象‘=’这样的引号内的字符串则按照字面直接生成6。其它的三地址指令的生成方法类似，也是将gen作用于表达式和字符串的组合。

当我们翻译产生式E→E1+E2时，图6.19中的语义规则首先将E1.code和E2.code联接起来，然后再加上一条将E1和E2的值相加的指令，从而生成E.code。新增加的这条指令将求和的结果放入一个为E生成的临时变量中，用E.addr表示。

产生式E→-E1的翻译类似。这个规则首先为E创建一个新的临时变量，并生成一条指令来执行单目-操作。

最终，产生式S→id = E;所生成的指令将表达式E的值赋给标识符id。和规则E?id中一样，这个产生式的语义规则使用函数top.get来确定id所代表的标识符的地址。S.code包含的代码首先计算E的值并将其保存到由E.addr指定的地址中，然后再将这个值赋给这个id实例的地址top.get(id.lexeme)。

例子6.11：图6.19中的语法制导定义将赋值语句a=b+-c;翻译成如下的三地址代码序列 6

在语法制导定义中，gen构造出一条指令并返回它。在翻译方案中，gen构造出一条指令，并增量地将它添加到指令流中去。

t1=minus c t2=b+t1 a=t2 □

6.4.2 增量翻译

code属性可能是很长的字符串，因此就像5.5.2中讨论的那样，它们通常是用增量的方式生成的。因此，我们不会象图6.19中那样构造E.code，我们可以设法象图6.20中那样只生成新的三地址代码。在这个增量方式中，gen不仅要构造出一个新的三地址指令，还要将它添加到至今为止已生成的三地址指令序列之后。指令序列可能暂时放在内存中进一步处理，也可能增量地输出。

图6.20中的翻译方案和图6.19中的语法制导定义产生相同的代码。采用增量方式时不需再用到code属性，因为对gen的连续调用将生成一个指令序列。例如，图6.20中对应于E→E1+E2的语义规则直接调用gen产生一条加法指令；在此之前，翻译方案已经生成了计算E1的值并放入E1.addr、计算E2并放入E2.addr的指令序列。

图6.20的方法同样可以被用来构造语法树，对应于E→E1+E2的语义规则使用构造算子生成新的结点。规则如下：

E→E1+E2 {E.addr = new Node(?+?, E1.addr, E2.addr); }

这里，属性addr表示的是一个结点的地址，而不是某个变量或常量。

图6.20 增量生成表达式的三地址代码

6.4.3 数组元素的寻址

将数组元素存储在一块连续的存储空间里就可以快速地访问它们。在C和Java中，一个具有n个元素的数组中的元素是按照0，1，…，n-1编号的。假设每个数组元素的宽度是w，那么数组A的第i个元素的开始地址为 base+i×w (6.2) 其中base是分配给数组A的内存块的相对地址。就是说，base是A[0]的相对地址。

公式（6.2）可以被泛化到2维或多维数组上。对于2维数组，我们在C和Java中用A[i1][i2]来表示第i1行的第i2个元素。假设一行的宽度是w1，同一行中每个元素的宽度是w2。A[i1][i2]的相对地址可以使用下面的公式计算 base+i1×w1+i2×w2 (6.3) 对于k维数组，相应的公式为

base+i1×w1+i2×w2+…..+ik×wk (6.4) 其中，wj (1≤j≤k)是对公式（6.3）中的w1和w2的泛化。

另一种计算数组引用的相对地址的方法是根据第j维上的数组元素的个数nj和该数组的每个元素的宽度w=wk进行计算。在二维数组中（即k=2，w=w2），A[i1][i2]的地址为 base+(i1×n2+i1)×w (6.5) 对于k维数组，下列公式计算得到的地址和公式6.4所得地址相同： base+((..(i1×n2+i2)×n3+i3)…)×nk+ik)×w (6.6) 在更一般的情况下，数组元素下标并不一定是从0开始的。在一个一维数组中，数组元素的编号方式如下：low,low+1….high，而base是A[low]的相对地址。计算A[i]的地址的公式(6.2)变成了：

base+(i-low)×w (6.7) 公式（6.2）和（6.7）都可以改写成i*w+c的形式，其中的子表达式c=base-low*w可以在编译时刻预先计算得到。请注意当low为0时c=base。我们假定c被存放在A对应的符号表条目中，因此只要简单地把i*w加到c上就可以计算得到A[i]的相对地址。

编译时刻的预先计算同样可以被用于多维数组元素的地址计算；见练习6.4.5。然而，有一种情况下我们不能使用编译时刻预先计算的技术：当数组大小是动态的时候。如果我们在编译时刻无法知道low和high（或者它们在多维数组情况下的泛化）的值，我们就无法提前计算出象c这样的常量。因此在程序运行时，象（6.7）这样的公式就需要按照公式所写进行求值。

上面的地址计算是基于数组的按行存放方式的。C和Java语言都使用这种数据布局方式。一个二维数组通常有两种存储方式，即按行存放（一行行地存储）和按列存放（一列列地存放）。图6.21显示了一个2×3的数组A的两种存储布局方式，（a）中是按行存放方式，（b）中是按列存放方式。Fortran系列语言使用按列存放方式。

First row 第一行 First column 第一列 (a)按行存放 Second row 第二行 Second column 第二列 Third column 第三列 (b)按列存放 图6.21：二维数组的存储布局 我们可以把按行存放策略和按列存放策略泛化到多维数组中。按行存放方式的泛化形式按照如下的方式来存储元素：当我们扫描一块存储区域时，就象汽车里程表中的数字一样，最右边的下标变化最为频繁。而按列存放方式则被泛化为相反的布局方式，最左边的下标变化最频繁。

6.4.4 数组引用的翻译

为数组引用生成代码时要解决的主要问题是将6.4.3节中给出的相对地址计算公式和数组引用的语法规则关联起来。令非终结符L生成一个数组名字再加上一个下标表达式的序列：

L → L[E] | id [E]

与C和Java中一样，我们假定数组元素的最低端编号是0。我们使用公式6.4，基于宽度来计算相对地址，而不是象公式（6.6）中那样使用元素的数量。图6.22的翻译方案为带有数组引用的表达式生成三地址代码。它包括了图6.20中给出的产生式和语义动作，同时还包

括了涉及到非终结符L的产生式。

图6.22 处理数组引用的语义动作 非终结符L有三个综合属性：

1. L.addr指示一个临时变量。这个临时变量将被用于累加公式(6.4)中的ij*wj项，计算得到

数组引用的偏移量。

2. L.array是一个指向数组名字的符号表条目的指针。在分析了所有的下标表达式之后，该

数组的基地址，也就是L.array.base，被用于确定一个数组引用的实际左值。

3. L.type是L生成的子数组的类型。对于任何类型t，我们假定其宽度由t.width给出。我

们把类型而不是宽度作为属性，是因为无论如何类型检查总是需要这个类型信息。对于任何数组类型t，假设t.elem给出了其数组元素的类型。

产生式S→id=E; 代表了一个对非数组变量的赋值语句，它按照通常的方法进行处理。S→L=E的语义规则产生了一个带下标的复制指令，它将表达式E的值存放到数组引用L所指的内存位置。回顾一下，属性L.array给出了数组的符号表条目。数组的基地址——即0号元素的地址——由L.array.base给出。属性L.addr表示了一个临时变量，它保存了L生成的数组引用的偏移量。因此这个数组引用的位置是L.array.base[L.addr]。这个指令将地址E.addr中的右值放入L的内存位置中。

产生式E→E1+E2和E→id和以前相同。新的产生式E→L的语义动作生成的代码将L所指位置上的值复制到一个新的临时变量中。和前面对产生式S→L=E的讨论中一样，L所指的地址就是L.array.base[L.addr]；其中属性L.array仍然给出了数组名，L.array.base给出了数组的基地址。属性L.addr表示保存偏移量的临时变量。数组引用的代码将存放在由基地址和偏移量给出的位置中的右值放入E.addr所指的临时变量中。

例子6.12：令a表示一个2×3的整数数组，c、i、j都是整数。那么a的类型就是aray(2,array(3,integer))。假定一个整数的宽度为4，那么a的类型的宽度就是24。a[i]的类型是array(3,integer)，宽度w1为12。a[i][j]的类型是整型。

图6.23给出了表达式c+a[i][j]的标注分析树。该表达式被翻译成图6.24中给出的三地址代码序列。这里我们仍然使用每个标识符的名字来表示它们的符号表条目。□

6.4.5 6.4节的练习

练习6.4.1：向图6.19的翻译方案中加入对应于下列产生式的规则：

a) E→E1*E2。

b) E→+E1 (单目加)。

练习6.4.2：使用图6.20中的增量式翻译方案，重复练习6.4.1。

图6.23：c+a[i][j]的标注分析树