语义分析和中间代码生成 课件.ppt

《语义分析和中间代码生成 课件.ppt》由会员分享，可在线阅读，更多相关《语义分析和中间代码生成 课件.ppt（145页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、语义分析和中间代码语义分析和中间代码生成生成 第1页，此课件共145页哦4.1 概概 述述 4.1.1语义分析的概念语法分析:在编译时对符合语法结构的源程序内部的逻辑含义加以分析，即审查每个语法成分的静态语义(动态语义检查在程序运行时进行)。如果静态语义正确，则生成与该语言成分等效的中间代码，或者直接生成目标代码。第2页，此课件共145页哦静态语义检查:是在编译时完成的，它涉及以下几个方面：(1)类型检查，如参与运算的操作数其类型应相容。(2)控制流检查，用以保证控制语句有合法的转向点。(3)一致性检查，如在相同作用域中标识符只能说明一次、case语句的标号不能相同等。属性文法:语义分析阶段只

2、产生中间代码,语义的形式化描述是非常困难的，目前较为常见的是用属性文法作为描述程序语言语义的工具，并采用语法制导翻译的方法完成对语法成分的翻译工作。第3页，此课件共145页哦4.1.2语法制导翻译方法语法制导翻译方法:就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并在语法分析的同时执行这些子程序。语义动作:是为产生式赋予具体意义的手段，它一方面指出了一个产生式所产生的符号串的意义，另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序就进入工作，完成既定的

3、翻译任务。语法制导翻译分为自下而上语法制导翻译和自上而下语法制导翻译。第4页，此课件共145页哦可拓展LR分析器能力，实现自下而上语法制导翻译使LR分析器在用某个产生式进行归约的同时调用相应的语义子程序进行有关的翻译工作；每个产生式的语义子程序执行之后，某些结果(语义信息)作为此产生式的左部符号的语义值暂时保存下来，以便以后语义子程序引用这些信息。扩充原LR分析器的分析栈以便能够存放与文法符号相对应的语义值。扩充后的分析栈如图41所示。第5页，此课件共145页哦图41扩充后的LR分析栈第6页，此课件共145页哦例子：valTOP表示放在语义栈顶的值产生式语义动作(0)SEprintvalTOP

