第七章语义分析和中间代码的产生

第七章

语义分析和中间代码的产生上海电力学院彭源内容7.1中间代码的形式7.2说明语句的处理7.3赋值语句的翻译(表达式、数组的翻译）7.4布尔表达式的翻译7.5控制语句的翻译(if、while、switch)

何谓中间代码：

源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。可以使编译程序的结构清晰、简单、明确。

为什么要此阶段及使用原则形式简单、语义明确、便于翻译独立于目标语言。

中间代码的几种形式后缀式,三地址代码(包括三元式/四元式/间接三元式),DAG图表示,抽象语法树表示

7.1中间代码(源程序的中间形式)7.1.1后缀式（逆波兰式）将运算对象写在前面，把运算符号写在后面表达式逆波兰式a+ba+b*c(a+b)*ca=b*c+b*dab+abc*+ab+c*abc*bd*+=一个表达式的后缀式可以如下定义：

（1）如果E是一个变量或常量，则E的后缀式是E自身。（2）如果E是E1opE2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’op,这里E1’和E2’分别为E1和E2的后缀式。（3）如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。可见后缀式中用不到括号后缀式的计算机处理后缀式的最大优点是易于计算机处理处理过程： 从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈顶。

bt1dct1t2t1t3t1=-bt2=c*dt3=t1+t2例：表达式－b＋c*d的后缀式b@cd*+的计值过程把表达式翻译成后缀式的语义规则产生式语义规则E->E1opE2E.code:=E1.code||E2.code||opE->(E1)E.code:=E1.codeE->idE.code:=id说明:E1,E2,E为同一个文法符号,加下标只是为了在定义语义规则的时候区分不同位置的E77a+b的中间代码生成过程：步骤 符号 输入串 语义动作1 ＃ a+b# 初始化2 ＃a +b# 3 ＃E +b# E.code:=“a”4 ＃E+ b# 5 ＃E+b # 6 ＃E+E1 # E1.code:=“b”7 ＃E # E.code:=“ab+”产生式语义规则E->E1opE2E.code:=E1.code||E2.code||opE->(E1)E.code:=E1.codeE->idE.code:=id逆波兰(后缀式)表示法的扩充

逆波兰法很容易扩充到表达式以外的范围 例如：语句逆波兰表示备注a:=b+cGOTOLIfEthenS1elseS2:=看作二目运算符jmp看成一目运算符，表示GOTO把￥看成三目运算符，表示if–then–elseabc+:=LjmpES1S2￥7.1.2图表示法包括DAG与抽象语法树。抽象语法树:

操作符和关键字都不作为叶节点出现,而是把它们作为内部节点即叶节点的父节点.S->ifBthenS1elseS2If_then_elseBS2S1=a+**bcbdSaETTbcbd**+=Ea=b*c+b*d7.1.2图表示法无循环有向图（DirectedAcyclicGraph,简称DAG):

与抽象语法树一样，对于表达式中的每个子表达式，DAG图中都有一个结点。一个内部结点代表一个操作符，它的孩子代表操作数。两者不同的是，在一棵抽象语法树中公共子表达式被表示为重复的子树，而在DAG图中代表公共子表达式的结点具有多个父结点。即:

把抽象语法树中的公共部分合并起来=a+**bcbd=a+**bcda+a*(b-c)+(b-c)*d+a+**a--dbcbc++**a-dbcE->E+T|E-T|TT->T*F|FF->(E)|i7.1.3三地址代码

三地址代码是由下面一般形式的语句构成的序列:

X:=yopz

其中，x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号如定点运算符、浮点运算符、逻辑运算符等。每个语句的右边只能有一个运算符。例如:x+y*z的三地址代码:t1:=y*zt2:=x+t1例如:a+a*(b-c)+(b-c)*d的三地址代码:t1:=b-ct2:=a*t1t3:=a+t2t4:=b-ct5:=t4*dt6:=t3+t5+a+**a--dbcbc++**a-dbct1:=b-ct2:=a*t1t3:=a+t2t5:=t1*dt6:=t3+t5例：表达式a+(-b*c+d)*e的三地址代码为：

t1:=-bt2:=t1*ct3=t2+dt4=t3*et5=a+t4三地址语句的种类:种类：x:=yopz双目运算

x:=opy单目运算

x:=y赋值

ifagotoL条件转移

ifa>bgotoLgotol无条件转移

paramx实在参数

callp,n(n是参数个数)过程调用

