编译原理(4)语义_2(表达式及赋值语句的翻译)

1、西北农林科技大学本科教程第10讲主讲教师：赵建邦第四章语义分析和中间代码生成 4.1语义分析概述 4. 2属性文法 4.4 表达式及赋值语句的翻译 4. 3几种常见的中间语言 4. 5控制语句的翻译 4.6数组元素的翻译 4.7过程或函数调用语句的翻译 4.8说明语句的翻译 4.9递归下降语法制导翻译方法简介本讲目标第四章语义分析和中间代码生成 4.4表达式及赋值语句的翻译简单算术表达式和赋值语句的翻译布尔表达式的翻译（难点）重点掌握算术表达式语义子程序布尔表达式的真假出口布尔表达式的语义子程序根据翻译图得到布尔表达式的四元式回顾：表达式及赋值语句的翻译 4.4.1简单算术表达式和赋值语句的翻

2、译简单变量：普通变量和常数，不包括数组、结构体成员等复 合型数据结构。简单算术表达式：仅含简单变量的算术表达式简单算术表达式与四元式简单算术表达式的计值顺序与四元式出现的顺序相同，因此彳艮容易将其翻译成四元式形式。当然，这些翻译方法稍加修改也可用于产生三元式或间接三元 式。 1. 3. 3语义分析和中间代码生成（续）-简单算术表达式的计值顺序与四元式出现的顺序相同:-例如，计算圆柱体表面积的C语言程序:s = 2 * 3.1416 * r * (h + r);赋值语句的四元式中间代码:(1) (*,2,3.1416,T1)(2) (*,Tl,r,T2)(3) (+,h,r,T3)(4) (*,

3、T2,T3,T4)(5) (=，T4,s )考虑以下文法GA:A i = E非终结符A代表“赋值句”非终结符E代表“表达式”E-> E+E|EE|-E|(E)|i然，文法GA是一个二义文法，但通过确定运算符的结合性及规定运算符的优先级就可避免二义性的发生。用该文法作为示例的目的：为了更简要地说明语义子程序的 设计过程以及赋值语句的语法制导翻译过程。如，对于赋值语句x=-b*(c+d),已经预先规定运算顺序4. 4表达式及赋值语句的翻译 1.设计6个产生式的语义子程序(1) A i=E p=lookup(); if(p=NULL) error(); else emit(=，Ep

4、lace，_，p);(a)对非终结符E定义语义变量E.place,即用E.place表示存放E 值的变量名在符号表中的入口地址或临时变量名的整数码 例如，赋值语句x = b刚开始读入到符号栈中，显示为 i= i，使用E->i规约，得到:i =E (符号栈)_b (语义栈)所以，E.Place中必须保存b在符 号表中的入口地址；x=b 翻译为(=，b，_，x) 1.设计6个产生式的语义子程序(1) A i=E p=lookup(); if(p=NULL) error();else emit(=，Eplace，_，p);(b)定义语义函数lookup(iname)，其功能是审查终