4、(1)EE(1)+E(2)valTOP+2=valTOP+valTOP+2(2)EE(1)*E(2)valTOP+2=valTOP*valTOP+2(3)E(E(1)valTOP+2=valTOP+1(4)EivalTOP=lexval(注：lexval为i的整型内部值)这个文法的LR分析表见表3.20。E.valE(2).valE(1).valE.val第7页，此课件共145页哦表3.20算术表达式的SLR(1)分析表状态ACTIONGOTOi+*()#E0s3s211s4s5acc2s3s263r4r4r4r44s3s275s3s286s4s5s97r1s5r1r18r2r2r2r29r3

5、r3r3r3第8页，此课件共145页哦表4.1则给出了根据表3.20用LR语法制导翻译方法得到的表达式79*5#的语义分析和计值过程。图42表示算术表达式79*5#的语法树及各结点值。第9页，此课件共145页哦表4.1表达式79*5#的语义分析和计值过程步骤状态栈符号栈语义栈输入串主要动作10#_79*5#s3203#i(val=7)_9*5#r4301#E_79*5#s44014#E+_7_9*5#s350143#E+i(9)_7_*5#r460147#E+E_7_9*5#s5701475#E+E*_7_9_5#s38014753#E+E*i(5)_7_9_#r49014758#E+E*E_

6、7_9_5#r2100147#E+E_7_45#r11101#E_52#acc规约时执行语义动作第10页，此课件共145页哦图42语法制导翻译计算表达式79*5#的语法树注释语法树第11页，此课件共145页哦4.2 属属 性性 文文 法法属性文法是在基础文法的基础上，附加上文法符号的属性计算规则形成的文法。属性文法可用作语言翻译动作的高层描述。4.2.1文法的属性属性:是指与文法符号的地址、类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。例如，判断变量X的类型是否匹配，要用X的数据类型来描述；判断变量X是否存在，要用X的存储位置来描述；而对X的运算，则要用X的值来描述；因此，语义分

7、析阶段引入X的属性，如X.type、X.place、X.val等来分别描述变量X的类型、存储位置以及值等不同的特征。第12页，此课件共145页哦文法符号的属性可分为继承属性与综合属性两类。继承属性用于“自上而下”传递信息。继承属性由相应语法树中结点的父结点或兄弟节点属性计算得到，即沿语法树向下传递，由根结点到分枝(子)结点，它反映了对上下文依赖的特性。继承属性可以很方便地用来表示程序语言上下文的结构关系。综合属性用于“自下而上”传递信息。综合属性由相应语法分析树中结点的分枝结点(即子结点)属性计算得到，其传递方向与继承属性相反，即沿语法分析树向上传递，从分枝结点到根结点。第13页，此课件共14

8、5页哦4.2.2属性文法属性文法：在语言文法的基础上，附加上文法符号的属性计算规则形成的文法即属性文法。属性文法也是一种翻译文法，属性有助于更详细地指定文法中的代码生成动作。第14页，此课件共145页哦例1，简单算术表达式求值的属性文法如下：产生式语义规则(1)SEprint(E.val)(2)EE(1)+TE.val=E(1).val+T.val(3)ETE.val=T.val(4)TT(1)*FT.val=T(1).val*F.val(5)TT(1)T.val=T(1).val(6)F(E)F.val=E.val(7)FiF.val=i.lexval注意：E、T、F等符号的属性由其各自相应

9、的右部符号决定，为综合属性。第15页，此课件共145页哦例2：一简单变量类型说明的文法GD如下：GD：DintLfloatLLL,idid其对应的属性文法为：产生式语义规则(1)DTLL.in=T.type(2)TintT.type=int(3)TfloatT.type=float(4)LL(1)，idL(1).in=L.in;addtype(id.entry,L.in)(5)Lidaddtype(id.entry,L.in)注意到与文法GD相应的说明语句形式可为intid1，id2,，idn或者floatid1，id2,，idn第16页，此课件共145页哦属性L.in=T.type表示L.i

10、n的属性值由其兄弟节点属性T.type决定，同样L(1).in由其父节点属性L.in决定，L.in和L(1).in均为继承属性。由此可见，标识符的类型可以通过继承属性的复写规则来传递。例如，对输入串inta,b，根据上述的语义规则，可在其生成的语法树中看到用“”表示的属性传递情况，如图43所示。第17页，此课件共145页哦图43属性信息传递情况示意第18页，此课件共145页哦4.3 几种常几种常见的中的中间语言言4.3.1抽象语法树抽象语法树也称图表示，是一种较为流行的中间语言表示形式。在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符和关键字。第1

11、9页，此课件共145页哦例1：如赋值语句语法规则：SV=EVid EE-E|E*E|id|i分析x=ab*c的抽象语法树如图44(a)所示，而图44(b)则是该赋值语句的普通语法树。图44x=ab*c的语法树第20页，此课件共145页哦例2：条件语句语法规则：Sif(e)S1;elseS2抽象语法树形式为：抽象语法树的一个显著特点是结构紧凑，容易构造且结点数较少。gcc等编译器把抽象语法树当作中间语言。第21页，此课件共145页哦4.3.2逆波兰表示法逆波兰表示法：是波兰逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示表达式的方法，这种表示法把运算量(操作数)写在前面，把运算符写在后

12、面，因而又称后缀表示法。例如，把a+b写成ab+，把a*(b+c)写成abc+*。第22页，此课件共145页哦1表达式的逆波兰表示表达式E的后缀表示的递归定义如下：(1)如果E是变量或常数，则E的后缀表示即E自身。(2)如果E为E1opE2形式，则它的后缀表示为E1E2op；其中op是二元运算符，而E1、E2分别又是E1和E2的后缀表示。若op为一元运算符，则视E1和E1为空。(3)如果E为(E1)形式，则E1的后缀表示即为E的后缀表示。第23页，此课件共145页哦后缀表示中的计值用栈实现非常方便。一般的计值过程是自左至右扫描后缀表达式，每碰到运算量就把它推进栈，每碰到K目运算符就把它作用于栈

13、顶的K个运算量，并用运算的结果(即一个运算量)来取代栈顶的K个运算量。2程序语句的逆波兰表示(自学)第24页，此课件共145页哦4.3.3三地址代码三地址代码的形式x=yopzx、y和z为名字、常量或编译时产生的临时变量；op为运算符。三地址代码的每条语句通常最多包含三个地址，两个用来存放运算对象，一个用来存放运算结果。第25页，此课件共145页哦三地址语句只含有一个运算符，因此多个运算符组成的表达式必须用三地址语句序列来表示。三地址代码是语法树的一种线性表示(深度优先遍历语法树可以得到对应的三地址语句。)，在语法制导翻译中常用临时变量代替抽象语法树中的内部结点(相应的三地址代码亦然)。如图4

14、4(a)所示的语法树用三地址代码表示为：t1=b*ct2=at1x=t2第26页，此课件共145页哦2三地址语句的种类三地址语句非常类似于汇编代码，它可以有符号标号和各种控制流语句。常用的三地址语句有以下几种：(1)赋值语句：x=yopz，其中op为二目的算术运算符或逻辑运算符。x=opy，其中op为一目运算符，如一目减uminus、逻辑否定not、移位运算符以及将定点数转换成浮点数的类型转换符。x=y，将y的值赋给。第27页，此课件共145页哦x=yi：变址赋值语句，其中x、y、i均代表数据对象，表示把从地址y开始的第i个地址单元中的值赋给x。xi=y则表示把y的值赋给从地址x开始的第i个地

15、址单元。地址和指针赋值语句x=&y表示将y的地址赋给x，y可以是一个名字或一个临时变量，而x是指针名或临时变量；x=*y表示将y所指示的地址单元中的内容(值)赋给x，y是一个指针或临时变量；*x=y表示指将x所指对象的值置为y的值。第28页，此课件共145页哦(2)转移语句gotoL，无条件转移语句，即下一个将被执行的语句是标号为L的语句。ifxropygotoL，条件转移语句，其中rop为关系运算符，如、=等。若x和y满足关系rop就转去执行标号为L的语句，否则继续按顺序执行本语句的下一条语句。第29页，此课件共145页哦(3)过程调用和返回语句：parX和callP,n。源程序中的过程调用

16、语句P(X1、X2、，Xn)可用下列三地址代码表示：parX1parX2parXncallP,n其中，整数n为实参个数。returny：过程返回语句，其中y为过程返回值。第30页，此课件共145页哦3三地址代码的具体实现三地址代码是中间代码的一种抽象形式。在编译程序中，三地址代码语言的具体实现通常有三种表示方法：四元式、三元式和间接三元式。1)四元式四元式是具有四个域的记录结构，这四个域为(op，arg1，arg2，result)op为运算符；arg1、arg2及result为指针，它们可指向有关名字在符号表中的登记项或一临时变量(也可空缺)。第31页，此课件共145页哦例：常用的三地址语句与