returnx过程返回

x:=y[i] 数组运算

x[i]:=yx:=&y 指针运算

x:=*y*x=y三地址代码是中间代码的抽象形式,其具体实现可用记录表示,记录中包含表示运算符和操作数的域。有以下三种表示方法:三元式四元式间接三元式四元式是一个带有四个域的记录结构，格式如下：

(算符,第一运算对象,第二运算对象,结果)如：a=b*c+b*d

(1) (*,b,c,t1)

(2) (*,b,d,t2)

(3) (+,t1,t2,t3)

(4) (=,t3,-,a)三元式格式：

(算符,第一运算对象,第二运算对象)例：A+B*C可表示成：

(1)(*,B,C)

(2)(+,A,(1))特点：

(1)把存放结果的单元推迟到代码生成阶段；

(2)在格式上比四元式紧凑，节省空间；

(3)三元式不利于优化。例：a+b*(c-d)-e/f**g(1)(-,c,d)(2)(*,b,(1))(3)(+,a,(2))(4)(**,f,g)(5)(/,e,(4))(6)(-,(3),(5))(1)(-,c,d)(2)(*,b,(1))(3)(**,f,G)(4)(/,e,(3))(5)(-,(2),(4))(6)(+,a,(5))E->E+T|E-T|TT->T*F|T/F|FF->F**M|MM->(E)|iE->E+E|E-E|TT->T*T|T/T|FF->F**F|MM->(E)|i多目运算的三元式表示x[i]:=yoparg1arg2(0)=[]xi(1)assign(0)yx:=y[i]oparg1arg2(0)[]=yi(1)assignx(0)间接三元式为了便于优化(1)三元式表，登记迄今生成的所有三元式；(2)操作码表(间接码表)，按引用三元式的顺序存放三元式在三元式表中的序号。如：X:=(A+B)*C;Y:=D↑(A+B)

三元式表(1)(+,A,B)(2)(*,(1),C)(3)(:=,X,(2))(4)(↑,D,(1))(5)(:=,Y,(4))操作码表(1)(2)(3)(1)(4)(5)练习7.1选择题：

(1)四元式之间的联系是通过

实现的。

a.指示器

b.临时变量

c.符号表

d.程序变量

(2)间接三元式表示法的优点为

。

a.采用间接码表，便于优化处理

b.节省存储空间，不便于表的修改

c.便于优化处理，节省存储空间

d.节省存储空间，不便于优化处理7.2将下列中缀式改写为逆波兰式：(-A*(B+C))^(D-E)((a*d+c)/d+e)*f+ga+x≦4∨(c∧d*3)(┐A∨B)∧(C∨D)解：A-BC+*DE-^ad*c+d/e+f*g+ax+4≦cd3*∧∨A┐B∨CD∨∧7.3将下列表达式分别用逆波兰式、DAG图、三地址语句、及三地址语句的三种具体实现方法：三元式、间接三元式、四元式表示:A+B*(C-D)+E/(C-D)^N逆波兰:ABCD-*+ECD–N^/+DAG图：

A+*BC-D^N/E+三地址码:T1:=C-DT2:=B*T1T3:=A+T2T4:=C-DT5:=T4^NT6:=E/T5T7:=T3+T6四元式:(1)(-CDT1)(2)(*BT1T2)(3)(+AT2T3)(4)(-CDT4)(5)(^T4NT5)(6)(/ET5T6)(7)(+T3T6T7)

A+B*(C-D)+E/(C-D)^N三元式:(1)(-CD)(2)(*B(1))(3)(+A(2))(4)(-CD)(5)(^(4)N)(6)(/E(5))(7)(+(3)(6))

间接三元式:(1)(-CD)(2)(*B(1))(3)(+A(2))(4)(^(1)N)(5)(/E(4))(6)(+(3)(5))

间接码表：

(1)(2)(3)(1)(4)(5)(6)A+B*(C-D)+E/(C-D)^N赋值语句的语义规则S→id:=E{p:=lookup(); ifp<>nilthenemit(:=,E.place,,p) elseerror}E→E1+E2{E.place=newtemp; emit(+,E1.place,E2.place,E.place)}说明：newtemp：函数，返回一临时变量序号；

lookup(i)：函数，查找变量i的入口地址；

emit(OP,ARG1,ARG2,RESULT)：语义过程，产生一个四元式，并填入四元式表；

E.place：与E相关的语义变量，可能是某变量的入口地址，或者为临时变量序号等。7.3赋值语句的语义翻译（接上页）

