【精品】【考研计算机专业课】天津大学 编译原理讲义 表达式的翻译5.2.4-5.3（可编辑.ppt

《【精品】【考研计算机专业课】天津大学 编译原理讲义 表达式的翻译5.2.4-5.3（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】天津大学 编译原理讲义 表达式的翻译5.2.4-5.3（可编辑.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【考研计算机专业课】天津大学 编译原理讲义 表达式的翻译5.2.4-5.3例例，赋值语句，赋值语句A:=-B*(C+D)可表示成四元式表可表示成四元式表:凡只需一个运算量的算符凡只需一个运算量的算符(单目单目运算符运算符)，一律使用，一律使用ARG1。T1临时变量临时变量T1B（1）T2临时变量临时变量T2DC+（2）T3临时变量临时变量T3T2T1*（3）赋值运算赋值运算AT3:=（4）注解注解RESULTARG2ARG1OP序号序号运算量和运算结果运算量和运算结果有时指用户自定义的变量，有时指编译有时指用户自定义的变量，有时指编译程序引进的临时变量。程序引进的临时变量。四元式间的联系是通过

2、四元式间的联系是通过临时变量临时变量实现的，这样更改四实现的，这样更改四元式表很容易。元式表很容易。相对来说，更改三元式比较困难，因为它意味着必须相对来说，更改三元式比较困难，因为它意味着必须改变其中一系列指示器的值。改变其中一系列指示器的值。在对中间代码进行优化处理时，四元式比三元式方便。在对中间代码进行优化处理时，四元式比三元式方便。学习要点学习要点:熟悉语法制导翻译的过程。熟悉语法制导翻译的过程。掌握各种语法结构生成的中间代码。掌握各种语法结构生成的中间代码。了解语义子程序的设计。了解语义子程序的设计。5.3表达式及赋值语句的翻译表达式及赋值语句的翻译5.3.1算术表达式与赋值语句的翻译