17、相应的四元式对应如下：约定：凡只需一个运算量的算符一律使用arg1。x=yopz对应(op,y,z,x)x=y对应(uminus,y,_,x)x=y对应(=,y,_,x)parx1对应(par,x1,_,_)callP对应(call,_,_,P)gotoL对应(j,_,_,L)ifxropygotoL对应(jrop,x,y,L)第32页，此课件共145页哦2)三元式三元式是具有三个域的记录结构，这三个域为(op，arg1，arg2)其中，op为运算符；arg1、arg2既可指向有关名字在符号表中的登记项或临时变量，也可以指向三元式表中的某一个三元式四元式中的result域用对应三元式的指针代替

18、。例如，相应于赋值语句a=(b+c)*(b+c)的三元式代码为：(+,b,c)(+,b,c)(*,)(=,a,)第33页，此课件共145页哦3)间接三元式间接码表：在三元式代码表的基础上另设一张表，该表按运算的次序列出相应三元式在三元式表中的位置，这张表称为间接码表。三元式表：只记录不同的三元式语句，而间接码表则表示由这些语句组成的运算次序。例，赋值语句a=(b+c)*(b+c)对应三元式表与间接码表为：三元式表：(+,b,c)(*,)(=,a,)间接码表：第34页，此课件共145页哦三地址表示方式与代码优化：三元式表示：代码优化阶段调整三元式的运算顺序需修改指向这些三元式位置指针的相关三元式