E→E1*E2{E.place=newtemp; emit(*,E1.place,E2.place,E.place)}E→-E1{E.place:=newtemp;emit(-,E1.place,,E.place)}

E→(E1) {E.place:=E1.place}

E→id {p:=lookup(); ifp<>nilthenE.place:=p elseerror}

E→num{E.place:=num}语义翻译过程用自下而上的分析方法。最终所得的语义动作如下：1.E11.place:=P(注：指向->c)2.(-,E11.place,,E1.place)

3.E21.place:=P(注：指向->b)4.E22.place:=345.(*,E21.place,E22.place,E2.place)6.(+,E1.place,E2.place,E.place)

7.(:=,E.place,,P(注：指向->a))例：翻译a:=-c+b*34

翻译中的其他问题类型转换:表达式中，可能出现不同类型的变量或常量进行运算，编译程序必须做到拒绝接受混合运算或者产生有关类型转换的指令。若允许混合运算，则需对语义规则进行扩充。用E.MODE表示E的类型，其值为r(实型)或int(整型)。如：产生式E->E1opE2的语义动作中关E.MODE的规则可定义为：

IFE1.MODE=intandE2.MODE=int

THENE.MODE=intELSEE.MODE=real另需生成一个类型转换的四元式：

(inttoreal,A1,--,T)类型转换如：X:=Y+I*J，X,Y为实型，I,J为整型，则相应的四元式序列应为：

(*int,I,J,T1)

(inttoreal,T1,--,T2)

(+real,Y,T2,T3)

(:=,T3,--,X)数组元素引用(1)按行存放(2)按列存放如：A:array[1:2,1:3]

A[1,1]A[1,2]A[1,3]A[2,1]A[2,2]A[2,3]A[1,1]A[2,1]A[1,2]A[2,2]A[1,3]A[2,3]数组元素地址的计算设A是一个二维数组，每个元素占w个字节。若按行存放，则A[i1,i2]地址为：

base+((i1-low1)*n2+i2-low2)*w若按列存放，则A[i1,i2]地址为：

base+((i2-low2)*n1+i1-low1)*w可推广到n维数组。数组A的起始地址行标下界列宽列标下界Low1,low2i1,i2行高n1列宽n2数组引用的中间代码形式以二维数组按行存放为例：A[i1,i2]地址＝base+((i1-low1)*n2+i2-low2)*w＝base-(low1*n2+low2)*w

+(i1*n2+i2)*w则可用基址[变址]来表示数组元素的地址。同理：按列存放时候A[i1,i2]地址＝base+((i2-low2)*n1+i1-low1)*w＝base-(low2*n1+low1)*w