3、算术表达式与赋值语句的翻译1.只含只含整型变量整型变量的简单赋值语句的翻译的简单赋值语句的翻译Ai:=EEE+E|E*E|-E|(E)|i上述文法的上述文法的语义动作描述语义动作描述:产生式产生式语义动作语义动作(1)Ai:=EGEN(:=,E.PLACE,ENTRY(i)(2)EE(1)+E(2)E.PLACE=NEWTEMP；GEN(+,E(1).PLACE,E(2).PLACE,E.PLACE)(3)EE(1)*E(2)E.PLACE=NEWTEMP；GEN(*,E(1).PLACE,E(2).PLACE,E.PLACE)(4)E-E(1)E.PLACE=NEWTEMP；GEN(,E(1

4、).PLACE,E.PLACE)(5)E(E(1)E.PLACE=E(1).PLACE(6)EiE.PLACE=ENTRY(i)输入输入栈栈PLACE四元式四元式A:=-B*(C+D):=-B*(C+D)i-B*(C+D)i:=A_B*(C+D)i:=-A_*(C+D)i:=-iA_B*(C+D)i:=-EA_B(,B,T1)*(C+D)i:=EA_T1(C+D)i:=E*A_T1_C+D)i:=E*(A_T1_+D)i:=E*(iA_T1_C+D)i:=E*(EA_T1_C例例，A:=-B*(C+D)的语法制导翻译过程的语法制导翻译过程i:=-i*(i+i)D)i:=E*(E+A_T1_C_

5、)i:=E*(E+iA_T1_C_D)i:=E*(E+EA_T1_C_D(+,C,D,T2)i:=E*(EA_T1_T2i:=E*(E)A_T1_T2_i:=E*EA_T1_T2(*,T1,T2,T3)i:=EA_T3(:=,T3,A)A输入输入栈栈PLACE四元式四元式最终生成最终生成:(,B,T1)(+,C,D,T2)(*,T1,T2,T3)(:=,T3,A)2.类型转换类型转换一个表达式中可能出现各种不同类型的变量和常数。一个表达式中可能出现各种不同类型的变量和常数。所以，编译程序必须做到所以，编译程序必须做到:或者拒绝接受某种混合运算，或者拒绝接受某种混合运算，或者产生有关类型转换的指

6、令。或者产生有关类型转换的指令。Ai:=EEE+E|E*E|-E|(E)|i文法中的文法中的 i既可是整型量，又可是实型量。当两个不同类型既可是整型量，又可是实型量。当两个不同类型的量进行运算时，规定首先必须把整型量转换成实型量。的量进行运算时，规定首先必须把整型量转换成实型量。(1)(1)为实现类型转换，每个非终结符的语义值必须增加为实现类型转换，每个非终结符的语义值必须增加类型信息类型信息。用用E.MODE表示，取值为表示，取值为r(实型实型)或或int(整型整型)。例，例，对于整形运算，产生式对于整形运算，产生式EE(1)opE(2)，E.MODE的语义规则将定义为的语义规则将定义为:i

7、f(E(1).MODE=int)&(E(2).MODE=int)E.MODE=int；(2)(2)在四元式中增加一个整型变量转换为实型变量的四元在四元式中增加一个整型变量转换为实型变量的四元式式:(itr,A,T)，同时在运算符上应指出相应的类型，同时在运算符上应指出相应的类型，这里规定用上角标表示这里规定用上角标表示(opi i，opr r)。例例，赋值语句，赋值语句:X:=Y+I*J其中其中:X,Y为实型为实型；I,J为整型为整型它产生的四元式为它产生的四元式为:(*i,I,J,T1)(itr,T1,T2)(+r,Y,T2,T3)(:=,T3,X)产生式产生式:EE(1)opE(2)的语义

8、子程序的描述是的语义子程序的描述是:if(E(1).MODE=int)&(E(2).MODE=int)GEN(opi,E(1).PLACE,E(2).PLACE,T)；E.MODE=int；elseif(E(1).MODE=r)&(E(2).MODE=r)GEN(opr,E(1).PLACE,E(2).PLACE,T)；E.MODE=r；T=NEWTEMP；elseif(E(1).MODE=int)/*&(E(2).MODE=r)*/U=NEWTEMP；GEN(itr,E(1).PLACE,U)；GEN(opr,U,E(2).PLACE,T)；E.MODE=r；else/*(E(1).MODE

9、=r)&(E(2).MODE=int)*/U=NEWTEMP；GEN(itr,E(2).PLACE,U)；GEN(opr,E(1).PLACE,U,T)；E.MODE=r；E.PLACE=T；输入输入栈栈PLACE四元式四元式X:=Y+I*J:=Y+I*JiY+I*Ji:=X_+I*Ji:=iX_Y+I*Ji:=EX_YI*Ji:=E+X_Y_*Ji:=E+iX_Y_I*Ji:=E+EX_Y_I例例，X:=Y+I*J的语法制导翻译过程的语法制导翻译过程i:=i+i*iJi:=E+E*X_Y_I_i:=E+E*iX_Y_I_Ji:=E+E*EX_Y_I_J(*i i,I,J,T1)i:=EX_T

10、3(:=,T3,X)i:=E+EX_Y_T1(itr,T1,T2)(+r,Y,T2,T3)输入输入 栈栈PLACE四元式四元式A5.3.2布尔表达式的翻译布尔表达式的翻译布尔表达式在程序语言中有两个基本功用布尔表达式在程序语言中有两个基本功用:一是作为控制语句一是作为控制语句(如如if或或while语句语句)的条件式；的条件式；二是作逻辑运算，获得逻辑值。二是作逻辑运算，获得逻辑值。IfX=0thenY:=3；1(00)0布尔表达式由布尔表达式由布尔算符布尔算符作用于作用于布尔变量布尔变量或或常量常量，或，或关系表关系表达式达式而形成的。而形成的。布尔算符布尔算符(按优先级按优先级)有有:(:

11、(非非)，(与与)，(或或)。关系符关系符rop有有:，布尔变量布尔变量:Boolean:A，B，C。布尔常量布尔常量:true，false，1，0。关系表达式是由关系符作用于算术表达式而形成，如关系表达式是由关系符作用于算术表达式而形成，如E1ropE2。布尔表达式的文法布尔表达式的文法:EEE|EE|E|(E)|i|iropi计算布尔表达式的值计算布尔表达式的值:1.直接计算直接计算按算术表达式的计算方式根据布尔运算符的优先级和结按算术表达式的计算方式根据布尔运算符的优先级和结合关系计算布尔表达式。合关系计算布尔表达式。例例，令令true=1，false=0，计算布尔表达式，计算布尔表达式

12、:1(00)000)0=1(10)01(10)0=100100=1010=1 12.采用某种优化措施来计算采用某种优化措施来计算计算计算AB，只要计算出，只要计算出A=1，则不必再算，则不必再算B，可知结果为，可知结果为1；计算计算AB，只要计算出，只要计算出A=0，则不必再算，则不必再算B，可知结果为，可知结果为0；用条件句来解释布尔计算用条件句来解释布尔计算:AB解释为解释为ifAthentrueelseBAB解释为解释为ifAthenBelsefalseA解释为解释为 ifAthenfalseelsetrue针对两种算法有两种不同的翻译方法。针对两种算法有两种不同的翻译方法。优化优化计算

13、条件语句的翻译计算条件语句的翻译:条件语句条件语句ifEthenS1elseS2中的布尔式中的布尔式E，它的作，它的作用在于控制对用在于控制对 S1和和S2的选择。的选择。E的代码的代码S1的代码的代码S2的代码的代码真真假假为了表述真、假出口，引入三种形式的四元式为了表述真、假出口，引入三种形式的四元式:(1)(jnz,A1,p)若若A1为为真真，则转向第，则转向第p个四元式。个四元式。(2)(j,A1,A2,p)若若A1A2为为真真,则转向第则转向第p个四元式。个四元式。(3)(j,p)无条件转向第无条件转向第p个四元式。个四元式。例例，将，将ifABDthenS1elseS2翻译成四元式

14、序列翻译成四元式序列为每一个为每一个子布尔式子布尔式都定义两个四元式，分别指向都定义两个四元式，分别指向真假出口真假出口。(jnz,A,0)真出口真出口(j,0)假出口假出口(j,B,D,0)真出口真出口(j,0)假出口假出口(1)(jnz,A,0)A的的“真真”出口出口开始未知，填开始未知，填0；ifABDthenS1elseS2翻译成四元式序列为翻译成四元式序列为:(2)(j,0)A的的“假假”出口出口开始未知开始未知0；(3)(j,B,D,1)BD的的“真真”出口出口与与1真出口合并；真出口合并；(4)(j,0)BD的的“假假”出口出口未知，填未知，填0；(5)(关于关于S1的四元式序列

15、的四元式序列)；(p)(j,0)跳过跳过S2的代码段，开始未知；的代码段，开始未知；(p+1)(关于关于S2的四元式序列的四元式序列)；(q)(1)(jnz,A,5)A的的“真真”出口出口为为5；(3)(j,B,D,5)BD的的“真真”出口出口为为5；(4)(j,p+1)BD的的“假假”出口出口为为(p+1)；(p)(j,q)跳过跳过S2的代码段；的代码段；E的代码的代码S1的代码的代码S2的代码的代码(2)(j,3)A的的“假假”出口出口为为3；注意一个布尔表达式的注意一个布尔表达式的真假出口真假出口:如如EE(1)E(2)若若E(1)为真，则为真，则E为真，为真，E(1)的真出口即的真出口

16、即E的真出口；的真出口；若若E(1)为假，再看为假，再看E(2)。E(2)为真，则为真，则E为真为真，E(2)的真出口就是的真出口就是E的真出口的真出口E(2)为假，则为假，则E为假，为假，E(2)的假出口就是的假出口就是E的假出口的假出口如如EE(1)E(2)若若E(1)为假，则为假，则E为假，为假，E(1)的假出口即的假出口即E的假出口；的假出口；若若E(1)为真，再看为真，再看E(2)。E(2)为真，则为真，则E为真为真，E(2)的真出口就是的真出口就是E的真出口的真出口E(2)为假，则为假，则E为假，为假，E(2)的假出口就是的假出口就是E的假出口的假出口如如EE(1)若若E(1)为假

17、，则为假，则E为真，为真，E(1)的假出口即的假出口即E的真出口；的真出口；若若E(1)为真，则为真，则E为假，为假，E(1)的真出口即的真出口即E的假出口；的假出口；问题问题1.1.在自下而上的分析过程中，一个布尔式的真假出口在自下而上的分析过程中，一个布尔式的真假出口往往不能在产生四元式的同时就填上，必须等到分析后面往往不能在产生四元式的同时就填上，必须等到分析后面的语句时进行回填，所以需要回填的四元式的地址必须被的语句时进行回填，所以需要回填的四元式的地址必须被保存起来。保存起来。存在两个问题存在两个问题:例例，ABDA归约为归约为E(Ei)时产生四元式时产生四元式 p (jnz,A,0

18、)EEE|EE|E|(E)|i|iropi解决方法解决方法:对非终结符定义两个语义值对非终结符定义两个语义值E.TC和和E.FC，分别记录表，分别记录表达式达式E所对应的四元式需回填的真、假出口的四元式地址所对应的四元式需回填的真、假出口的四元式地址所构成的链。所构成的链。例例，E的四元式中需回填的的四元式中需回填的真真出口的有出口的有p,q和和r三个四三个四元式，这三个四元式可以用一条元式，这三个四元式可以用一条真真链链(TC)连接，连接，E.TC的的值为链首的的值为链首r。(p)(0)0为链末标志为链末标志(q)(p)(r)(q)地址地址(r)为为TC链之首，链之首，E.TC之值。之值。(

19、1)(jnz,A,0)A的的“真真”出口出口开始未知，填开始未知，填0；例例，ifABDthenS1elseS2(2)(j,3)A的的“假假”出口出口为为3；(3)(j,B,D,1)BD的的“真真”出口出口与与1真出口合并；真出口合并；(4)(j,0)BD的的“假假”出口出口未知，填未知，填0；(5)(关于关于S1的四元式序列的四元式序列)；(1)(jnz,A,5)A的的“真真”出口出口为为5；(3)(j,B,D,5)BD的的“真真”出口出口为为5；E.TC=3为了处理为了处理E.TC和和E.FC，定义新的，定义新的语义变量语义变量和和语义过程语义过程:NXQ指示器，指向指示器，指向下一个下一

20、个将要形成但尚未形成的四元将要形成但尚未形成的四元式的地址式的地址(编号编号)。其初值为。其初值为1。每执行。每执行GEN一次，自动增一次，自动增1。MERG(p1,p2)合并合并函数，把以函数，把以p1和和p2为链首的链合而为链首的链合而为一，合并后的链首作为函数值送回。为一，合并后的链首作为函数值送回。BACKPATCH(p,t)回填回填函数，把函数，把p所链接的每个四元式所链接的每个四元式的第四区段都回填进的第四区段都回填进t。if(p2=NULL)returnp1；p=p2；while(四元式四元式p的第四区段的内容不为的第四区段的内容不为NULL)p=四元式四元式p的第四区段的内容；

21、的第四区段的内容；把把p1填进四元式填进四元式p的第四区段；的第四区段；returnp2；void*MERG(void*p1,void*p2)void*p；else函数函数MERG(p1,p2)把把p1和和p2为链首的链二而为一，为链首的链二而为一，p2作为合作为合并后的链首以函数值的形式返回。并后的链首以函数值的形式返回。（0）.（p1）（）.（）p1（）p2（）若若p2NULL，则，则p2链的链尾链的链尾NULL改成改成p1，p2为新的链首；为新的链首；否则，若否则，若p2=NULL，p1为新的链首。为新的链首。q=p；q1=四元式四元式q的第四区段的内容；的第四区段的内容；把把t填进四元

22、式填进四元式q的第四区段；的第四区段；q=q1；while(q!=NULL)void*BACKPATCH(void*p,void*t)void*q,*q1；函数函数BACKPATCH(p,t)，负责把，负责把p所链接的每个四元式的所链接的每个四元式的第四区段都回填进第四区段都回填进t。(1)(jnz,A,0)A的的“真真”出口出口开始未知，填开始未知，填0；例例，ifABDthenS1elseS2(2)(j,3)A的的“假假”出口出口为为3；(3)(j,B,D,0)BD的的“真真”出口出口开始为开始为0；(4)(j,0)BD的的“假假”出口出口未知，填未知，填0；(5)(关于关于S1的四元式序

23、列的四元式序列)；(3)(j,B,D,1)BD的的“真真”出口出口与与1真出口合并；真出口合并；E.TC=3(1)(jnz,A,5)A的的“真真”出口出口为为5；(3)(j,B,D,5)BD的的“真真”出口出口为为5；问题问题2:真假出口何时回填？真假出口何时回填？EEE|EE|E|(E)|i|iropi例例，ifABDthenS1elseS2(1)(jnz,A,0)A的的“真真”出口出口开始未知，填开始未知，填0；(2)(j,0)A的的“假假”出口出口开始未知开始未知0；(3)(j,B,D,1)BD的的“真真”出口出口与与1真出口合并；真出口合并；(2)(j,3)A的的“假假”出口出口为为3

24、；(4)(j,0)BD的的“假假”出口出口未知，填未知，填0；EEE|EE|E|(E)|i|iropi例例，ifABDthenS1elseS2(1)(jnz,A,0)A的的“真真”出口出口开始未知，填开始未知，填0；(2)(j,0)A的的“假假”出口出口开始未知开始未知0；(3)(j,B,D,0)BD的的“真真”出口出口开始未知开始未知0；(1)(jnz,A,3)A的的“真真”出口出口为为3；(4)(j,2)BD的的“假假”出口出口与与2假出口合并；假出口合并；为了使用语法制导翻译，在扫描到为了使用语法制导翻译，在扫描到或或时能及时回填时能及时回填一些业已明确的待填的转移目标，需要对文法改写成

25、一些业已明确的待填的转移目标，需要对文法改写成:EEAE|EOE|E|(E)|i|iropiEAEEOEEEE|EE|E|(E)|i|iropi文法的每个产生式相应的语义子程序如下文法的每个产生式相应的语义子程序如下:(1)EiE.TC=NXQ；E.FC=NXQ+1；GEN(jnz,ENTRY(i),0)；GEN(j,0)(2)Ei(1)ropi(2)E.TC=NXQ；E.FC=NXQ+1；GEN(jrop,ENTRY(i(1),ENTRY(i(2),0)；GEN(j,0)(3)E(E(1)E.TC=E(1).TC；E.FC=E(1).FC(4)EE(1)E.TC=E(1).FC；E.FC=E

26、(1).TC(5)EAE(1)BACKPATCH(E(1).TC，NXQ)；EA.FC=E(1).FC(6)EEAE(2)E.TC=E(2).TC；E.FC=MERG(EA.FC，E(2).FC)(7)EOE(1)BACKPATCH(E(1).FC，NXQ)；EO.TC=E(1).TC(8)EEOE(2)E.FC=E(2).FC；E.TC=MERG(EO.TC，E(2).TC)例例，A(B(CD)的语法制导翻译过程的语法制导翻译过程i(i(ii)1(NXQ)Ei(A)(jnz,A,0)2E.TC=1E.FC=2(j,0)3(j,3)EOE(1)EO.TC=1Ei(B)(jnz,B,0)4E.T

27、C=3E.FC=4(j,0)5EAE(1)E.FC=4(jnz,B,5)Ei(C)(jnz,C,0)6E.TC=5E.FC=6(j,0)7(j,7)EOE(1)EO.TC=5Ei(D)(jnz,A,0)8E.TC=7E.FC=8(j,0)9EEOE(2)E.FC=8(jnz,D,5)E.TC=7E(E(1)E.FC=8E.TC=7EE(1)E.TC=8E.FC=7EEAE(2)E.TC=8(jnz,C,4)E.FC=7E(E(1)E.TC=8E.FC=7EEOE(2)E.FC=7E.TC=8(j,1)1(jnz,A,0)2(j,3)3(jnz,B,5)4(j,0)5(jnz,C,4)6(j,7)7(jnz,D,5)8(j,1)E.TC=8E.FC=7下面的学习中要重点注意的两点地方下面的学习中要重点注意的两点地方:1.真、假链的处理真、假链的处理:为什么引入真假链、什么时候为什么引入真假链、什么时候需要回填、什么时候需要合并。需要回填、什么时候需要合并。2.文法的改造文法的改造:根据实际情况，怎样改造文法以方根据实际情况，怎样改造文法以方便实现真假链的构造、合并和回填。便实现真假链的构造、合并和回填。作业作业:(AB)(CD)