19、的指针值(arg1或arg2)。不利于代码优化。四元式：代码调整时不需修改四元式的任何域值。间接三元式：通过间接码表来描述语句的运算次序，代码调整时只需修改间接码表，无需修改三元式的任何域值。第35页，此课件共145页哦4.4 表达式及表达式及赋值语句的翻句的翻译4.4.1简单算术表达式和赋值语句的翻译简单算术表达式是一种仅含简单变量的算术表达式；简单变量是指普通变量和常数，但不含数组元素及结构引用等复合型数据结构。GA：Ai=E/非终结符A代表“赋值句”。EE+EE*EE(E)i第36页，此课件共145页哦语义子程序所涉及的语义变量、语义过程及函数说明如下：(1)语义变量E.place:表示

20、存放E值的变量名在符号表中的入口地址或临时变量名的整数码。(2)语义函数newtemp():创建一个临时变量。返回一个代表新临时变量的整数码；临时变量名按产生的顺序可设为T1、T2、。(3)语义过程emit(op,arg1,arg2,result):产生一个四元式并填入四元式表中。(4)语义函数lookup(i.name)：在符号表中查找变量i.name，有则返回i.name在符号表的入口指针，否则返回NULL。第37页，此课件共145页哦文法GA中的每一个产生式的语义子程序如下。(1)Ai=Ep=lookup(i.name);if(p=NULL)error();elseemit(=,E.pl

21、ace,_,P);(2)EE(1)+E(2)E.place=newtemp();emit(+,E(1).place,E(2).place,E.place);如规约出左部E的时候，E的属性值为一新值，需创建一个临时变量，保存该新值第38页，此课件共145页哦(3)EE(1)*E(2)E.place=newtemp();emit(*,E(1).place,E(2).place,E.place);(4)EE(1)E.place=newtemp();emit(uminus,E(1).place,_,E.place);(5)E(E(1)E.place=E(1).place;(6)Eip=lookup(i

22、.name);if(p!=NULL)E.place=p;elseerror();第39页，此课件共145页哦例4.1试分析赋值语句X=B*(C+D)的语法制导翻译过程。解答第40页，此课件共145页哦表4.2赋值语句X=B*(C+D)的翻译过程输入串归约产生式符号栈语义栈(place)四元式X=B*(C+D)#_=B*(C+D)#i_XB*(C+D)#i=_X_B*(C+D)#i=_X_*(C+D)#(6)#i=i_X_B*(C+D)#(4)#i=E_X_B(uminus,B,_,T1)*(C+D)#i=E_X_T1第41页，此课件共145页哦(C+D)#i=E*_X_T1_C+D)#i=E*

23、(_X_T1_+D)#(6)#i=E*(i_X_T1_C+D)#i=E*(E_X_T1_CD)#i=E*(E+_X_T1_C_)#(6)#i=E*(E+i_X_T1_C_D)#(2)#i=E*(E+E_X_T1_C_D(+,C,D,T2)#i=E*(E_X_T1_T2#(5)#i=E*(E)_X_T1_T2_#(3)#i=E*E_X_T1_T2(*,T1,T2,T3)#(1)#i=E_X_T3(=,T3,_,X)#A_X第42页，此课件共145页哦4.4.2布尔表达式的翻译布尔表达式的组成：由运算符与运算对象组成。布尔运算符：、，或为not、and和or(注：C语言中为！、&和|)。布尔运算符

24、的运算顺序一般为、，且和服从左结合。布尔算符的运算优先级低于任何关系运算符运算对象：为布尔变量，也可为常量或关系表达式。关系运算符：、=、等。关系运算符的优先级相同但不得结合，其运算优先级低于任何算术运算符。，第43页，此课件共145页哦布尔表达式文法GE：GE：EEEEEE(E)iiropi布尔表达式的计算：从左往右，按优先级逐个计算根据布尔运算的特点实施某种优化，不必一步一步地计算布尔表达式中所有运算对象的值，省略不影响运算结果的运算。例如，在计算AB时，若计算出的A值为1，则B值就无需再计算了；因为不管B的结果是什么，AB的值都为1。同理，在计算AB时若发现A值为0，则B值也无需计算，A

25、B的值一定为0。第44页，此课件共145页哦布尔表达式常用于条件或循环语句中表示条件，表达式为真时程序跳转到一个”真出口”(对应一条条件跳转语句(jmp,条件,_,真出口),否则跳转到一个“假出口”。如何确定一个表达式的真假出口的位置呢？第45页，此课件共145页哦图45E(1)E(2)和E(1)E(2)的翻译图(a)E(1)E(2)；(b)E(1)E(2)若E(1)为真，则立即知道E也为真，E(1)的真出口也就是整个E的真出口若E(1)为假，则E(2)必须被计值，E(2)的第一个四元式就是E(1)的假出口。第46页，此课件共145页哦在语法的分析过程中，一个布尔式的真假出口往往不能在产生四元

26、式的同时就填上，我们只好把这种未完成的四元式的地址(编号)作为E的语义值暂存起来，待到整个表达式的四元式产生完毕之后，再来填写这个未填入的转移目标。对于每个非终结符E，我们需要为它赋予两个语义值E.tc和E.fc，以分别记录E所对应的四元式需要回填“真”、“假”出口的四元式地址所构成的链。这是因为在翻译过程中，常常会出现若干转移四元式转向同一个目标但目标位置又未确定的情况，此时可用“拉链”的方法将这些四元式链接起来，待获得转移目标的四元式地址时再进行返填。例如，假定E的四元式需要回填“真”出口的有p、q、r这三个四元式，则它们可链接成如图46所示的一条真值链(记作tc)。第47页，此课件共14

27、5页哦图46拉链法链接四元式示意第48页，此课件共145页哦为了处理E.tc和E.fc这两项语义值，我们需要引入如下的语义变量和函数：(1)nxq：始终指向下一条将要产生的四元式的地址(序号)，其初值为1。每当执行一次emit语句后，nxq自动增1。(2)merge(p1,p2)：把以p1和p2为链首的两条链合并为一条以p2为链首的链(即返回链首值p2)。(3)Backpatch(p,t)：把链首p所链接的每个四元式的第四区段(即result)都改写为地址t。第49页，此课件共145页哦merge()函数如下：merge(p1，p2)if(p2=0)return(p1);elsep=p2;wh

28、ile(四元式p的第四区段内容不为0)第50页，此课件共145页哦p=四元式p的第四区段内容；把p1填进四元式p的第四区段；return(p2);Backpatch()函数如下：Backpatch(p,t)Q=p;while(Q!=0)第51页，此课件共145页哦q=四元式Q的第四区段内容；把t填进四元式Q的第四区段；Q=q;第52页，此课件共145页哦为了便于实现布尔表达式的语法制导翻译，并在扫描到“”与“”时能及时回填一些已经确定了的待填转移目标，我们将前述文法GE改写为下面的文法GE，以利于编制相应的语义子程序：GE：EEAEEBEE(E)iiropiEAEEBE第53页，此课件共145

29、页哦这时，文法GE的每个产生式和相应的语义子程序如下：(1)EiE.tc=nxq;E.fc=nxq+1;emit(jnz,entry(i),_,0);emit(j,_,_,0);(2)Ei(1)ropi(2)E.tc=nxq;E.fc=nxq+1;emit(jrop,entry(i(1),entry(i(2),0);emit(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(1).tc;第54页，此课件共145页哦(5)EAE(1)Backpatch(E(1).tc,nxq);EA.fc=E(1).f

30、c;(6)EEAE(2)E.tc=E(2).tc;E.fc=merge(EA.fc，E(2).fc);(7)EBE(1)Backpatch(E(1).fc，nxq);EB.tc=E(1).tc;(8)EEBE(2)E.fc=E(2).fc;E.tc=merge(EB.tc，E(2).tc);第55页，此课件共145页哦例4.2试给出布尔表达式abcd作为控制条件的四元式中间代码。解答设四元式序号从100开始，则布尔表达式abcd的分析过程如图47所示。第56页，此课件共145页哦图47表达式abcd分析示意注意此时合并两条假出口链,结果103（j,_,_,101)注意此时合并两条真出口链,结果

31、104（j=,c,d,102)第57页，此课件共145页哦即：100(jnz，a，_，102)101(j，_，_，104)102(jnz，b，_，106)103(j，_，_，104)104(j，c，d，106)105(j，_，_，q)T:106F:q第58页，此课件共145页哦图48abcd的翻译图第59页，此课件共145页哦4.5 控制控制语句的翻句的翻译在源程序中，控制语句用于实现程序流程的控制。一般程序流程控制可分为下面三种基本结构：(1)顺序结构，一般用复合语句实现；(2)选择结构，用if和case等语句实现；(3)循环结构，用for、while、do(即repeat)等语句实现。第6

32、0页，此课件共145页哦4.5.1条件语句if的翻译1条件语句if的代码结构if(E)S1;elseS2布尔表达式E的作用仅在于控制对S1和S2的选择，因此可将作为转移条件的布尔式E赋予两种“出口”：一是“真”出口，出向S1；一是“假”出口，出向S2。条件语句可以翻译成如图49所示的代码结构。第61页，此课件共145页哦图49条件语句if(E)S1;elseS2的代码结构非终结符E具有两项语义值E.tc和E.fc，它们分别指出了尚待回填真假出口的四元式串。E的“真”出口E.tc只有在扫描完布尔表达式E后的“)”时才能知道非终结符E具有两项语义值E.tc和E.fc，“假”出口E.fc则需要处理过

33、S1之后并且到else时才能明确。必须把E.fc的值传下去，以便到达相应的else时才进行回填。S1语句执行完就意味着整个if-else语句也已执行完毕，在S1的编码之后应产生一条无条件转移指令。在完成S2的翻译之前，这条无条件转移指令的转移目标是不知道的，甚至在翻译完S2之后仍无法确定，需要把该条转移四元式编号传下去，在后续代码翻译的某个时刻填入转移地址。第62页，此课件共145页哦代码结构说明：(1)非终结符E具有两项语义值E.tc和E.fc，它们分别指出了尚待回填真假出口的四元式串。E的“真”出口只有在扫描完布尔表达式E后的“)”时才能知道，而它的“假”出口则需要处理过S1之后并且到el

34、se时才能明确。必须把E.fc的值传下去，以便到达相应的else时才进行回填。(2)S1语句执行完就意味着整个if-else语句也已执行完毕，在S1的编码之后应产生一条无条件转移指令，这条转移指令将导致程序控制离开整个if-else语句。在完成S2的翻译之前，这条无条件转移指令的转移目标是不知道的，甚至在翻译完S2之后仍无法确定，需要传下去，在外层代码翻译的某个时刻填入。第63页，此课件共145页哦2条件语句if的文法和语义子程序的设计条件语句if的文法GS如下：GS：Sif(E)S(1)Sif(E)S(1);elseS(2)为了在扫描条件语句过程中不失时机地处理和回填有关信息，可将GS改写为

35、如下的GS：GS：(1)SCS(1)(2)Cif(E)(3)STpS(2)(4)TPCS(1);else第64页，此课件共145页哦根据程序语言的处理顺序来看语句的翻译。用(2)Cif(E)进行归约。Cif(E)Backpatch(E.tc,nxq);C.chain=E.fc;如条件语句为不含else的条件句，用产生式(1)SCS(1)继续向上归约。SCS(1)S.chain=merge(C.chain,S(1).chain)“)”后的第一个四元式地址回填至E的真出口E的假出口地址则作为待填信息放在C的语义变量C.chain(不然的话，if(E)规约完E的属性值就消失了)E的假出口、S的出口S