+(i2*n1+i1)*w基址变址数组翻译举例A是一个10*20数组，首地址为A。下标从１开始，按行存储，元素长度为４。那么X:=A[i,j]的中间代码序列为（语义规则定义见书page182）：T1:=i*20T1:=T1+jT2:=A-84T3:=4*T1T4:=T2[T3]X:=T4base-(low1*n2+low2)*w+(i1*n2+i2)*w将下列赋值语句翻译成三地址代码(下标从0开始，按行存储，行列宽为10，A,B,C,D为数组的首地址，数组元素宽度为4）：A[i,j]:=B[i,j]+C[A[k,1]]+D[i+j]t1:=i*10t1:=t1+jt2:=At3:=4*t1t4:=i*10t4:=t4+jt5:=Bt6:=4*t4t7:=t5[t6]t8:=k*10t8:=t8+1t9:=At10:=4*t8t11:=t9[t10]t12:=Ct13:=4*t11t14:=t12[t13]t15:=t7+t14t16:=i+jt17:=Dt18:=4*t16t19:=t17[t18]t20:=t15+t19t2[t3]:=t20base-(low1*n2+low2)*w+(i1*n2+i2)*w数组vara:array[1..10,1..20]ofreal;按列存放，其首址addA,每个实数占８个字节编址，则语句b:=x+a[i,j];

的四元式序列是什么？*j10t1+it1t1-addrA88t2*8t1t3[]=t2t3t4+xt4t5:=t5_bbase-(low2*n1+low1)*w+(i2*n1+i1)*w例:数组A:array[2…10,3…8];B:array[-3,3],按列存放,A的首地址为100,每个元素占2个字节;B的首地址为200,每个元素占1字节编址;

对于语句A[m+1,n+2]:=A[B[k+2],5]求:B[k+2]的地址求:A[m+1,n+2]的地址将该语句翻译成四元式子序列解:1.=base-low*w+i*w=200-(-3)*1+(k+2)*1=205+k2.=base-(low2*n1+low1)*w+(i2*n1+i1)*w=100-(3*9+2)*2+((n+2)*9+m+1)*2

=80+(m+9n)*2

例:数组A:array[2…10,3…8];B:array[-3,3],按列存放,A的首地址为100,每个元素占2个字节;B的首地址为200,每个元素占1字节编址;

对于语句A[m+1,n+2]:=A[B[k+2],5]求:B[k+2]的地址求:A[m+1,n+2]的地址将该语句翻译成四元式子序列解:3.(+,m,1,t1)(+,n,2,t2)(*,t2,9,t3)(+,t3,t1,

t3)(-,100,58,t4)(*,2,t3

,t5

)base-(low2*n1+low1)*w+(i2*n1+i1)*w(+,k,2,t6)(-,200,-3,t7)(*,t6,1,t8)([]=,t7,t8,t9)(*,5,9,t10)(+,t10,t9,t11)base-low*w+i*w(-,100,58,t12)(*,2,t11,t11)([]=,t12,t11,t13)(=[],t4,t5

,t14)(:=,t13,_,t14)课后作业：将上三题改为按列(第二题按行)存放，给出相应的答案．7.4布尔表达式的翻译关系表达式：形如E1relopE2的表达式，其中E1,E2为算术表达式，relop为关系运算符（<,>,<=,>=,!=）布尔表达式：用布尔运算符(and,or,not)作用到布尔变量（常量）或关系表达式上而组成的表达式。文法如下：

E－>EandE|EorE|notE|(E)|id|ErelopE布尔表达式的作用用于计算逻辑值用于控制语句之中的条件表达式，如if-then，if-then-else和while-do等之中的条件表达式7.4布尔表达式的翻译用于计算逻辑值时的翻译用数值表示真和假，对布尔表达式的求值可以象对算术表达式的求值那样一步一步地来计算。两者的翻译过程非常相似。如：AorBandnotC翻译成三地址代码为：T1:=notCT2:=BandT1T3:=AorT27.4布尔表达式的翻译用于计算逻辑值时的翻译对于关系表达式

arelopb可等价的解释成:

ifarelopbthen1else0如a<b翻译成三地址代码序列：

100：ifa＜bgotol03101：t：=0102：gotol04103:t:=1104：100:ifa<bgoto103101:t1:=0102:goto104103:t1:=1104:ifc<dgoto107105:t2:=0106:goto1087.4布尔表达式的翻译例：a<borc<dande<f翻译成三地址代码序列：107:t2:=1

108:ife<fgoto111109:t3:=0110:goto112111:t3:=1112:t4:=t2andt3113:t5:=t1ort47.4布尔表达式的翻译用于条件控制的布尔表达式的翻译

作为条件的布尔表达式作用仅在于控制对S1和S2的选择。控制语句S®ifEthenS1

elseS２

out:

把作为转移条件的布尔表达式E翻译成一系列的跳转指令（条件真转和无条件转）的四元式E.

true:S1的代码goto

outE.false:S2的代码E的代码E.

true:E.false:E1.codeE2.codeE.code:E1.codeE2.codeE.code:控制语句中的布尔表达式（1）E→E1andE2truefalsetruetoE.truetoE.falsetruetoE.truefalsetoE.falsefalsetoE.false（2）E→E1orE2

falsetoE.truetrue控制语句中的布尔表达式（3）E→notE1

（4）E→(E1)

E1.codetruefalseE.codetoE.falsetoE.true

E1.codetruefalseE.codetoE.truetoE.false控制语句中的布尔表达式（5）E→id1relopid2（relop为关系运算符）

（6）E→true

（7）E→falseE.codeifid1relopid2thengotoE.truegotoE.falsetoE.falsetoE.trueE.codegotoE.truetoE.trueE.codegotoE.falsetoE.false如某控制语句中的条件：a<borc<dande<f可翻译成如下代码：

ifa<bgotoE.truegotoL1L1:ifc<dgotoL2gotoE.falseL2:ife<fgotoE.truegotoE.false

…E.ture:…GotooutE.false:…Out:

如if(a<borc<dande<f)a=1elseb=1;可翻译成：100:(j<,a,b,107)102:(j,_,_,103)103:(j<,c,d,105)104:(j,_,_,109)105:(j<,e,f,107)106:(j,_,_,109)107:(:=,1,_,a)108:(j,_,_,109)109:(:=,1,_,b)110:在生成100这条四元式的时候，最后一个域(指向107的指针)怎么得来的？暂时不能确定

100:(j<,a,b,＿＿)102:(j,_,_,＿＿)

103:(j<,c,d,＿＿)104:(j,_,_,＿＿)105:(j<,e,f,＿＿)106:(j,_,_,＿＿)107:(:=,1,_,a)108:(j,_,_,＿＿)109:(:=,1,_,b)110:当知道了条件为真时和条件为假时分别应做哪些事时就可以进行回填。例重新考虑表达式a＜borc＜dande＜f103105107107109109110回填技术：

记录需回填地址的四元式，把需回填Ｅ．ｔｒｕｅ的四元式拉成一链，把需回填Ｅ．ｆａｌｓｅ的四元式拉成一链，分别称做“真”链和“假”链，并在适当的时候进行回填（１０）…ｇoｔｏＥ．ｔｒｕｅ

…（２０）…ｇｏｔｏＥ．ｔｒｕｅ

…（３０）…ｇｏｔｏＥ．ｔｒｕｅ则链成（１０）…ｇｏｔｏ（０）

…（２０）…ｇｏｔｏ（１０）

…（３０）…ｇｏｔｏ（２０）把地址（３０）称作“真”链链首，０为链尾标志，即地址（１０）为“真”链链尾。例：写出Aand(Bandnot(CorD))的四元式序列，并给出真假链。（1）jnzA_(3)（2）j___（3）jnzB_(5)（4）j__(2)（5）jnzC_（4）

（6）j__(7)（7）jnzD_（5）

（8）j___

（2）真链：（8）（4）->假链：（7）->（5）->例：将下列布尔表达式表示为四元式:A∧(B∨(C∨D∧F)),并给出真假链。（1）jnzA_(3)（2）j___（3）jnzB__（4）j__(5)（5）jnzC_(3)（6）j__(7)（7）jnzD_(9)（8）j__(2)（9）jnzF_(5)（10）j__(8)真链：假链：9->10->235->8->作业写出Aand(BorC)的四元式序列，并给出真假链。四类控制语句：无条件转移：

goto（转向某标号所在位置）

exit、break（退出某个范围）条件转移：

if_then,if_then_else

循环：

while_do：for分支：

switch7.4控制语句的翻译控制流语句的翻译：1.SifEthenS1E.codeS1.codeE.true:...E.false:toE.truetoE.falseifEgotoL1gotooutL1:S1Out:控制流语句的翻译：1.SifEthenS1elseS2E.codeS1.codeE.true:S2.codeE.false

:gotoS.next...S.next:toE.truetoE.falseifEgotoL1gotoL2L1:S1

gotooutL2:S2Out:控制流语句的翻译：2.SwhileEdoS1E.codeS1.codeE.true:E.false:gotoS.begin...S.begin:toE.falsetoE.trueL1:ifEgotoL2gotooutL2:S1gotoL2Out:先记录要回填的转移指令地址，在适当的时候进行回填，以便赋值和布尔表达式的求值得到合适的连接，以完成程序的控制流程。控制流语句的翻译模式：1.SifEthenM1

S1E.codeS1.codeE.true:...E.false:toE.truetoE.falseM1处反填E.true控制流语句的翻译模式：2.SifEthenM1S1NelseM2S2E.codeS1.codeE.true:S2.codeE.false:gotoS.next...S.next:toE.truetoE.falseM1处反填E.trueM2处反填E.falseN出生成

´gotoS.next´控制流语句的翻译模式：2.SwhileM1EdoM2S1NE.codeS1.codeE.true:E.false:gotoS.begin...S.begin:toE.falsetoE.trueM1处生成标号S.beginM2处反填E.trueN处生成gotoS.begin例3：翻译下列语句whilea<bdoifc<5thenwhilex>ydoz:=x+1;elsex:=ywhilea<bdoifc<5thenwhilex>ydoz:=x+1;elsex:=y100ifa<bgoto102；101goto111；102ifc<5goto104；103goto109；104ifx>ygoto106；105goto108；106x:=z+1；107goto104；108goto110；109x:=y；110goto100；E.codeE1.codeS11.codeS12.codeS1.code例其中A1，A2和A3均表示赋值语句