1
编译原理第五章 语法制导翻译和中间代码生成上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 4月
2
本章目的经过词法分析、语法分析后，源程序在静态结构上的正确性得到了保证，
编译程序接着需作静态语义检查以及翻译，真正实现不同程序语言的代码间的等价变换。
3
第五章 语法制导翻译和中间代码生成
§ 5.1翻译概述一、静态语义检查如同词法分析，语法分析同时进行着词法检查、语法检查一样。在语义分析时，必然要进行语义检查。动态语义检查需要生成相应的目标代码，在运行时刻进行，静态语义检查在编译时完成它，则涉及：
4
(1) 类型检查，如参数运算的操作数的类型应相容。
(2) 控制流检查，以保证控制语句有合法的转向点，
如 C语言中的 break语句，需寻找包含它的最小的
switch,while或 for语句，方可找到转向点，否则出错。
(3) 有关名字的匹配检查。可以对某些程序段命名，
该名字出现在程序段的开始和结束处，如同语句括号一般，应检查它们的配对。
(4) 一致性检查，如在相同作用域中标识符只能说明一次,case语句的标号不能相同，枚举类型的元素不能重复等 。
5
二、语法制导翻译的例子。
讨论翻译前，先看一个例子：
图 5.1 展示了文法（ 4.2）的一个翻译方案
E→E+T {print,1”}
E→T {print,2”}
T→T*F {print,3”}
T→F {print,4”}
F→(E) {print,5”}
F→I {print,6”}
图 5.1 文法 (4.2)的一个翻译方案其实是在文法（ 4.2）的每个产生式后配了一个由 { }扩起来的语义子程序，不难证明终结符串（ id+id） *id 是文法（ 4.2）的一个合法句子，它的分析树如图 5.2所示,
6
E
T
* FT
F
E )(
+ TE
T
F
F
i
i
i
图 5.2 (i+i)*i的分析树
7
按照这个句子向文法开始符 E的归约次序，且每当归约时调用该句柄的产生式所对应的语义子程序，便可得到相应的输出串,64264154632。
这个例子表明：输入源语言的符号串 (i+i)*i,输出目标语言的数字串。这自然是一种变幻，而变换的规则时每当（按句柄）归约时调用相应的语言子程序。
无疑这个例子是翻译的一个十分简单的模型。如果将数字串这种目标代码定义为所需目标语言的目标代码，如果每个产生式对应的语言子程序中的一系列语义动作被描述成实现这种转换的动作的序列，
并最终生成所需目标语言的目标代码，那么作为程序变换的翻译也就迎刃而解了。
8
三、翻译要解决的问题翻译是将源语言的程序等价变换为目标语言的程序，于是有三个问题需解决：
（一）、翻译成什么样的目标语言的代码？
（二）、什么时候实现这种变换，即翻译？
（三）、如何实现这种翻译？
9
(1)如第一章引论中提到的那样，我们将源语言程序翻译成中间语言的程序，中间语言与机器无关，而语句颗粒度又与机器语言相当，
于是带来了诸多好处：
①编译逻辑结构简单明确，与机器相关的工作集中到目标代码生成阶段，难度和工作量下降。
②便于移植和维护。
③利于优化。代码优化将分成与机器无关的中间代码优化及与机器相关的目标代码优化两个阶段，是优化更有效。 § 5.2 将讨论中间语言。
10
(2) 如例子所示，如果作为句柄所对应的产生式，
都配有一个相应的翻译子程序，则每当按句柄归约时，就调用相应的翻译子程序（语义子程序）
完成局部的翻译，则一个句子，一段代码，按它们的归约次序，将所有翻译子程序一次执行，就完成了这个句子，这段代码的翻译。这种翻译与语法分析紧密相关，称之为语法制导翻译：每当归约时，调用相应的语义子程序，这就是翻译的时机。
11
(3) 至此不难明白，语法制导翻译的关键，是为每个产生式些相应的翻译子程序了。例子中的 print产生式序号这种语义子程序只能输出这个数字串。现在，对一个有穷表示的文法的无穷多个语句，按所给出的语义子程序要完成不同语句的翻译任务，输出各自的目标代码。难点自然就集中在如何写这些语义子程序了。这一章自 § 5.3起，将花大部分篇幅来讨论各种语句的翻译方案该如何写。
12
§ 5.2 中间语言一、后缀式表示也称逆波兰表示，是由波兰数学家卢卡西维奇
(Lukasiewicz)提出的。它是将 a op b中运算量 a,b依次写在算符 op之前，即 a b op，我们可以形式地给出表达式 E的后缀表示的递归定义：
(1) 如果 E是变量或常数，则 E的后缀表示即 E本身。
(2) 如果 E为 E1 op E2形式，则它的后缀表示为 E1? E2?
op，其中 op是二元算符,E1?,E2?分别是 E的后缀表示 (op
为一元运算时视 E1,E1?为空 )。
(3) 如果 E为 (E1)形式，则 E1后缀表示即为 E的后缀表示。
例如 (-a*b+c)-d的后缀表示 a uminus b*c+d-其中 uminus表示一元运算,=”。
13
三、三地址代码三地址代码其语句一般形式为：
x:=y op z
三地址代码便是这样的语句序列，其中 x,y和 z为名字、常量或编译时产生的临时变量,op为运算符如定点算符，浮点算符，逻辑算符等。由于三地址语句只含一个运算符，故多个算符组成的表达式必须用三地址语句序列表示。例如表达式 x+y*z的三地址代码为：
t1:=y*z
t2:=x+t1
其中,t1和 t2是编译时需要的临时变量。
三地址语句通常包含三个地址，两个用来存放运算对象，
一个用来存放运算结果。在实际实现时，用户定义的名字将由指向符号表中该名字项的指针所代替。
14
t1:=-c t1:=-c
t2:=b*t1 t2:=b*t1
t3:=-c t3:=t2*t2
t4:=b*t1 a:=t5
t5:=t2*t4
a:=t5
(a) (b)
图 5.6 三地址代码
15
四、三地址语句的种类作为中间语言的三地址语句很类似于汇编代码，语句可以有符号标号，有各种控制流语句，本书中常用的三地址语句有以下几种：
(1) x:=y op z形式的赋值语句，其中 op为二目的算术运算符或逻辑运算符。
(2) x:=op y形式的赋值语句，其中 op为一目运算符，如一目减 uminus，逻辑否定 not，移位算符及将定点数转换成浮点数的类型转换符。
(3) x:=y形式的复写语句，将 y的值赋给 x。
(4) 无条件转移语句 goto L下一个将被执行的语句是标号为
L的语句
16
(5) 条件转移语句 if x relopa y goto L,relop为关系运算符如
<、＝,>,>=等，若 x和 y满足关系 relop就转而执行标号为 L的语句，否则顺序执行本语句的下一语句。
(6) 过程调用语句 param X和 call P.n。源程序中的过程调用语句 P(x1,x2,…,xn) 可以用下列三地址代码表示：
param x1
param x2
……
param xn
call P,n
其中整数 n为实参个数。
过程返回语句为 return y，其中 y为过程返回值。
(7) 变址赋值,x:=y[i]，把从地址 y开始的第 i个地址单元的值赋给 x。
x[i]:=y，则是把 y的值赋给从地址 x开始的第 I个地址单元。
以上 x,y,i均代表数据对象。
17
(8) 地址和指针赋值：
x:=&y将 y的地址赋给 x,y可认为是一个名字或者为一个临时变量，它表示一个具左一值的表达式，如 A[i,j]，而 x是指针名或临时变量，这就是说 x的右一值是某个对象 (y)的左一值。
x:=*y将 y指示的地址单元中的内容赋给 x，即 x的右一值等于 y指示的存贮地址的内容。 Y是一个指针或临时变量，其右一值为一地址。
* x:=y将 x所指向的对象的右一值置为 y的右一值。
对设计中间语言来说一个足够小型但却是功能完备的算符集 (足以实现源语言的运算 )当然易于在目标机上实现，但因此会产生较长的中间代码，给优化及代码生成阶段要产生高质量的代码带来困难，因此选择适当的算符集是重要的。
18
五、三地址代码的具体实现三地址代码是中间代码的一种抽象形式，作为具体实现，
通常有四元式，三元式及间接三元式几种形式。
1,四元式具有四个域的记录结构：
(op,arg1,arg2,result)
其中 op为算符,arg1,arg2及 result为指针，可指向有关名字在符号表中的登记项或一临时变量，也可空缺 (我们用 /
表示 )。
19
前面曾遇到的一些三地址语句的相应四元式：
x:= y op z (op,y,z,x)
x:=-y (uminus,y,/,x)
x:=y (:=,y,/,x)
param x1 (param,x1,/,/)
call P (call,/,/,P)
对于赋值语句 a:=b*-c+b*-c相应四元式代码为：
0,(uminus,c,/,t1)
1,(*,b,t1,t2)
2,(uminus,c,/,t5)
3,(*,b,t3,t4)
4,(+,t2,t4,t5)
5,(:=,t5,/,a)
20
2。具有三个域的记录：
(op arg1 arg2)
这里 arg1,arg2既可指向有关名字在符号表中的登记项或临时变量，也可以指向三元表本身某一项。相应于赋值语句 a:=b*-c+b*-c的三元式代码为：
0,uminus c 1
1,*,b 0
2,uminus c /
3,* b 2
4,+ 1 3
5：,= a 4
因此三元式?表示 b与三元式?的结果相乘。
21
3,间接三元式三元式，四元式的运算次序即为其代码表中语句的次序，
在三元式代码表的基础上另设一张表，按运算次序相应三元式在三元式表的位置，这张表称为间接码表。因此三元式表只记录不同的三元式语句，而间接码表则表示由这些语言砀运算次序，对于赋值语句,a:= b*-c+b*-c，其间接三元式代码为：
0,14 14,uminus c /
1,15 15,* b 14
2,14 16,+ 15 15
3,15 17：,=a 16
4,16
5,17
22
三元式表示中，每个语句的位置同时有二个作用：一是可作为该三元式的结果被其他三元引用；二是三元式位置依次又是运算，此在代码优化时需要调整运算次序就会遇到困难。这是因为三元式中 arg1,arg2也可以是指向三元式某位置的指针，因此三元式间有强相关性，次序一旦，调整相关三元式中的一毓指针均需改变。
23
对四元式而言，引用另一语句的结果可以通过引用相应语句的 result(通常是一个临时变量 )来实现，而间接三元式则通过间接码表来描述语句运算次序，这两种方法都改变了三元式的语句位置同时具两个功能的规定，因此代码调整时要作的改动只是局部的，要方便得多，当然四元式表示更接近程序设计习惯。
四元式多了一个域 (还需要临时变量 )，间接三元式多了一个间接码表，与三元式相比，其存贮空间当然要大些，但四元式与间接三元式两者的存贮空间大致相当。
24
§ 5.4 赋值语句赋值语句的文法为：
S?V:=E
赋值左部的变量以及表达式中的变量可以是整型或实型的，也可以是下标变量 (数组元素 )或者记录分量。赋值语句意味着将引用出现在表达式中那些变量或常量的值来计算出表达式的值，并以此对赋值左部变量定值。重要的是需确定出现在赋值语句中这些名字的存贮位置。
25
一、只含简单变量的情况图 5.12给出了只含简单变量的赋值语句三地址代码的翻译方案。翻译方案中 emit是个语义过程，
按所给出的参数生成三地址语句，记在 nextcode
所指的代码空间，然后 nextcode:=nextcode+1指向下一个待生成语句位置（假定语句长度为 1）。出现在赋值语句中的名字由属性 id.name给出名字本身，以此为参数，函数过程 lookup(id.name)将在符号表中寻找此名。若已在符号表中，则返回指向该符号表项的指针，否则，返回 nil，表示没有找到。 newtemp是一个分配临时变量的语义函数，
返回所分配的临时变量,uminus是个一目运算符 。
26
S?id:=E { p:=lookup(id.name)；
if p<>nil then
emit(p':=' E.place)
else error}
E?E1 op E2 { E.place:=newtemp；
emit(E.place?:=?,E1.place，
‘ op?,E2.place)}
E? - E1 { E.place:=newtemp；
emit(E.place':=' 'uminus' E1.place)}
E? (E1) { E.place:=E1.place}
E?id { p:=lookup(id.name)；
if p<>nil then
E.place:=p
else error}
图 5.12 只含简单变量赋值语句的三地址代码翻译方案
27
图 5.12的翻译方案中,E→E1 op E2 参与运算的两个运算对象 E1,E2应有相同的类型，或同为 integer，或同为 real，
而运算符 op则应与运算对象的类型一致。其实在目标语言中，整形 +(i)和实型 +(r)是不同的操作码，反映到中间语言中，也应区分 opi和 opr。
如果参与运算的两个运算对象类型不一致，例如一个为
integer，另一个为 real，则有的语言会以类型不相容做出错处理，而现在大多数语言的算术表达式中，容许整形和实型数之间的运算。这时，需将整形运算量转换到实型运算量。在翻译中，借助于语义函数 i+r(x),将整形 x转换成实型数。于是相应于 E→E1 op E2 的语义子程序在引进语义变量 E.type后将如图 5.13所示
28
E→E1 op E2
{ t:=newtemp; if（ E1.type=integer and E2.type=integer）
{ E.type:=integer;
emit(t:=E1.place opi E2.place)
}
else if(E1.type=real and E2.type=real）
{E.type:=real;
emit(t:=E1.place opr E2.place)
}
else if（ E1.type=integer）
{ t1:=newtemp;t1:=i+r(E1.place);
emit(t:=t1 opr E2.place);
E.type:=real ；
} else{ t1:=newtemp;t1:=I+r(E2.place);
emit(t:=E1.place opr t1);
E.type:=real;E.place:=t}
图 5.13 允许不同类型间运算的翻译子程序
29
二、数组元素的地址计算分式相同类型的一组数据形成数组。数组总是存放在一片连续单元里。
一维数组的元素是线性序的，所以与所分配的连续空间极易建立一一对应关系。
n维数组 A(n≥2)描述了 n维空间元素集，因此它的数组元素空间必须与一维的线性存贮空间建立起一个一一映射，这样每个数组元素就有了一个唯一确定的存贮位置。当然这种一一映射可能不止一个，例如按行存放和按列存放就是两种不同的映射。按行存放是将第一维看成最高位，第 n
维看成是最低位。设第 i维的下界为 lowi上界为 highi则将第
i位看成是 di=highi-lowi+1进制成的，那么这是个 n位的，
每一位是 di，进制的计数器，就给出了将这 n维空间的元素映射成一个线性序的一维空间的一个函数。初始元素 A0
为 A[low1,low2,…,lown],元素 A[i1,i2,…in] 是 A0后的第
L个元素。
30
L＝ (i1-low1)*d2*d3*…*dn+(i2 -low2)*d3*d4
*…*dn+…+(in -1－ lown-1)*d1+in－ lown (5.1)
其中 di=highi-lowi+1(i=1,2,…,n) (5.2)
如果每个元素的存贮宽度为 W,A0的存贮位置为 base，则：
A[i1,i2,…in] 的存贮位置 D为：
D ＝ base+L*W
＝ base-((…((low1*d2+low2)*d3+low3)…)
dn+lown)*W+((…((i1*d2+i2)*d3+i3)…)
dn+in*W (5.3)
因为 base是个相对地址，所以 D也是个相对地址，公式 (5.3)
为数组元素的地址计算公式。
令 C＝
((…((low1*d2+low2)*d2+low3)…)*dn+lown)*W
AVRPART=((…((i1*d2+i2)*d3+i3)…)*dn+in)*W
则 D=base-C+VARPART (5.4)
31
显然一维，二维数组是上述公式的特例。
一维数组元素 A[i]的相对地址为：
D＝ base+(i-low)*W=base-C+i*W
这里 C=low*W
二维数组元素 A[i1,i2]的相对地址为：
D＝ base+((i1-low1)*d2+i2-low2)*W
=base-C+(i1*d2+i2)*W
这里 C=(low1*d2+low2)*W
32
三、含数组元素的变量的访问赋值语句中出现的变量既可以是简单变量也可以是数组元素 (或称下标变量 )，其语法可由下列产生式描述：
V→id[Elist]|id
Elist→Elist,E|E
其中 id或为数组名，或为简单变量名,Elist是由下标表达式组成的下标表。在翻译时要确定数组元素的位置，需要知道该数组的 base和 C及每一维的长度 di，然后根据公式
(5.4)，可计算该数组元素的相对地址，但是 base,C和 di
的信息都在相应于数组名 id的内情向量中，为了在用
Elist→Elist,E|E归约时能得到 id表项中上述信息，因此将上述文法改写为：
V→Elist]|id
Elist→Elist,E|id[E
33
由产生式 Elist→id[E 归约时即可将 id的表项位置作为 Elist
的一个综合属性 Elist.array的值。以后每当用产生式
Elist→Elist,E归约一次，就处理这一维的地址计算 (即
ej=ej-1*dj+ij)同时将 Elist.array这个属性值一直传递下去，
直至最后由 V→Elist] 归约时止。
一个数组元素的地址是由数组零地址 base-C和这个元素相对于零地址的偏移量组成，它们分别由 V.place和 V.offset记录着。对简单变量而言，它的地址则由 V.place记录着，而
V.offset则恒置为 null，这可作为翻译中对简单变量和下标变量的一种识别或区分。
34
四、含数组元素的赋值语句的翻译方案相应的文法为：
1 S→V:=E
2 E→E1 op E2
3 E→(E1)
4 E→V
5 V→Elist]
6 V→id
7 Elist→Elist1,E
8 Elist→id[E
35
翻译方案中的语义动作是这样给出的：
(1) 在表达式中或赋值左部遇到的是简单变量 (也即由
V→id 归约 )或下标变量 (由 Elist→id[E 归约 ]，两者区别当然是名字 id后是否有下标括号 [，当为简单变量时语义动作为,V→id { p:=lookup(id.name)；
if p≠nil then begin V.place:=p；
V.offset:=null end else error}
当为下标变量时，产生式 Elist→id[E 中 id为数组名，由
id.name可查得数组表项位置，同时第一维下标表达式的值已在 E.place中，所以语义动作为：
Elist→id [E { p:=lookup(id.name)；
if （ p≠nil） { Elist.array:=p；
Elist.place:=E.place；
Elist.dim:=1； }
else error}
36
(2) Elist→Elist1,E表明下标变量的下标表已归约了 i-1维，
现遇到第 i维下标表达式 E1，此时需生成乘加的三地址指令：即 ei=ei-1*di+E1，运算后的中间结果保存在 Elist1
place中，第 i维的长度 di可由函数 limit(Elist1 array,i)查得。
注意 Elist1.array指出数组名的表项位置。
Elist→Elist1,E { t:=newtemp； i:=Elist.dim+1；
emit(t?:=?Elist1.place*limit(Elist1.array,i))； }
emit(t?:=?t+e.place)；
Elist.array:=Elist1.array；
Elist.place:=t；
Elist.dim:=i}
37
(3) 由 V→Elist] 归约时，数组元素的下标表结束，这时下标变量的 base-C及 VARPART或由数组的符号表项
(Elist.array指出 )查得，或通过计算得到，它们分别保存在
V.place和 V.offset中。
V→Elist] { V.place:=newtemp；
V.place?:=base-C)；
V.offset:=newtemp；
emit(V.offset?:=?Elist.place?*?W)}
38
(4) 对于表达式中的变量，按简单变量或下标变量分别处理：
E→V { if V.offset =null then
E.place:= V.place
else begin
E.place:=newtemp；
emit(E.place?:=?V.place[V.offset])
end}
表达式中对数组元素的引用，需要的是 V的右一值。故生成的三地址指令 E.place:=V.place [V.offset]这是变址取类型的指令。
39
（ 5） 表达式运算及子表达式仍同 § 5.3一：
E→E1 op E2 {E.place:=newtemp ；
emit(E.place:?=?E1.place?op?E2.place)}
E→(E1) {E.place:=E1.place}
(6) 赋值语句的左部变量可能为简单变量，也可能为下标变量，若 V为下标变量时，需要 V的左一值，生成三地址指令就是变址存贮的形式：
V.place [V.offset]:=E.place
故有 S→V:=E { if （ V.offset=null）
emit(V.place:?=?E.place)
else
emit(v.place[V.offset]?:=?E.place)}′
40
[例 5.1] 一个 10′20的数组 A(d1=10,d2=20)，设 W=4，
low1=low2=1，即 A[1,1]为数组的第一个元素，则
C=(low1*d2+low2)*W=84，如果赋值语句为 x:=A[y,z]，
则它的带注释的语法分析树如 5.14所示。
根据自下而上的翻译方案，赋值语句 x:=A[y,z]被翻译成下列三地址语句序列：
t1:=y*20
t1:=t1+z
t2:=A-84
t3:=4*t1
t4:=t2[t3]
x:=t4
翻译中 id.place均直接用相应的名字来代替。
41
z
s
:=V.place=x
V.offset=n
ullx
E.place=t1
…
V.place=t2
V.offset=t3
Elist.place
=t1
Elist.dim=
2
Elist.array
=A
Elist.place
=y
Elist.dim=
1
Elist.array
=A
,E.place=x
…
V.place=z
V.offset=n
ullA [ E.place=y…
V.place=y
V.offset=n
ully
图 5.14 赋值语句 x:=A[y,z]的带注释的分析树
]
42
§ 5.5 控制流语句一、布尔表达式的两种基本作用在程序语言中布尔表达式 E有两个基本作用：
参于逻辑运算，如 E?E或?E。
作控制语句的条件式，如 if E then S或 while E do S。
布尔表达式是由布尔运算符 and,or,not(亦可为?,?、
)作用于布尔变量 (或布尔常量 )或关系表达式而形成的，
关系表达式的形式为 E1 relop E2，其中 E1,E2为算术表达式,relop为关系运算符如 <,?,=,?,>,?，由属性
relop.op确定。
我们只考虑下列文法所产生的布尔表达式：
E?E and E|E or E|not E|(E)|id relop id|id|true|false
(5.5)
为消除上述文法的二义性，按通常习惯规定,or,and
为左结合的，优先顺序由高到低依次为 not,and,or。而关系运算符的优先级均相同，并且高于任何布尔运算符，
而低于任何算术运算符，关系运算符不得结合，如
A=B>C是不符合文法的。
43
二、布尔表达式的两种翻译方法第一种方法为数值表示法：以 0表示 false,1表示 true，
并像计算算术表达式那样根据优先级结合律逐步计算出表达式的逻辑值，例如布尔表达式：
1 or not 0 and 0 or 0 的计算过程为
1 or not 0 and 0 or 0=l or 1 and 0 or 0
=1 or 0 or 0
=1 or 0
=1
第二种方法为解释法。例如，布尔表达式 E1 or E2，如果 E1为 true则不管 E2的值如何布尔表达式肯定为 true，
只有 E1为 false时,E2的值即为布尔表达式 E的值。与数值表示法相比，运算次数有可能减少，因而可能是一种优化。这种方法是将 or,and,not这三个逻辑运算用 if-
then-else来解释：
将 A or B解释为 if A then true else B；
将 A and B解释为 if A then B else false；
将 not A解释为 if A then false else true。
44
三、数值表示法翻译方案用 0表示 false,1表示 true像算术表达式那样根据优先级，
结合律从左到右去示值，则布尔表达式 a or b and not c将被翻译成如下三地址语句序列：
t1:=not c
t2:=b and t1
t3:=a or t2
对于表达式 a<b由 if a<b then 1 else 0来确定它的值 (0或 1)，
相应的三地址语句序列为：
100,if a<b goto 103
101,t:=0
102,goto 104
103,t:=1
104：
然后像布尔量一样参于布尔表达式的运算。
45
产生布尔表达式三地址代码的翻译方案示于图 5.13，其中由 nextcode指向当前将生成三地址语句位置，显然 emit
生成一三地址语句并送到三地址语句表后 nextcode需增 1。
我们约定：这种情况的 nextcode增 1是恰在过程 emit返回前完成的。
46
E→E1 or E2 { E.place:=newtemp ；
emit(E.place ‘:=’ E1.place ‘or’ E2.place)}
E→E1 and E2 { E.place:=newtemp ；
emit(E.place ‘:=’ E1.place ‘and’ E2.place)}
E→not E1 { E.place:=newtemp ；
emit(E.place ‘:=’ ‘not’ E1.place)}
E→(E1) { E.place:=E1.place}
E→id1 relop id2 { E.place:=newtemp ；
emit (‘if’ id1.place relop.op id2.place
‘goto’ nextcode+3)；
emit(E.place ‘:=’ ’0’)；
emit(‘goto’ nextcode+2)；
emit(E.place ‘:=’ ’1’)}
47
E→id { E.place:=newtemp ；
emit(‘if’ id.place ‘goto’ nextcode+3)；
emit(E.place ‘:=’ ‘0’)；
emit(‘goto’ nextcode+2)；
emit(E.place ‘:=’ ‘1’)}
E→true { E.place:=newtemp ；
emit(E.place ‘:=’ ‘1’)}
E→false { E.place:=newtemp ；
emit(E.place ‘:=’ ‘0’)}
图 5.15 布尔表达式数值表示的翻译方案
48
[例 5.4] 对布尔表达式 a<b or c=d and not e>f生成三地址代码，由图 5.15的翻译方案可得下列三地址代码：
100,if a<b goto 103 108,if e>f goto 111
101,t1:=0 109,t3:=0
102,goto 104 110,goto 112
103,t1:=1 111,t3=1
104,if c=d goto 107 112,t4:=not t3
105,t2:=0 113,t5:=t2 and t4
106,goto 108 114,t6:=t1 or t5
107,t2:=1
49
五、控制流语句中布尔表达式的翻译控制流语句中的布尔表达式 E按照控制转移的解释翻译方法，它将被翻译成一系列的条件转移和无条件转移的三地址代码。不管由这些转向语句组成的代码序列有多长，作为布尔表达式，最终总是综合为转向 E的真出口,E.true和 E的假出口 E.false。
作为布尔表达式 E的最基本成分是布尔常量，布尔变量和关系表达式，由它们最早产生的转向真出口或转向假出口的语句，分别为：
50
(1) E→id1 relop id2,(这里 id1,id2均为算术量，
relop为关系运算符 )E,if id1 relop id2 goto E.true
goto E.false
(2) E→id( 这里 id是个布尔变量 )E,if id goto E.true
goto E.false
(3) E→trueE,goto E.true
(4) E→falseE,goto E.false
由于表达式参于表达式运算时，则依据逻辑运算符将子表达式的真出口和假出口综合得到 E的真出口 E.true和 E的假出口 E.false。
51
(5) E→E1 or E2
E1.code to
E1.falseto
E1.true
E2.code
E.code
E1.false:
to
E2.false
to
E2.true toE.trueto
E.false
52
(6) E→E1 and E2
E1.code to
E1.trueto
E1.false
E2.code
E.code
E1.false,toE
2.falseto
E2.true
to
E.falseto
E.true
53
(7) E→not E1
E1.codeE1.code toE
1.trueto
E1.false
to
E.falseto
E.true
54
当判定 E1为真时，需为 goto E.true，但由于 E2尚未翻译，
它的代码长度桅顶，因此 后续为真的转向点自然不得而知，例如：
a<b or c<d and not e<f
在 nextcode为 100的假定下按上述代码结构，他可以生成三地址代码为
100 if a<b goto E.true
101 goto 102
102 if c<d goto 104
103 goto E.false
104 if e<f goto E.false
105 goto E.true
55
当翻译 a<b时，它可以生成 100,101二个语句。
但 101,goto E.true这 E.true究竟在何处，这完全依赖 or后的表达式结构，在翻译当时无法确定。我们把在翻译过程中有相同的转向（其实只有 E.true、
E.false两种不同转向）而当时又不能确定具体转向点的三地址语句勾连成一条链，最先生成的链上的三地址语句 L1转向点用 0表示为链尾是，即
L1,goto 0
56
其次生成的链上的三地址语 L2，其转向点用 L1表示，即：
L2,goto L1
依次类推，最后生成的三地址语句便为 Ln：
L1,… goto 0;
…
L2,… goto L1;
…
Ln-1:…goto Ln -2
…
Ln:… goto Ln
图 5.16 有相同转向点的语句链
57
(1) E→E1 or M E2 { backpatch(E1.falselist,M.code);
E.trulist:=merge(E1.truelist,E2.truelist);
E.falselist:=E2.falselist}
(2) E→E1 and M E2{ backpatch(E1.truelist,M.code);
E.falselist:=merge(E1.falselist,E2.falselist);
E.truelist:=E2.truelist}
(3) E→not E1 { E.truelist:=E1.falselist;
E.falselist:=E1.truelist;}
58
(4) E→(E1) { E.truelist:=E1.truelist;
E.falselist:=E1.falselist;}
(5) E→id1 relop id2 { E.truelist:=makelist(nextcode);
emit(if id1.place relop id2.place goto 0);
E.falselist:=makelist(nextcode);
emit(goto 0)}
59
(6) E→id { E.truelist:=makelist(nextcode);
emit(if id.place goto 0);
E.falselist:=makelist(nextcode);
emit(goto 0)}
(7) E→true { E.truelist:=makelist(nextcode);
emit(goto 0)}
(8) E→false {E.falselist:=makelist(nextcode);
emit(goto 0) }
(9) M→ε { M.code:=nextcode}
图 5.17 布尔表达式的翻译方案
60
[例 5.5] 用回填技术完成 a<b or c<d and not e<f 的翻译，设
nextcode为 100。翻译的注释分析树如图 5.18所示。
d
orE1.truelist=10
0
E1.falselist=10
1 ε
E5.truelist=10
5
E5.falselist=10
4
E2.truelist=10
2
E2.falselist=10
3
E4.truelist=10
5
E4.falselist=10
4<c
图 5.18 a<b or c<d and not e<f 的翻译分析树
an
d
E.truelist=105
E.falselist=10
4
M1.code=102
M2.code=104
ε
not E3.truelist=10
4
E3.falselist=10
5 f<e
b<a
61
生成的三地址代码为：
100 if a<b goto 0
101 goto 102
102 if c<d goto 104
103 goto 0
104 if e<f goto 103
105 goto 100
同时有 E.truelist=105,E.falselist=104。待该布尔表达式后续部分翻译过程中确定 E为真的转向地址时，
按链头 105的 E.truelist来回填转向语句的转向点；
确定 E为假的转向地址时，按链头为 104的
E.falselist来回填转向语句的转向点。因此，上述三地址代码并非最后生成的中间代码，其中挂在链上的转向语句，是尚未完成的语句。其转向点只是链的连接元，并非是真实的转向地址。
62
五,控制流语句的翻译这里只讨论下列文法所指定的控制流语句：
(1)S→if E then S1
(2) | if E then S1 else S2
(3) | while E do S1
(4) | begin L end
(5) | A
(6)L→L ; S
(7) |S
其中 A为赋值语句,L为语句表,所以 begin L end为复合语言,它的语法地位同其它一般语句 。 如果文法中相当 S位置上不能由一个语句,而需要由一串语句 （ 即语句表 ） 来描述时,用语句括号把语句表 L括起来,就可以作为一个语句对待了 。
63
产生式 (1),(2),(3)的目标代码结构分别如图 5.16之 (a)、
(b),(c)所示。
E.code to E.true
to S.next (to
E.false)
S1.codeE.true:
(if-then
E.code to E.true
to
E.false
S1.codeE.true:
(if-then-else
goto
S.next
to S.next
S2.codeE.false:
E.code
S1.code
goto
S.begin
E.true:
S.begin,to E.true
to S.next
(wile-do
图 5.16 控制流语句的目标代码结构
64
(1)S→ if E then M S1 { bakpatch(E.truelist,M.code);
S.nextlist:=merge(E.falselist,S1.nextlist)}
(2)F→ if E then M S1 else
{ backpatch(E.truelist,M.code);
t:=makelist(nextcode);
emit(goto,0);
F.nextlist:=merge(S1.nextlist,t);
backpatch(E.falselist,nextcode)}
(3)S→ F S1 { S.nextlist:=merge(F.nextlist,S1.nextlist)}
(4)S→ while M1 E do M2 S1
{ backpatch(E.truelist,M2.code);
backpatch(S1.nextlist,M1.code);
emit(goto,M1.code);
S.nextlist:=E.falselist}
65
(5) S→ begin L end { S.nextlist:=L.nextlist}
(6) S→ A { S.nextlist:=makelist()}
(7) L→ L1; M S { backpatch(L1.nextlist,
M.code);
L.nextlist:=S.nextlist}
(8) L→ S { L.nextlist:=S.nextlist}
(9) M→ ε { M.code:=nextcode}
图 5.17控制流语句的翻译方案
66
[例 5.5] 有下列语句序列
if a<b or e<d and not e<f then A1 else A2;
while a<b do A3
其中 A1,A2,A3均为赋值语句,这里不予展开 。 假定它们生成 10个三地址语句,它们的代码均以方框来表示 。 这里有二个语句,并组成一个语句表,主要涉及：
F→ if E then M S1 else
S→ F S1
S→ while M1 E do M2 S1
L→ S
L→ L1; M S
产生式及相应的语义动作 。 假定翻译开始时
nextcode=100。
67
(1) 布尔表达式 a<b or c<d and not e<f的代码在例
5.5生成了代码：
100,if a<b goto 0
101,goto 102
102,if c<d goto 104
103,goto 0
104,if e<f goto 103
105,goto 100
以及二条链 E.truelist=105,E.falselist=104,它们各自有 105,100二个语句及 104,103二个语句 。
(2) 在 then后有一次 M→ε 归约,M.code=106；它恰为 A1代码开始位置 。
(3) A1经归约后生成的代码为,106,A1.code
116:
68
(4) 识别 else后,应按 F→ if E then M A1 else归约,
这时有语义动作,backpatch(E.truelist,M.code),即以 105为链头的 E.truelist,用 106回填,故 100,105语句的转向点均为 106,生成语句
116,goto 0
并将 116与 S1.nextlist（ 即 A1的空链 ） 两条链合并,
成为 F.nextlist,这条链上只有 116一个语句,用现在的 nextcode=117 回填 E.falselist,
badkpatch(E.false,117)。 故 104,103的转向点均为
117。
(5) 识别 A2后,即用产生式 S→F S1归约后,因为
S1即 A2的 S1.nextlist为空链,故 S.nextlist=F.nextlist即
116,而 A2的代码为,117,A2.code
127:
69
(6) L→S 后 L.nextlist:=116,识别；后 M→ ε归约将当时 nextcode=127记录在 M.code中 。
(7) while M1 a<b do M2 A3 时,
M1.code=127,M2.code=129生成的代码为,
127:if a<b goto
128,goto 0
129:A3.code
139,goto 127
并形成 S.nextlist=128的语句出口链 。
(8) 用 L→L 1; M S 归 约 时,
backpatch(L1.nextlist,M.code),即以 116 为 链 头 的
L1.nextlist,用 M.code=127回填,使 116语句为 goto
127；同时 L.nextlist:=S.nextllist为 128。
最后有 L.nextlist=128。
70
§ 5.6 循环语句、过程调用语句及 CASE语句一,循环语句的翻译有一类循环语句可以用下列文法来描述：
S→ for i:=1 to N do S1
其中 i为循环变量,它的循环初值和终值分别为１
和 N,都是常量,其语义为：
i:=1; L,i:=1
again,if i<=N then L+1,if i>N goto S.nextlist
begin S1; L+2,S1.code
i:=i+1; M,i:=i+1
goto again M+1,goto L+1
end
71
其中,从 L+2开始到 M之前是 S1语句的代码 。 显然在生成 的代码之前,应先生成 i:=1等二个语句 。 也即在发生对 S1的归约之前先发生一次归约,这样才可能调用相应语义子程序,生成这二个语句 。 为此引进辅助非终结符 F,并将文法转换为：
F→ for i:=1 to N do
S→ F S1
相应的翻译方案为
F→ for i:=1 to N do { p:=lookup(i.name);
emit(p,?:=?,?1?);
f.again:=nextcode;
emit(if p,>,?N?,goto 0);
F.place:=p}
S→F S1 { emit(F.place,?:=?,F.place,+,?1?);
emit(goto,F.again);
backpatch(S1.nextlist,F.again);
S.nextlist:=F.again}
72
翻译方案中,属性 F.place记录循环变量的地址,
F.again记录循环入口,S.nextlist,记录了循环出口语句的位置,待 S的后续语句的位置确定后再回填由 S.nextlist指出的转向语句的转向地址 。
在上述翻译方案中,我们通过改写文法而不是通过插入标记非终结符的办法来完成翻译的 。 因为在
do后插入标记非终结符 M虽然在分析到此时刻,可以增加 M→ε 的归约,但是生成二个语句的语义动作不可能由 M→ε 时获得 。 目前采取的分两段归约的做法有更强的可适用性 。
编译原理第五章 语法制导翻译和中间代码生成上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 4月
2
本章目的经过词法分析、语法分析后，源程序在静态结构上的正确性得到了保证，
编译程序接着需作静态语义检查以及翻译，真正实现不同程序语言的代码间的等价变换。
3
第五章 语法制导翻译和中间代码生成
§ 5.1翻译概述一、静态语义检查如同词法分析，语法分析同时进行着词法检查、语法检查一样。在语义分析时，必然要进行语义检查。动态语义检查需要生成相应的目标代码，在运行时刻进行，静态语义检查在编译时完成它，则涉及：
4
(1) 类型检查，如参数运算的操作数的类型应相容。
(2) 控制流检查，以保证控制语句有合法的转向点，
如 C语言中的 break语句，需寻找包含它的最小的
switch,while或 for语句，方可找到转向点，否则出错。
(3) 有关名字的匹配检查。可以对某些程序段命名，
该名字出现在程序段的开始和结束处，如同语句括号一般，应检查它们的配对。
(4) 一致性检查，如在相同作用域中标识符只能说明一次,case语句的标号不能相同，枚举类型的元素不能重复等 。
5
二、语法制导翻译的例子。
讨论翻译前，先看一个例子：
图 5.1 展示了文法（ 4.2）的一个翻译方案
E→E+T {print,1”}
E→T {print,2”}
T→T*F {print,3”}
T→F {print,4”}
F→(E) {print,5”}
F→I {print,6”}
图 5.1 文法 (4.2)的一个翻译方案其实是在文法（ 4.2）的每个产生式后配了一个由 { }扩起来的语义子程序，不难证明终结符串（ id+id） *id 是文法（ 4.2）的一个合法句子，它的分析树如图 5.2所示,
6
E
T
* FT
F
E )(
+ TE
T
F
F
i
i
i
图 5.2 (i+i)*i的分析树
7
按照这个句子向文法开始符 E的归约次序，且每当归约时调用该句柄的产生式所对应的语义子程序，便可得到相应的输出串,64264154632。
这个例子表明：输入源语言的符号串 (i+i)*i,输出目标语言的数字串。这自然是一种变幻，而变换的规则时每当（按句柄）归约时调用相应的语言子程序。
无疑这个例子是翻译的一个十分简单的模型。如果将数字串这种目标代码定义为所需目标语言的目标代码，如果每个产生式对应的语言子程序中的一系列语义动作被描述成实现这种转换的动作的序列，
并最终生成所需目标语言的目标代码，那么作为程序变换的翻译也就迎刃而解了。
8
三、翻译要解决的问题翻译是将源语言的程序等价变换为目标语言的程序，于是有三个问题需解决：
（一）、翻译成什么样的目标语言的代码？
（二）、什么时候实现这种变换，即翻译？
（三）、如何实现这种翻译？
9
(1)如第一章引论中提到的那样，我们将源语言程序翻译成中间语言的程序，中间语言与机器无关，而语句颗粒度又与机器语言相当，
于是带来了诸多好处：
①编译逻辑结构简单明确，与机器相关的工作集中到目标代码生成阶段，难度和工作量下降。
②便于移植和维护。
③利于优化。代码优化将分成与机器无关的中间代码优化及与机器相关的目标代码优化两个阶段，是优化更有效。 § 5.2 将讨论中间语言。
10
(2) 如例子所示，如果作为句柄所对应的产生式，
都配有一个相应的翻译子程序，则每当按句柄归约时，就调用相应的翻译子程序（语义子程序）
完成局部的翻译，则一个句子，一段代码，按它们的归约次序，将所有翻译子程序一次执行，就完成了这个句子，这段代码的翻译。这种翻译与语法分析紧密相关，称之为语法制导翻译：每当归约时，调用相应的语义子程序，这就是翻译的时机。
11
(3) 至此不难明白，语法制导翻译的关键，是为每个产生式些相应的翻译子程序了。例子中的 print产生式序号这种语义子程序只能输出这个数字串。现在，对一个有穷表示的文法的无穷多个语句，按所给出的语义子程序要完成不同语句的翻译任务，输出各自的目标代码。难点自然就集中在如何写这些语义子程序了。这一章自 § 5.3起，将花大部分篇幅来讨论各种语句的翻译方案该如何写。
12
§ 5.2 中间语言一、后缀式表示也称逆波兰表示，是由波兰数学家卢卡西维奇
(Lukasiewicz)提出的。它是将 a op b中运算量 a,b依次写在算符 op之前，即 a b op，我们可以形式地给出表达式 E的后缀表示的递归定义：
(1) 如果 E是变量或常数，则 E的后缀表示即 E本身。
(2) 如果 E为 E1 op E2形式，则它的后缀表示为 E1? E2?
op，其中 op是二元算符,E1?,E2?分别是 E的后缀表示 (op
为一元运算时视 E1,E1?为空 )。
(3) 如果 E为 (E1)形式，则 E1后缀表示即为 E的后缀表示。
例如 (-a*b+c)-d的后缀表示 a uminus b*c+d-其中 uminus表示一元运算,=”。
13
三、三地址代码三地址代码其语句一般形式为：
x:=y op z
三地址代码便是这样的语句序列，其中 x,y和 z为名字、常量或编译时产生的临时变量,op为运算符如定点算符，浮点算符，逻辑算符等。由于三地址语句只含一个运算符，故多个算符组成的表达式必须用三地址语句序列表示。例如表达式 x+y*z的三地址代码为：
t1:=y*z
t2:=x+t1
其中,t1和 t2是编译时需要的临时变量。
三地址语句通常包含三个地址，两个用来存放运算对象，
一个用来存放运算结果。在实际实现时，用户定义的名字将由指向符号表中该名字项的指针所代替。
14
t1:=-c t1:=-c
t2:=b*t1 t2:=b*t1
t3:=-c t3:=t2*t2
t4:=b*t1 a:=t5
t5:=t2*t4
a:=t5
(a) (b)
图 5.6 三地址代码
15
四、三地址语句的种类作为中间语言的三地址语句很类似于汇编代码，语句可以有符号标号，有各种控制流语句，本书中常用的三地址语句有以下几种：
(1) x:=y op z形式的赋值语句，其中 op为二目的算术运算符或逻辑运算符。
(2) x:=op y形式的赋值语句，其中 op为一目运算符，如一目减 uminus，逻辑否定 not，移位算符及将定点数转换成浮点数的类型转换符。
(3) x:=y形式的复写语句，将 y的值赋给 x。
(4) 无条件转移语句 goto L下一个将被执行的语句是标号为
L的语句
16
(5) 条件转移语句 if x relopa y goto L,relop为关系运算符如
<、＝,>,>=等，若 x和 y满足关系 relop就转而执行标号为 L的语句，否则顺序执行本语句的下一语句。
(6) 过程调用语句 param X和 call P.n。源程序中的过程调用语句 P(x1,x2,…,xn) 可以用下列三地址代码表示：
param x1
param x2
……
param xn
call P,n
其中整数 n为实参个数。
过程返回语句为 return y，其中 y为过程返回值。
(7) 变址赋值,x:=y[i]，把从地址 y开始的第 i个地址单元的值赋给 x。
x[i]:=y，则是把 y的值赋给从地址 x开始的第 I个地址单元。
以上 x,y,i均代表数据对象。
17
(8) 地址和指针赋值：
x:=&y将 y的地址赋给 x,y可认为是一个名字或者为一个临时变量，它表示一个具左一值的表达式，如 A[i,j]，而 x是指针名或临时变量，这就是说 x的右一值是某个对象 (y)的左一值。
x:=*y将 y指示的地址单元中的内容赋给 x，即 x的右一值等于 y指示的存贮地址的内容。 Y是一个指针或临时变量，其右一值为一地址。
* x:=y将 x所指向的对象的右一值置为 y的右一值。
对设计中间语言来说一个足够小型但却是功能完备的算符集 (足以实现源语言的运算 )当然易于在目标机上实现，但因此会产生较长的中间代码，给优化及代码生成阶段要产生高质量的代码带来困难，因此选择适当的算符集是重要的。
18
五、三地址代码的具体实现三地址代码是中间代码的一种抽象形式，作为具体实现，
通常有四元式，三元式及间接三元式几种形式。
1,四元式具有四个域的记录结构：
(op,arg1,arg2,result)
其中 op为算符,arg1,arg2及 result为指针，可指向有关名字在符号表中的登记项或一临时变量，也可空缺 (我们用 /
表示 )。
19
前面曾遇到的一些三地址语句的相应四元式：
x:= y op z (op,y,z,x)
x:=-y (uminus,y,/,x)
x:=y (:=,y,/,x)
param x1 (param,x1,/,/)
call P (call,/,/,P)
对于赋值语句 a:=b*-c+b*-c相应四元式代码为：
0,(uminus,c,/,t1)
1,(*,b,t1,t2)
2,(uminus,c,/,t5)
3,(*,b,t3,t4)
4,(+,t2,t4,t5)
5,(:=,t5,/,a)
20
2。具有三个域的记录：
(op arg1 arg2)
这里 arg1,arg2既可指向有关名字在符号表中的登记项或临时变量，也可以指向三元表本身某一项。相应于赋值语句 a:=b*-c+b*-c的三元式代码为：
0,uminus c 1
1,*,b 0
2,uminus c /
3,* b 2
4,+ 1 3
5：,= a 4
因此三元式?表示 b与三元式?的结果相乘。
21
3,间接三元式三元式，四元式的运算次序即为其代码表中语句的次序，
在三元式代码表的基础上另设一张表，按运算次序相应三元式在三元式表的位置，这张表称为间接码表。因此三元式表只记录不同的三元式语句，而间接码表则表示由这些语言砀运算次序，对于赋值语句,a:= b*-c+b*-c，其间接三元式代码为：
0,14 14,uminus c /
1,15 15,* b 14
2,14 16,+ 15 15
3,15 17：,=a 16
4,16
5,17
22
三元式表示中，每个语句的位置同时有二个作用：一是可作为该三元式的结果被其他三元引用；二是三元式位置依次又是运算，此在代码优化时需要调整运算次序就会遇到困难。这是因为三元式中 arg1,arg2也可以是指向三元式某位置的指针，因此三元式间有强相关性，次序一旦，调整相关三元式中的一毓指针均需改变。
23
对四元式而言，引用另一语句的结果可以通过引用相应语句的 result(通常是一个临时变量 )来实现，而间接三元式则通过间接码表来描述语句运算次序，这两种方法都改变了三元式的语句位置同时具两个功能的规定，因此代码调整时要作的改动只是局部的，要方便得多，当然四元式表示更接近程序设计习惯。
四元式多了一个域 (还需要临时变量 )，间接三元式多了一个间接码表，与三元式相比，其存贮空间当然要大些，但四元式与间接三元式两者的存贮空间大致相当。
24
§ 5.4 赋值语句赋值语句的文法为：
S?V:=E
赋值左部的变量以及表达式中的变量可以是整型或实型的，也可以是下标变量 (数组元素 )或者记录分量。赋值语句意味着将引用出现在表达式中那些变量或常量的值来计算出表达式的值，并以此对赋值左部变量定值。重要的是需确定出现在赋值语句中这些名字的存贮位置。
25
一、只含简单变量的情况图 5.12给出了只含简单变量的赋值语句三地址代码的翻译方案。翻译方案中 emit是个语义过程，
按所给出的参数生成三地址语句，记在 nextcode
所指的代码空间，然后 nextcode:=nextcode+1指向下一个待生成语句位置（假定语句长度为 1）。出现在赋值语句中的名字由属性 id.name给出名字本身，以此为参数，函数过程 lookup(id.name)将在符号表中寻找此名。若已在符号表中，则返回指向该符号表项的指针，否则，返回 nil，表示没有找到。 newtemp是一个分配临时变量的语义函数，
返回所分配的临时变量,uminus是个一目运算符 。
26
S?id:=E { p:=lookup(id.name)；
if p<>nil then
emit(p':=' E.place)
else error}
E?E1 op E2 { E.place:=newtemp；
emit(E.place?:=?,E1.place，
‘ op?,E2.place)}
E? - E1 { E.place:=newtemp；
emit(E.place':=' 'uminus' E1.place)}
E? (E1) { E.place:=E1.place}
E?id { p:=lookup(id.name)；
if p<>nil then
E.place:=p
else error}
图 5.12 只含简单变量赋值语句的三地址代码翻译方案
27
图 5.12的翻译方案中,E→E1 op E2 参与运算的两个运算对象 E1,E2应有相同的类型，或同为 integer，或同为 real，
而运算符 op则应与运算对象的类型一致。其实在目标语言中，整形 +(i)和实型 +(r)是不同的操作码，反映到中间语言中，也应区分 opi和 opr。
如果参与运算的两个运算对象类型不一致，例如一个为
integer，另一个为 real，则有的语言会以类型不相容做出错处理，而现在大多数语言的算术表达式中，容许整形和实型数之间的运算。这时，需将整形运算量转换到实型运算量。在翻译中，借助于语义函数 i+r(x),将整形 x转换成实型数。于是相应于 E→E1 op E2 的语义子程序在引进语义变量 E.type后将如图 5.13所示
28
E→E1 op E2
{ t:=newtemp; if（ E1.type=integer and E2.type=integer）
{ E.type:=integer;
emit(t:=E1.place opi E2.place)
}
else if(E1.type=real and E2.type=real）
{E.type:=real;
emit(t:=E1.place opr E2.place)
}
else if（ E1.type=integer）
{ t1:=newtemp;t1:=i+r(E1.place);
emit(t:=t1 opr E2.place);
E.type:=real ；
} else{ t1:=newtemp;t1:=I+r(E2.place);
emit(t:=E1.place opr t1);
E.type:=real;E.place:=t}
图 5.13 允许不同类型间运算的翻译子程序
29
二、数组元素的地址计算分式相同类型的一组数据形成数组。数组总是存放在一片连续单元里。
一维数组的元素是线性序的，所以与所分配的连续空间极易建立一一对应关系。
n维数组 A(n≥2)描述了 n维空间元素集，因此它的数组元素空间必须与一维的线性存贮空间建立起一个一一映射，这样每个数组元素就有了一个唯一确定的存贮位置。当然这种一一映射可能不止一个，例如按行存放和按列存放就是两种不同的映射。按行存放是将第一维看成最高位，第 n
维看成是最低位。设第 i维的下界为 lowi上界为 highi则将第
i位看成是 di=highi-lowi+1进制成的，那么这是个 n位的，
每一位是 di，进制的计数器，就给出了将这 n维空间的元素映射成一个线性序的一维空间的一个函数。初始元素 A0
为 A[low1,low2,…,lown],元素 A[i1,i2,…in] 是 A0后的第
L个元素。
30
L＝ (i1-low1)*d2*d3*…*dn+(i2 -low2)*d3*d4
*…*dn+…+(in -1－ lown-1)*d1+in－ lown (5.1)
其中 di=highi-lowi+1(i=1,2,…,n) (5.2)
如果每个元素的存贮宽度为 W,A0的存贮位置为 base，则：
A[i1,i2,…in] 的存贮位置 D为：
D ＝ base+L*W
＝ base-((…((low1*d2+low2)*d3+low3)…)
dn+lown)*W+((…((i1*d2+i2)*d3+i3)…)
dn+in*W (5.3)
因为 base是个相对地址，所以 D也是个相对地址，公式 (5.3)
为数组元素的地址计算公式。
令 C＝
((…((low1*d2+low2)*d2+low3)…)*dn+lown)*W
AVRPART=((…((i1*d2+i2)*d3+i3)…)*dn+in)*W
则 D=base-C+VARPART (5.4)
31
显然一维，二维数组是上述公式的特例。
一维数组元素 A[i]的相对地址为：
D＝ base+(i-low)*W=base-C+i*W
这里 C=low*W
二维数组元素 A[i1,i2]的相对地址为：
D＝ base+((i1-low1)*d2+i2-low2)*W
=base-C+(i1*d2+i2)*W
这里 C=(low1*d2+low2)*W
32
三、含数组元素的变量的访问赋值语句中出现的变量既可以是简单变量也可以是数组元素 (或称下标变量 )，其语法可由下列产生式描述：
V→id[Elist]|id
Elist→Elist,E|E
其中 id或为数组名，或为简单变量名,Elist是由下标表达式组成的下标表。在翻译时要确定数组元素的位置，需要知道该数组的 base和 C及每一维的长度 di，然后根据公式
(5.4)，可计算该数组元素的相对地址，但是 base,C和 di
的信息都在相应于数组名 id的内情向量中，为了在用
Elist→Elist,E|E归约时能得到 id表项中上述信息，因此将上述文法改写为：
V→Elist]|id
Elist→Elist,E|id[E
33
由产生式 Elist→id[E 归约时即可将 id的表项位置作为 Elist
的一个综合属性 Elist.array的值。以后每当用产生式
Elist→Elist,E归约一次，就处理这一维的地址计算 (即
ej=ej-1*dj+ij)同时将 Elist.array这个属性值一直传递下去，
直至最后由 V→Elist] 归约时止。
一个数组元素的地址是由数组零地址 base-C和这个元素相对于零地址的偏移量组成，它们分别由 V.place和 V.offset记录着。对简单变量而言，它的地址则由 V.place记录着，而
V.offset则恒置为 null，这可作为翻译中对简单变量和下标变量的一种识别或区分。
34
四、含数组元素的赋值语句的翻译方案相应的文法为：
1 S→V:=E
2 E→E1 op E2
3 E→(E1)
4 E→V
5 V→Elist]
6 V→id
7 Elist→Elist1,E
8 Elist→id[E
35
翻译方案中的语义动作是这样给出的：
(1) 在表达式中或赋值左部遇到的是简单变量 (也即由
V→id 归约 )或下标变量 (由 Elist→id[E 归约 ]，两者区别当然是名字 id后是否有下标括号 [，当为简单变量时语义动作为,V→id { p:=lookup(id.name)；
if p≠nil then begin V.place:=p；
V.offset:=null end else error}
当为下标变量时，产生式 Elist→id[E 中 id为数组名，由
id.name可查得数组表项位置，同时第一维下标表达式的值已在 E.place中，所以语义动作为：
Elist→id [E { p:=lookup(id.name)；
if （ p≠nil） { Elist.array:=p；
Elist.place:=E.place；
Elist.dim:=1； }
else error}
36
(2) Elist→Elist1,E表明下标变量的下标表已归约了 i-1维，
现遇到第 i维下标表达式 E1，此时需生成乘加的三地址指令：即 ei=ei-1*di+E1，运算后的中间结果保存在 Elist1
place中，第 i维的长度 di可由函数 limit(Elist1 array,i)查得。
注意 Elist1.array指出数组名的表项位置。
Elist→Elist1,E { t:=newtemp； i:=Elist.dim+1；
emit(t?:=?Elist1.place*limit(Elist1.array,i))； }
emit(t?:=?t+e.place)；
Elist.array:=Elist1.array；
Elist.place:=t；
Elist.dim:=i}
37
(3) 由 V→Elist] 归约时，数组元素的下标表结束，这时下标变量的 base-C及 VARPART或由数组的符号表项
(Elist.array指出 )查得，或通过计算得到，它们分别保存在
V.place和 V.offset中。
V→Elist] { V.place:=newtemp；
V.place?:=base-C)；
V.offset:=newtemp；
emit(V.offset?:=?Elist.place?*?W)}
38
(4) 对于表达式中的变量，按简单变量或下标变量分别处理：
E→V { if V.offset =null then
E.place:= V.place
else begin
E.place:=newtemp；
emit(E.place?:=?V.place[V.offset])
end}
表达式中对数组元素的引用，需要的是 V的右一值。故生成的三地址指令 E.place:=V.place [V.offset]这是变址取类型的指令。
39
（ 5） 表达式运算及子表达式仍同 § 5.3一：
E→E1 op E2 {E.place:=newtemp ；
emit(E.place:?=?E1.place?op?E2.place)}
E→(E1) {E.place:=E1.place}
(6) 赋值语句的左部变量可能为简单变量，也可能为下标变量，若 V为下标变量时，需要 V的左一值，生成三地址指令就是变址存贮的形式：
V.place [V.offset]:=E.place
故有 S→V:=E { if （ V.offset=null）
emit(V.place:?=?E.place)
else
emit(v.place[V.offset]?:=?E.place)}′
40
[例 5.1] 一个 10′20的数组 A(d1=10,d2=20)，设 W=4，
low1=low2=1，即 A[1,1]为数组的第一个元素，则
C=(low1*d2+low2)*W=84，如果赋值语句为 x:=A[y,z]，
则它的带注释的语法分析树如 5.14所示。
根据自下而上的翻译方案，赋值语句 x:=A[y,z]被翻译成下列三地址语句序列：
t1:=y*20
t1:=t1+z
t2:=A-84
t3:=4*t1
t4:=t2[t3]
x:=t4
翻译中 id.place均直接用相应的名字来代替。
41
z
s
:=V.place=x
V.offset=n
ullx
E.place=t1
…
V.place=t2
V.offset=t3
Elist.place
=t1
Elist.dim=
2
Elist.array
=A
Elist.place
=y
Elist.dim=
1
Elist.array
=A
,E.place=x
…
V.place=z
V.offset=n
ullA [ E.place=y…
V.place=y
V.offset=n
ully
图 5.14 赋值语句 x:=A[y,z]的带注释的分析树
]
42
§ 5.5 控制流语句一、布尔表达式的两种基本作用在程序语言中布尔表达式 E有两个基本作用：
参于逻辑运算，如 E?E或?E。
作控制语句的条件式，如 if E then S或 while E do S。
布尔表达式是由布尔运算符 and,or,not(亦可为?,?、
)作用于布尔变量 (或布尔常量 )或关系表达式而形成的，
关系表达式的形式为 E1 relop E2，其中 E1,E2为算术表达式,relop为关系运算符如 <,?,=,?,>,?，由属性
relop.op确定。
我们只考虑下列文法所产生的布尔表达式：
E?E and E|E or E|not E|(E)|id relop id|id|true|false
(5.5)
为消除上述文法的二义性，按通常习惯规定,or,and
为左结合的，优先顺序由高到低依次为 not,and,or。而关系运算符的优先级均相同，并且高于任何布尔运算符，
而低于任何算术运算符，关系运算符不得结合，如
A=B>C是不符合文法的。
43
二、布尔表达式的两种翻译方法第一种方法为数值表示法：以 0表示 false,1表示 true，
并像计算算术表达式那样根据优先级结合律逐步计算出表达式的逻辑值，例如布尔表达式：
1 or not 0 and 0 or 0 的计算过程为
1 or not 0 and 0 or 0=l or 1 and 0 or 0
=1 or 0 or 0
=1 or 0
=1
第二种方法为解释法。例如，布尔表达式 E1 or E2，如果 E1为 true则不管 E2的值如何布尔表达式肯定为 true，
只有 E1为 false时,E2的值即为布尔表达式 E的值。与数值表示法相比，运算次数有可能减少，因而可能是一种优化。这种方法是将 or,and,not这三个逻辑运算用 if-
then-else来解释：
将 A or B解释为 if A then true else B；
将 A and B解释为 if A then B else false；
将 not A解释为 if A then false else true。
44
三、数值表示法翻译方案用 0表示 false,1表示 true像算术表达式那样根据优先级，
结合律从左到右去示值，则布尔表达式 a or b and not c将被翻译成如下三地址语句序列：
t1:=not c
t2:=b and t1
t3:=a or t2
对于表达式 a<b由 if a<b then 1 else 0来确定它的值 (0或 1)，
相应的三地址语句序列为：
100,if a<b goto 103
101,t:=0
102,goto 104
103,t:=1
104：
然后像布尔量一样参于布尔表达式的运算。
45
产生布尔表达式三地址代码的翻译方案示于图 5.13，其中由 nextcode指向当前将生成三地址语句位置，显然 emit
生成一三地址语句并送到三地址语句表后 nextcode需增 1。
我们约定：这种情况的 nextcode增 1是恰在过程 emit返回前完成的。
46
E→E1 or E2 { E.place:=newtemp ；
emit(E.place ‘:=’ E1.place ‘or’ E2.place)}
E→E1 and E2 { E.place:=newtemp ；
emit(E.place ‘:=’ E1.place ‘and’ E2.place)}
E→not E1 { E.place:=newtemp ；
emit(E.place ‘:=’ ‘not’ E1.place)}
E→(E1) { E.place:=E1.place}
E→id1 relop id2 { E.place:=newtemp ；
emit (‘if’ id1.place relop.op id2.place
‘goto’ nextcode+3)；
emit(E.place ‘:=’ ’0’)；
emit(‘goto’ nextcode+2)；
emit(E.place ‘:=’ ’1’)}
47
E→id { E.place:=newtemp ；
emit(‘if’ id.place ‘goto’ nextcode+3)；
emit(E.place ‘:=’ ‘0’)；
emit(‘goto’ nextcode+2)；
emit(E.place ‘:=’ ‘1’)}
E→true { E.place:=newtemp ；
emit(E.place ‘:=’ ‘1’)}
E→false { E.place:=newtemp ；
emit(E.place ‘:=’ ‘0’)}
图 5.15 布尔表达式数值表示的翻译方案
48
[例 5.4] 对布尔表达式 a<b or c=d and not e>f生成三地址代码，由图 5.15的翻译方案可得下列三地址代码：
100,if a<b goto 103 108,if e>f goto 111
101,t1:=0 109,t3:=0
102,goto 104 110,goto 112
103,t1:=1 111,t3=1
104,if c=d goto 107 112,t4:=not t3
105,t2:=0 113,t5:=t2 and t4
106,goto 108 114,t6:=t1 or t5
107,t2:=1
49
五、控制流语句中布尔表达式的翻译控制流语句中的布尔表达式 E按照控制转移的解释翻译方法，它将被翻译成一系列的条件转移和无条件转移的三地址代码。不管由这些转向语句组成的代码序列有多长，作为布尔表达式，最终总是综合为转向 E的真出口,E.true和 E的假出口 E.false。
作为布尔表达式 E的最基本成分是布尔常量，布尔变量和关系表达式，由它们最早产生的转向真出口或转向假出口的语句，分别为：
50
(1) E→id1 relop id2,(这里 id1,id2均为算术量，
relop为关系运算符 )E,if id1 relop id2 goto E.true
goto E.false
(2) E→id( 这里 id是个布尔变量 )E,if id goto E.true
goto E.false
(3) E→trueE,goto E.true
(4) E→falseE,goto E.false
由于表达式参于表达式运算时，则依据逻辑运算符将子表达式的真出口和假出口综合得到 E的真出口 E.true和 E的假出口 E.false。
51
(5) E→E1 or E2
E1.code to
E1.falseto
E1.true
E2.code
E.code
E1.false:
to
E2.false
to
E2.true toE.trueto
E.false
52
(6) E→E1 and E2
E1.code to
E1.trueto
E1.false
E2.code
E.code
E1.false,toE
2.falseto
E2.true
to
E.falseto
E.true
53
(7) E→not E1
E1.codeE1.code toE
1.trueto
E1.false
to
E.falseto
E.true
54
当判定 E1为真时，需为 goto E.true，但由于 E2尚未翻译，
它的代码长度桅顶，因此 后续为真的转向点自然不得而知，例如：
a<b or c<d and not e<f
在 nextcode为 100的假定下按上述代码结构，他可以生成三地址代码为
100 if a<b goto E.true
101 goto 102
102 if c<d goto 104
103 goto E.false
104 if e<f goto E.false
105 goto E.true
55
当翻译 a<b时，它可以生成 100,101二个语句。
但 101,goto E.true这 E.true究竟在何处，这完全依赖 or后的表达式结构，在翻译当时无法确定。我们把在翻译过程中有相同的转向（其实只有 E.true、
E.false两种不同转向）而当时又不能确定具体转向点的三地址语句勾连成一条链，最先生成的链上的三地址语句 L1转向点用 0表示为链尾是，即
L1,goto 0
56
其次生成的链上的三地址语 L2，其转向点用 L1表示，即：
L2,goto L1
依次类推，最后生成的三地址语句便为 Ln：
L1,… goto 0;
…
L2,… goto L1;
…
Ln-1:…goto Ln -2
…
Ln:… goto Ln
图 5.16 有相同转向点的语句链
57
(1) E→E1 or M E2 { backpatch(E1.falselist,M.code);
E.trulist:=merge(E1.truelist,E2.truelist);
E.falselist:=E2.falselist}
(2) E→E1 and M E2{ backpatch(E1.truelist,M.code);
E.falselist:=merge(E1.falselist,E2.falselist);
E.truelist:=E2.truelist}
(3) E→not E1 { E.truelist:=E1.falselist;
E.falselist:=E1.truelist;}
58
(4) E→(E1) { E.truelist:=E1.truelist;
E.falselist:=E1.falselist;}
(5) E→id1 relop id2 { E.truelist:=makelist(nextcode);
emit(if id1.place relop id2.place goto 0);
E.falselist:=makelist(nextcode);
emit(goto 0)}
59
(6) E→id { E.truelist:=makelist(nextcode);
emit(if id.place goto 0);
E.falselist:=makelist(nextcode);
emit(goto 0)}
(7) E→true { E.truelist:=makelist(nextcode);
emit(goto 0)}
(8) E→false {E.falselist:=makelist(nextcode);
emit(goto 0) }
(9) M→ε { M.code:=nextcode}
图 5.17 布尔表达式的翻译方案
60
[例 5.5] 用回填技术完成 a<b or c<d and not e<f 的翻译，设
nextcode为 100。翻译的注释分析树如图 5.18所示。
d
orE1.truelist=10
0
E1.falselist=10
1 ε
E5.truelist=10
5
E5.falselist=10
4
E2.truelist=10
2
E2.falselist=10
3
E4.truelist=10
5
E4.falselist=10
4<c
图 5.18 a<b or c<d and not e<f 的翻译分析树
an
d
E.truelist=105
E.falselist=10
4
M1.code=102
M2.code=104
ε
not E3.truelist=10
4
E3.falselist=10
5 f<e
b<a
61
生成的三地址代码为：
100 if a<b goto 0
101 goto 102
102 if c<d goto 104
103 goto 0
104 if e<f goto 103
105 goto 100
同时有 E.truelist=105,E.falselist=104。待该布尔表达式后续部分翻译过程中确定 E为真的转向地址时，
按链头 105的 E.truelist来回填转向语句的转向点；
确定 E为假的转向地址时，按链头为 104的
E.falselist来回填转向语句的转向点。因此，上述三地址代码并非最后生成的中间代码，其中挂在链上的转向语句，是尚未完成的语句。其转向点只是链的连接元，并非是真实的转向地址。
62
五,控制流语句的翻译这里只讨论下列文法所指定的控制流语句：
(1)S→if E then S1
(2) | if E then S1 else S2
(3) | while E do S1
(4) | begin L end
(5) | A
(6)L→L ; S
(7) |S
其中 A为赋值语句,L为语句表,所以 begin L end为复合语言,它的语法地位同其它一般语句 。 如果文法中相当 S位置上不能由一个语句,而需要由一串语句 （ 即语句表 ） 来描述时,用语句括号把语句表 L括起来,就可以作为一个语句对待了 。
63
产生式 (1),(2),(3)的目标代码结构分别如图 5.16之 (a)、
(b),(c)所示。
E.code to E.true
to S.next (to
E.false)
S1.codeE.true:
(if-then
E.code to E.true
to
E.false
S1.codeE.true:
(if-then-else
goto
S.next
to S.next
S2.codeE.false:
E.code
S1.code
goto
S.begin
E.true:
S.begin,to E.true
to S.next
(wile-do
图 5.16 控制流语句的目标代码结构
64
(1)S→ if E then M S1 { bakpatch(E.truelist,M.code);
S.nextlist:=merge(E.falselist,S1.nextlist)}
(2)F→ if E then M S1 else
{ backpatch(E.truelist,M.code);
t:=makelist(nextcode);
emit(goto,0);
F.nextlist:=merge(S1.nextlist,t);
backpatch(E.falselist,nextcode)}
(3)S→ F S1 { S.nextlist:=merge(F.nextlist,S1.nextlist)}
(4)S→ while M1 E do M2 S1
{ backpatch(E.truelist,M2.code);
backpatch(S1.nextlist,M1.code);
emit(goto,M1.code);
S.nextlist:=E.falselist}
65
(5) S→ begin L end { S.nextlist:=L.nextlist}
(6) S→ A { S.nextlist:=makelist()}
(7) L→ L1; M S { backpatch(L1.nextlist,
M.code);
L.nextlist:=S.nextlist}
(8) L→ S { L.nextlist:=S.nextlist}
(9) M→ ε { M.code:=nextcode}
图 5.17控制流语句的翻译方案
66
[例 5.5] 有下列语句序列
if a<b or e<d and not e<f then A1 else A2;
while a<b do A3
其中 A1,A2,A3均为赋值语句,这里不予展开 。 假定它们生成 10个三地址语句,它们的代码均以方框来表示 。 这里有二个语句,并组成一个语句表,主要涉及：
F→ if E then M S1 else
S→ F S1
S→ while M1 E do M2 S1
L→ S
L→ L1; M S
产生式及相应的语义动作 。 假定翻译开始时
nextcode=100。
67
(1) 布尔表达式 a<b or c<d and not e<f的代码在例
5.5生成了代码：
100,if a<b goto 0
101,goto 102
102,if c<d goto 104
103,goto 0
104,if e<f goto 103
105,goto 100
以及二条链 E.truelist=105,E.falselist=104,它们各自有 105,100二个语句及 104,103二个语句 。
(2) 在 then后有一次 M→ε 归约,M.code=106；它恰为 A1代码开始位置 。
(3) A1经归约后生成的代码为,106,A1.code
116:
68
(4) 识别 else后,应按 F→ if E then M A1 else归约,
这时有语义动作,backpatch(E.truelist,M.code),即以 105为链头的 E.truelist,用 106回填,故 100,105语句的转向点均为 106,生成语句
116,goto 0
并将 116与 S1.nextlist（ 即 A1的空链 ） 两条链合并,
成为 F.nextlist,这条链上只有 116一个语句,用现在的 nextcode=117 回填 E.falselist,
badkpatch(E.false,117)。 故 104,103的转向点均为
117。
(5) 识别 A2后,即用产生式 S→F S1归约后,因为
S1即 A2的 S1.nextlist为空链,故 S.nextlist=F.nextlist即
116,而 A2的代码为,117,A2.code
127:
69
(6) L→S 后 L.nextlist:=116,识别；后 M→ ε归约将当时 nextcode=127记录在 M.code中 。
(7) while M1 a<b do M2 A3 时,
M1.code=127,M2.code=129生成的代码为,
127:if a<b goto
128,goto 0
129:A3.code
139,goto 127
并形成 S.nextlist=128的语句出口链 。
(8) 用 L→L 1; M S 归 约 时,
backpatch(L1.nextlist,M.code),即以 116 为 链 头 的
L1.nextlist,用 M.code=127回填,使 116语句为 goto
127；同时 L.nextlist:=S.nextllist为 128。
最后有 L.nextlist=128。
70
§ 5.6 循环语句、过程调用语句及 CASE语句一,循环语句的翻译有一类循环语句可以用下列文法来描述：
S→ for i:=1 to N do S1
其中 i为循环变量,它的循环初值和终值分别为１
和 N,都是常量,其语义为：
i:=1; L,i:=1
again,if i<=N then L+1,if i>N goto S.nextlist
begin S1; L+2,S1.code
i:=i+1; M,i:=i+1
goto again M+1,goto L+1
end
71
其中,从 L+2开始到 M之前是 S1语句的代码 。 显然在生成 的代码之前,应先生成 i:=1等二个语句 。 也即在发生对 S1的归约之前先发生一次归约,这样才可能调用相应语义子程序,生成这二个语句 。 为此引进辅助非终结符 F,并将文法转换为：
F→ for i:=1 to N do
S→ F S1
相应的翻译方案为
F→ for i:=1 to N do { p:=lookup(i.name);
emit(p,?:=?,?1?);
f.again:=nextcode;
emit(if p,>,?N?,goto 0);
F.place:=p}
S→F S1 { emit(F.place,?:=?,F.place,+,?1?);
emit(goto,F.again);
backpatch(S1.nextlist,F.again);
S.nextlist:=F.again}
72
翻译方案中,属性 F.place记录循环变量的地址,
F.again记录循环入口,S.nextlist,记录了循环出口语句的位置,待 S的后续语句的位置确定后再回填由 S.nextlist指出的转向语句的转向地址 。
在上述翻译方案中,我们通过改写文法而不是通过插入标记非终结符的办法来完成翻译的 。 因为在
do后插入标记非终结符 M虽然在分析到此时刻,可以增加 M→ε 的归约,但是生成二个语句的语义动作不可能由 M→ε 时获得 。 目前采取的分两段归约的做法有更强的可适用性 。