36、(1)的出口相同未定，将C.chain和S(1).chain一起作为S的待填信息链用函数merge链在一起保留在S的语义值S.chain中第65页，此课件共145页哦条件语句为不含else的条件句，则在产生式(1)、(2)归约为S后即可以用下一个将要产生的四元式地址(即S的出口地址)来回填S的出口地址链(即S.chain)；在if语句的下一条语句翻译前完成。如果条件语句为if-else形式，用产生式(4)TPCS(1);else归约,产生一个无条件转移四元式。TpCS(1);elseq=nxq;emit(j,_,_,0);Tp.chain=merge(S.chain,q);Backpatch(

37、C.chain,nxq);(1)S(1)语句序列后产生一个无条件转移四元式(见图49的结构框图)，该四元式的地址(即标号)保留在q中，以便待获知要转移的地址后再进行回填(2)q的出口也就是整个条件语句的出口，将其与S.chain链接后挂入链头为Tp.chain的链中。(3)(q+1)地址即为else后(也即S(2)的第一个四元式地址，是E的假出口地址，因此应将此地址回填到E.fc即C.chain中第66页，此课件共145页哦用产生式(3)STpS(2)归约。当，即STpS(2)S.chain=merge(Tp.chain,S(2).chain);S、Tp和S(2)的出口地址一样，在翻译完if语

38、句之后的后继语句才可以填入，可能(非一定)是if语句之后的后继语句翻译得到的四元式地址，故将Tp.chain与S(2).chain链接后挂入链头为S.chain的链中,以便在后续翻译过程中回填跳转地址(如标号为p的四元式的跳转地址)。第67页，此课件共145页哦4.5.2条件循环语句while的翻译1条件循环语句while的代码结构条件循环语句while(E)S(1)通常被翻译成图410所示的代码结构。第68页，此课件共145页哦图410条件循环while语句的代码结构布尔表达式E的“真”出口出向S(1)代码段的第一个四元式，而E的“假”出口将导致程序控制离开整个while语句而去执行whil

39、e语句之后的后继语句。紧接S(1)代码段之后应产生一条转向测试E的无条件转移指令；第69页，此课件共145页哦2条件循环语句while的文法和语义子程序设计为了易于及时处理和回填，给出条件循环语句while的文法GS如下：GS：(1)SWdS(1)(2)WdW(E)(3)Wwhile根据while语句的扫描加工顺序，看语义处理动作：第70页，此课件共145页哦首先用产生式(3)Wwhile进行归约(1)WwhileW.quad=nxq;nxq即为E的第一个四元式地址，我们将其保留在W.quad中(后续语句翻译过程中nxq的值将发生变化)，S(1)后的无条件跳转语句将要跳转到该地址。第71页，此

40、课件共145页哦继续扫描并用WdW(E)归约(2)WdW(E)Backpatch(E.tc,nxq);Wd.chain=E.fc;Wd.quad=W.quad;扫描完“)”后可以用Backpatch(E.tc,nxq)回填E.tc值E.fc作为待填信息用Wd.chain=E.fc传下去(不然的话，WdW(E)规约完E的属性值就消失了)E的第一个四元式地址也通过W.quad向Wd传递第72页，此课件共145页哦用产生式(1)SWdS(1)归约时，S(1)语句序列的全部四元式已经产生。(3)SWdS(1)Backpatch(S(1).chain,Wd.quad);emit(j,_,_,Wd.qua

41、d);S.chain=Wd.chain;无条件返回到E的第一个四元式继续对条件E进行测试S(1)语句序列中的跳转出口语句地址也应该是E的第一个四元式，所以回填S(1).chain无条件转移语句(j,_,_,Wd.quad)之后即为while语句的后继语句，而这个后继语句中的第一个四元式地址即为while语句E的假出口，保存在Wd.chain中。考虑到嵌套情况，将Wd.chain信息作为整个while语句的出口保留在S.chain中，以便适当时机回填。第73页，此课件共145页哦翻译示例例4.3将下面语句翻译成四元式：while(AB)if(CD)X=Y+Z第74页，此课件共145页哦图411例