5、结符 是否出现在符号表中，是则返回在符号表的入口指针， 否则返回N ULLO (c)定义语义函数emit(oparglarg2result), emit的功能是产 生一个四元式并填入四元式表中。(2) EE(i)+EE.place=newtemp();emit(+，E(l)place, E(2)place, E.place);(3) EE(i)*E(2)E.place=newtemp();4. 4表达式及赋值语句的翻译(4) E-Eemit(*,E(l).place, E(2)>place,E.place);E.place=newtemp();emit(uminu

6、s9 E.place， E.place);(d)定义语义函数newtemp()，即每次调用newtemp()时都将回送一个代表新临时变量的整数码；临时变量名按产生的顺序可 设为Tl. T2(5) E(E(D)(6) ET E.place= E.place ; p=lookup(); if(p!=NULL) E.place=p; else error ( );例42试分析赋值语句X=B*(C+D)的语法制导翻译过程解答赋值语句X=B*(C+D)的语法制导翻译过程如表4.2所示(加工分析过程参考表41)。其实，利用带注释的语法树进行规约的同时,就可以完成相应的语义分析(一起看黑板)O表

7、42 赋值语句X=-B*(C+D)的翻译过程输入串归约产生式符号栈语义栈(place)四元式X=-B*(C+D)#=-B*(C+D)#-B*(C+D>/#i=B*(C+D)#憑二-_ _ _ _*(C+D 肖#i=-i*(C+D 肖(6)憑二-EB*(C+D)#(4)#i=ETi(wnmus,B,Ti)(C+D 肖#i=E*C+D鸭#i=E*(+D)#姐二E*(i -Ti- 表4.2(2)赋值语句X=-B%C+D)的翻译过程+D)#(6)#i=E*(ED)#i=E*(E+T C)#1 甘(E+i入C)#(6)#1二E*(E+ECD)#(2)#i=E*(E(+,C叽#i=E*(E)#(5)

8、#i=E*E:Ti T2#i=E丄(*,Ti,T皿)#(1)#AX仁 T3, ,X)4.4 表达式及赋值语句的翻译 4.4.2布尔表达式的翻译1、布尔表达式的组成布尔表达式：由运算符与运算对象组成。 定义布尔变量 A、B、C、D运算符：非1 （单目）、与A （双目）、或P （双目） 注意:1、优先级：-> A > V2、人和V服从左结合3、运算符的优先级：算术A关系布尔运算对象（三种）:布尔变量布尔常量（false、true）关系表达式1 运算符 Fop ： V、= =、！=、=、2.运算对象：算术表达式 3.返回值类型：bool类型例：bool a,b,c; int x,y,z思

9、考：运算顺序？ ？a = b V c A true V (x+y >= z)a = b V c A true V x+y >= z2. 布尔表达式的计算 了解1:对布尔运算.关系运算.算术运算的运算对象的类型 可不区分布尔型或算术型，假定不同类型的变换工作将在需要时强制执行。思考：C语言的强制转换？ ？ 了解2:布尔表达式在程序语言中不仅用作计算布尔值，还作为控制语句（如if-else while等）的条件表达式，用以确定程序的控制流向。无论布尔表达式的作用如何，按照程序执行的顺序，都必须先计算出布尔表达式的值。计算布尔表达式的值有两种方法: K按照优先级和各变量的值，一步步求出结

10、果; 2优化计算:b = true; a = b V c ;（不计算c，a=true）b = false; a = b A c ;（不计算c，a=false）4. 4表达式及赋值语句的翻译2.布尔表达式的计算所以，按照优化方式计算布尔表达式，需要给出整个表达式的真假出口。“真”岀口真出口：若E为真，则E为真； 若忙为真，则E为真； 所以E的真出口有两个:E的真出口和E的真出口。（a） E = EVE（2） （2）假出口:E的假出口并不是E的假出口 ,E如果为假,必须计算E,因此：E的假出口是整个E的假出口。2.布尔表达式的计算假出口：若E为假，则E为假；若已为假，则E为假； 所以E的假出口有两

11、个：E的假出口和E的假出口。EA即假”出口(b) E = E A E (2)真出口：E的真出口并不是E的真出口，E如果为真，必须计算E(2), 因此：E的真出口是整个E的真出口。练习布尔表达式aAbVc>d的真假出口。布尔表达式中，每个布尔分量一般至少对应两个四元式。例如：E = E（i）VE= aVb 对应：（l）（jnz, 真出口 ）（J亠3）（Jnz, b,_,真出口）if(a II b) c=l;（4）幺-_，假出口） （6） if语句后面的四元式在这个例子中，真出口和假出口不能在生成四元式的当时产生；假如a和b并不是简单的布尔变量，或者条件语句后执行 的语句并不是仅仅一句，所有

12、的真假出口都无法给定。4. 4表达式及赋值语句的翻译3. 布尔表达式的文法： (1)普通布尔表达式文法：GE:E->EAE I EVE | n E | (E) | i | i rop i (2)优化的布尔表达式文法：GE： EtEAE I EBE | -| E | (E) | i | i rop iEAE/EB->EV好处：在句子中，如果出现"aVb"或tta A b"之类的表达式，当扫描到或"a A"之后就立即可以进行规约，不用去关系b的取值。4. 解决“真”.“假"出口问题的方法：拉链和回填 （1）拉链：在同一个表达式

13、内，每个四元式产生的时候，强制 其出口为0,若后面一个四元式和它出口相同，用前面产生式 的序号去填充后面产生式的跳转位置（result）,从而将不同 的四元式链接起来，俗称“拉链”。(i) (_，亠，(J)(k)0)假如下面三个四元式都是真出口 :（i）（亠，0）（亠，0）（k）（亠，_）注意：（k）为链首，（i）为链尾，链尾result=0拉链算法:Pl，P2各自是两个链首，将它们合并成一个以P2为链首的新链mergeCpj ,p2) if(p2=0) return(p!); else P=P2；while(四元式p的第四区段内容不为0) p=四元式p的第四区段内容；把P1填进四元式P的第四

