编译原理PPT课件第五章中间代码生成

翻译方式有两种:,第五章中间代码生成,中间代码的特点:结构简单,功能明确,易于优化,易于翻译.,2,第一节中间代码简介,1)逆波兰表示法运算量在前,运算符在后的后缀式表示法.例如:表达式后缀式a+bab+(a+b)*cab+c*a*(b+c)abc+*(a+b)*(c+d)ab+cd+*,3,2)三元式表示法三元式就是三元组:(操作符,操作数1,操作数2)例如:语句D:=A+B*C可翻译为下述三元式表:(1)(*,B,C)(2)(+,A,(1)(3)(:=,D,(2)三元式没有明确指出结果放在何处.,4,3)四元式表示法四元式就是四元组:(操作符,操作数1,操作数2,结果)例如:语句D:=A+B*C可翻译为下述四元式表:(1)(*,B,C,T1)(2)(+,A,T1,T2)(3)(:=,T2,D)四元式间通过临时变量传值.操作符实现的运算也非常简单,本章主要介绍各种语句到四元式的翻译.,5,第二节语法制导翻译的基本思想,1何谓语法制导翻译在语法分析的每次归约或推导时,根据产生式的语义进行翻译的一种方法.翻译时,除了产生中间代码外,还有许多辅助工作,包括:改变语法变量的值;查填符号表;诊查与报告源程序错误等.2与翻译相关的若干约定1)临时变量在翻译中,可能会引入许多临时变量存放中间结果.通过调用newtemp()返回一个临时变量Ti.,6,2)分析栈分析栈中的内容为语法单位,每个语法单位包含两个部分:(语法单位名称,语法单位属性),属性可能有多个值.例如:E为表达式的语法单位,E.place代表了该表达式值存放的地方.3)符号表符号表用于存放变量及属性值,由如干项构成,每个项为:(变量名,变量信息).4)四元式表四元式表用于存放翻译中产生的四元式,通过过程Gen(操作符,操作数1,操作数2,结果)把四元式存入四元式表的NXQ所指空间中,NXQ自动加1.,四元式表,NXQ,7,5一些基本操作,newtemp()产生一临时变量;gen(操作符,操作数1,操作数2,结果)填入四元式表;fill(i,属性)填入符号表;entry(i)查符号表,返回i在符号表中的位置;backpatch(m,n)把n填入四元式表第m个四元式中;,8,第三节简单变量说明语句的翻译,程序设计中,首先应该对程序中使用的变量进行说明.其目的是规定变量所占用空间的大小.编译时,对变量说明语句的翻译工作,本质上就是把变量名及属性登记在符号表中,以便后续工作中使用.pascal语言的简单变量说明语句为:x,y,z:real;语法可表示为:DNAMELIST:TNAMELISTNAMELIST,i|iTinteger|real|boolean|char,该文法代表了所有非结构型变量的说明语句.,9,当然,也可以用如下文法表示:Di:T|i,DTinteger|real|boolean|char我们已经知道用该文法如何分析一个说明语句,下面要解决的是,怎样在分析的过程中,把该语句表达的意思完整的翻译清楚.说明语句的含义是:说明的变量具有给定类型;编译时则翻译为:把每个变量及类型登记在符号表中.语法制导翻译就是为每一条产生式配一个子程序,当用某个产生式归约时,就调用相应的子程序进行适当的翻译工作.这些子程序称为语法单位的语义子程序(或语义动作).,10,下面讨论如下文法的各产生式的语义子程序及翻译过程Di:T|i,DTinteger|real|boolean|char1)TintegerT.att:=integer;2)TrealT.att:=real;3)TbooleanT.att:=boolean;4)TcharT.att:=char;5)Di:TD.att:=T.att;fill(i,T.att);6)Di:DD.att:=D.att;fill(i,D.att);,11,12,第四节简单算术表达式和赋值语句的翻译,简单算术赋值语句的文法可表示为:Si:=EEE+E|E-E|E*E|E/E|(E)|i该文法为二义文法,但如果规定每个终结符的优先关系,并按优先关系进行归约,则可以避免二义性.赋值语句的含义是:计算出E的值,并写入变量i中.编译中,并不关心值是多少,而关心的是怎样计算值的过程;也即,哪些变量参加运算,怎样运算?上面文法的各产生式语义子程序如下:,13,EiE.place:=entry(i)/E.place表示了表达式E的值放在什么变量中E(E1)E.place:=E1.placeEE1+E2E.place:=newtemp()Gen(+,E1.place,E2.place,E.place)EE1-E2E.place:=newtemp()Gen(-,E1.place,E2.place,E.place)EE1*E2E.place:=newtemp()Gen(*,E1.place,E2.place,E.place)EE1/E2E.place:=newtemp()Gen(/,E1.place,E2.place,E.place)Si:=EGen(:=,E.place,entry(i)四元式中的操作数及结果,实质上是一指向变量的指针.,14,示例:x:=y+z,x:=y+z,x:=y,x:=E,x:=E+z,x:=E1+E2,E.place=entry(y),E1.place=entry(y);E2.place=entry(z),+z,+z,x:=E,E.place=T1;Gen(+,y,z,T1),S,Gen(:=,T1,x),15,第五节布尔表达式的翻译,布尔表达式文法可表示为:BnotB|BandB|BorB|(B)|i|EROPEROP|=|该文法也为二义文法,但如果规定每个终结符的优先关系,并按优先关系进行归约,则可以避免二义性.各产生式语义子程序如下:ROP|=|ROP.val=或=或,16,BiB.place:=entry(i)/B.place表示了表达式B的值放在什么变量中B(B1)B.place:=B1.placeBnotB1B.place:=newtemp()Gen(not,B1.place,B.place)BB1andB2B.place:=newtemp()Gen(and,B1.place,B2.place,B.place)BB1orB2B.place:=newtemp()Gen(or,B1.place,B2.place,B.place)BE1ROPE2B.place:=newtemp()Gen(ROP.val,E1.place,E2.place,B.place),17,第六节分支语句的翻译,分支语句包括:ifcase(省略)goto,1if语句的翻译在程序设计种,if语句可以表示为:ifBthenS1elseS2;if语句翻译后,将得到一组四元式,其流程可以表示为:,18,分析是从前向后进行的,按四元式流程的要求,(1)首先归约布尔表达式,产生B的四元式;(2)在归约S1之前,应产生条件转移语句,也即当归约ifBthen时,产生条件转移语句;由于S1S2还未处理,因此,条件转移语句的转移地址未知,只有等到S1处理完毕并产生了无条件转移语句,才能知道条件转移语句转移的确切地址.(3)归约S1;并在归约S1else时,产生无条件转移语句;此时,由于S2未处理,无条件转移语句的转移地址不确定;回填条件转移语句的地址.(4)归约S2;回填无条件转移语句的地址.,*,*,19,从以上分析,可以将文法设计为:STS2TCS1elseCifBthen语义子程序为:CifBthenC.chain:=NXQ;Gen(Jz,B.place,xxxx)TCS1elseT.chain:=NXQ;Gen(J,xxxx);backpatch(C.chain,NXQ)STS2backpatch(T.chain,NXQ),并设:TC有属性值T.chain及C.chain,用于记录条件及无条件转移四元式的序号.,20,示例:ifA1thenx:=2elsey:=4,x:=2elsey:=4,C,CS1else,T,TS2,x:=2elsey:=4,y:=4,ifBthen,四元式序列(1)(E2?,E2的四元式,T,i:=E1,S的四元式,i:=i+1,28,第八节数组的翻译,这节讨论三个问题:数组说明的翻译数组元素的翻译含数组元素的赋值语句的翻译1数组说明语句的翻译进行数组说明语句的翻译时,要把数组名填入符号表,并建立一内情向量表,记录维数,下标上下界,类型等.简单起见,只考虑如下的数组说明:A:arrayL1:U1,L2:U2,.Ln:UnofTYPE,29,文法如下:Di:arrayLISTofTLISTi(1):i(2)|LIST(1),i(1):i(2)Tinteger|real|char|boolean语义子程序如下:LISTi(1):i(2)建立一个仅含i(1):i(2)的队列LIST.QLISTLIST(1),i(1):i(2)把i(1):i(2)插入队列LIST.Q中Di:arrayLISTofTi填入符号表并标志为数组;开辟内情向量表,把LIST.Q中的上下界对逐一取出,计算di,并将i(1),i(2),di,放入内情向量表;计算维数n及c,将T.attr,n,c填入内情向量表.数组说明语句不产生四元式.,30,c=(L1)*d2d3d4.dn+(L2)*d3d4.dn+(Ln-1)*dn+(Ln)*elemlength=(.(L1d2+L2)d3+L3)d4+L4).)dn+Ln*elemlength,31,2数组元素的翻译设数组元素为:AE1,E2,.En,要取得该元素值,首先要计算出该元素的地址:addr=conspart+varpartconspart=a-cvarpart=(.(E1d2+E2)d3+E3)d4+E4).)dn+Enconspart的ac已经通过数组说明语句的翻译登记在内情向量表中;而varpart中含有未知数,只能在程序运行时通过如下算法实现:,32,varpart:=E1;k:=1;whilekndovarpart:=varpart*dk+1+Ek+1;K:=k+1下面是包含数组元素的变量的文法:Vi|iE1,E2,.En为了便于翻译上面的算法,文法改为如下形式:Vi|ElistElistiE|Elist1,EV有两个值:V.place,V.off对于简单变量,V.place=entry(i),V.off=0;对于数组变量,V.place=a-c,V.off=varpart;,33,Elist有三个值:Elist.array/i在符号表中的位置Elist.dim/i的维数Elist.place/存放varpart的中间结果语义子程序如下:ViV.place:=entry(i);V.off:=0;ElistiEElist.array:=entry(i);Elist.place:=E.place;Elist.dim:=1,34,ElistElist1,EElist.place:=newtemp();Elist.array:=Elist1.array;Elist.dim:=Elist1.dim+1;dk:=get_dk(Elist.array,Elist.dim);gen(*,Elist1.place,dk,Elist.place);gen(+,E.place,Elist.place,Elist.place);VElistV.place:=newtemp();gen(-,Elist.array.a,Elist.array.c,V.place)V.off:=Elist.place,