42、4.3的代码结构图解答我们首先画出该语句对应的代码结构图如图411所示。第75页，此课件共145页哦按照文法及加工子程序(包括前述赋值句和布尔表达式的翻译法)得到该语句对应的四元式序列如下：100(j，A，B，102)/*E1为T*/101(j，_，_，107)/*E1为F*/102(j，C，D，104)/*E2为T*/103(j，_，_，106)/*E2为F*/104(+，Y，Z，T)105(=，T，_，X)106(j，_，_，100)/*转对E的测试*/107第76页，此课件共145页哦4.5.3三种基本控制结构的翻译1三种基本控制结构的文法我们给出三种基本控制结构的文法GS如下：GS：(

43、1)SCS(2)TPS(3)WdS(4)L(5)A/*A代表赋值语句*/(6)LLSS第77页，此课件共145页哦(7)S(8)Cif(E)(9)TPCS;else(10)WdW(E)(11)Wwhile(12)LSL;第78页，此课件共145页哦GS中各产生式对应的语义子程序如下：(1)SCS(1)S.chain=merge(C.chain,S(1).chain);(2)STPS(2)S.chain=merge(TP.chain,S(2).chain);(3)SWdS(1)Backpatch(S(1).chain,Wd.quad);emit(j,_,_,Wd.quad);S.chain=Wd