14、区段； return(p2); / else / merge(rj0)(Qi)(Pi)qj(r2)0)(q2)勺)(p2)q?)算法执行完，其实就是将(Fj)中的result变为Pl，最终形成一个链 (2)回填算法：把链首p所链接的每个四元式的第四区段(result)都改写为地址t。Backpatch(p int t) Q=P； while(Q!=O) q=四元式Q的第四区段内容; 把t填进四元式Q的第四区段;Q=q; / while(r)(亠(q)(p) (_，_(r)t)(q),t)(p)，t) /Backpatch其它需要说明的问题：1>对于每个非终结符E,我们需要为它赋予两个语义

15、值E.tc和E.fc，分别用来记录E所对应的四元式的真链和假链。也就是说，为每个非终结符E添加两个属性：tc和fc;因此，规约的时候，再次扩充语义栈，添加tc栈和fc栈;2> nxq:这是一个int变量，翻译工作开始之前，初始值 是1,翻译工作开始之后，每执行一次emit(), nxq自增1, 即：nxq =四元式个数+1;4. 4表达式及赋值语句的翻译5. 布尔表达式的翻译 1.文法：GE： E->EAE I EBE | -| E | (E) | i | i rop iEA->EAEB->EV 2语义子程序:(1) E->i (布尔值) E.tc=nxq; E.

16、fc=nxq+1; emit(jnz,entry (i),_,0);例如 if(a) b;(2) Ei rop i(2) E.tc=nxq; E.fc=nxq+1;emit(jrop5 entry(i(1)9 entry(i)，0);(3) Ef (E) E.tc = Etc; E.fc = Efc;(4) E->|E(i) E.tc = E.fc; E.fc = Etc;(5) EAE/ Backpatch( Eg nxq);EA.fc = Efc; 说明（5）:如果E为真，表达式的值取决于/之后，可以回填E的tc链，跳转到nxq ;如果E为假，那么不必计算后面，EA直接为假。(6)

17、EEAE E.tc = E(2).tc;(7) EBE V(8) EEBE(2)E.fc =merge( EA.fc, Efc); Backpatch(E(1).fc, nxq);EB.tc = Etc; E.fc = Efc;E.tc = merge(EB.tc, Etc);说明(8):能使用(8)规约，说明E为假，E的真出口必须链 接到砂)，因此要拉链操作；E的真假出口都必须依赖于已， 因此E.fc = Efc; E.tc = Etc; 3.步骤:首先规约布尔表达式，如ttaAbVc>d",通过语义子程序翻译出初始的四元式;添加真假出口的四元式标记 回填真假出口，经判断得知

18、， 整个布尔表达式的真出口是106, 假出口是q(回填链尾为0的tc、fc)if (aAbVc>d) else 100 (jnz, a,102)1010,104)102 (jnz, b,0)103 0,104)104 g>, c, d, 102)105 0, _，_，0)T: 106 F:例4.3试给出布尔表达式aAbVc>d作为控制条件的四元式中 间代码。解答设四元式序号从100开始，则布尔表达式aAbVc>d的 分析过程为：初始输入：aAbVc>dtE>i (布尔值) E.tc=nxq; E.fc=nxq+1;emit(jnz,entry (i),_,0

19、);emit6，_，_，()；规则：EiEAbVc>d语义栈(tc/fc)四元式：100 (jnz, a, _ , 0)E.tc 二 100E.fc=1014. 4表达式及赋值语句的翻译4. 4表达式及赋值语句的翻译规则： EA_>e /EAbVc>d语义栈(tc/fc)规则：EiEAE VcR语义栈(tc/fc)E.tc=102规则：E->EAE(2)EVc>d语义栈(tc/fc)E.tc=102四元式：100 (jnz,102)101(j,_,_,0) nxq = 102EA.fc=101四元式：102 (jnz, b,_,0)103(j,_,_,0)E.fc

20、 二 103EA.fc=101四元式：E.fc 二 1034. 4表达式及赋值语句的翻译4. 4表达式及赋值语句的翻译规则：EB_>E VEBc>dEB.tc 二 102语义栈(tc/fc)：四元式：101一 104)103亠，104)规则：E>i rop iEBEE.tc 二 104E.fc=105EB.tc 二 102语义栈(tc/fc)：四元式：104 m 0)105 一 0)规则：E EBE E四元式：104 (jN c 102)E.tc=102E.fc 二 105语义栈(tc/fc)：4. 4表达式及赋值语句的翻译4. 4表达式及赋值语句的翻译第一步结束，得到aAbVc>d的四元式如下:100 (jnz, a, 102)1010,104)102 (jnz, b, 0) _103 0,104)104 g>,