44、.chain;(4)SLS.chain=L.chain;(5)SAS.chain=0;/*空链*/第79页，此课件共145页哦(6)LLSS(1)L.chain=S(1).chain(7)LSL.chain=S.chain(8)Cif(E)Backpatch(E.tc,nxq);C.chain=E.fc;(9)TPCS(1);elseq=nxq;emit(j,_,_,0);Backpatch(C.chain,nxq);TP.chain=merge(S(1).chain,q);第80页，此课件共145页哦(10)WwhileW.quad=nxq;(11)WdW(E)Backpatch(E.tc,

45、nxq);Wd.chain=E.fc;Wd.quad=W.quad;(12)LSL;Backpatch(L.chain,nxq);第81页，此课件共145页哦例4.4按已学过的文法及语义加工子程序分析下述语句语义加工的全过程：while(xy)x=x+1解答语句while(xy)x=x+1的语义加工过程见表4.3所示。第82页，此课件共145页哦表4.3while(xy)x=x+1#的语义加工过程输入串符号栈语义栈（place）语义动作四元式while(xy)#_移进(xy)x=x+1#while_归约w.quad=100(xy)x=x+1#W_移进xy)x=x+1#W(_移进y)x=x+1#

46、W(x_归约（参见赋值句文法）第83页，此课件共145页哦E1.tc=100i1.place=entry(x)y)x=x+1#W(i1_x移进y)x=x+1#W(i1_x_移进)x=x+1#W(i1y_x_归约i2.place=entry(y)x=x+1#W(i1i2_x_y归约（参见布尔表达式文法）E1.fc=101102100(j,x,y,0)105101(j,_,_,0)x=x+1#W(E1_移进x=x+1#W(E1)_归约第84页，此课件共145页哦Backpatch(100,102)Wd.chain=101x=x+1#Wd_移进=x+1#Wdx_归约i3.place=entry(x)

47、=x+1#Wdi3_x移进x+1#Wdi3=_x_移进+1#Wdi3=x_x_归约E2.place=entry(x)+1#Wdi3=E2_x_x移进1#Wdi3=E2+_x_x_移进#Wdi3=E2+1_x_x_归约第85页，此课件共145页哦E3.place=entry(1)#Wdi3=E2+E3_x_x_1归约E4.place=T1102(+,x,1,T1)#Wdi3=E4_x_归约103(=,T1,_,x)#WdS(1)_归约Backpatch(S(1).chain,100)(因无S(1).chain故不回填)104(j,_,_,100)S.chain=101#S_while语句分析结束

48、外层返填：由LSL归约得：Backpatch(S.chain,105)第86页，此课件共145页哦4.5.4多分支控制语句case的翻译多分支控制语句具有如下形式的语法结构：switch(E)casec1:S1;casec2:S2;caseci:Si;casecn:Sn;default:Sn+1第87页，此课件共145页哦其中n1。switch语句的语义是：先计算整型表达式E的值，然后将表达式的值依次和case后的常数ci比较，当与某常数ci相等时就执行语句Si，并结束多分支控制语句；若与诸常数均不相等，则执行语句Sn+1。多分支控制语句switch常见的中间代码形式如下：E计值后存放在临时单

49、元T的中间代码；第88页，此课件共145页哦gototest；P1:S1的中间代码；gotonext；P2:S2的中间代码；gotonext；Pn:Sn的中间代码；gotonext；第89页，此课件共145页哦default:Sn+1的中间代码；gotonext；test:if(T=c1)gotoP1；if(T=c2)gotoP2；if(T=cn)gotoPn；if(T=default)gotoPn+1；next:第90页，此课件共145页哦进行语义加工处理时应先设置一空队列queue，当遇到ci时，将这个ci连同nxq(指向标号ci后语句Si的入口)送入队列queue，然后按通常的办法产生语

50、句Si的四元式。需要注意的是，在Si的四元式之后要有一个gotonext的四元式。当处理完default:Sn+1之后，应产生以test为标号的n个条件转移语句的四元式。这时，逐项读出queue的内容即可形成如下的四元式序列：第91页，此课件共145页哦(case,c1,P1,_)(case,c2,P2,_)(case,cn,Pn,_)(case,T.place,default,_)其中，T.place是存放E值的临时变量名，每个四元式(case,ci,Pi,_)实际上代表一个如下的条件语句：if(T=ci)gotoPi第92页，此课件共145页哦为了便于语法制导翻译，我们给出了switch语