编译原理语义2(表达式及赋值语句的翻译).ppt

第 10 讲,编译原理,西北农林科技大学本科教程,主讲教师：赵建邦,第四章 语义分析和中间代码生成,4.1 语义分析概述 4.2 属性文法 4.3 几种常见的中间语言 4.4 表达式及赋值语句的翻译 4.5 控制语句的翻译 4.6 数组元素的翻译 4.7 过程或函数调用语句的翻译 4.8 说明语句的翻译 4.9 递归下降语法制导翻译方法简介,第四章语义分析和中间代码生成 4.4 表达式及赋值语句的翻译 简单算术表达式和赋值语句的翻译 布尔表达式的翻译(难点) 重点掌握 算术表达式语义子程序 布尔表达式的真假出口 布尔表达式的语义子程序 根据翻译图得到布尔表达式的四元式,本讲目标,4.4 表达式及赋值语句的翻译,4.4.1 简单算术表达式和赋值语句的翻译 简单变量：普通变量和常数，不包括数组、结构体成员等复合型数据结构。 简单算术表达式：仅含简单变量的算术表达式 简单算术表达式与四元式,简单算术表达式的计值顺序与四元式出现的顺序相同，因此很容易将其翻译成四元式形式。,当然，这些翻译方法稍加修改也可用于产生三元式或间接三元式。,1.3.3 语义分析和中间代码生成（续） 简单算术表达式的计值顺序与四元式出现的顺序相同： 例如，计算圆柱体表面积的C语言程序： s = 2 * 3.1416 * r *（h + r）; 赋值语句的四元式中间代码： （1）（*，2, 3.1416，T1） （2）（*，T1, r， T2） （3）（+，h, r， T3） （4）（*，T2, T3， T4） （5）（=，T4, _， s ）,回顾： 表达式及赋值语句的翻译,考虑以下文法GA: A i = E E E+E | E*E | E | (E) | i,4.4 表达式及赋值语句的翻译,显然，文法GA 是一个二义文法，但通过确定运算符的结合性及规定运算符的优先级就可避免二义性的发生。,用该文法作为示例的目的：为了更简要地说明语义子程序的设计过程以及赋值语句的语法制导翻译过程。 如，对于赋值语句x=-b*(c+d)，已经预先规定运算顺序,非终结符A代表“赋值句”,非终结符E代表“表达式”,4.4 表达式及赋值语句的翻译,1.设计6个产生式的语义子程序,(1) A i=E p=lookup(); if(p=NULL) error( ); else emit(=,E.place,_,p); ,例如，赋值语句 x = b 刚开始读入到符号栈中，显示为 i = i, 使用E i规约，得到： i = E（符号栈） _ _ b（语义栈）,(a)对非终结符E定义语义变量E.place，即用E.place表示存放E值的变量名在符号表中的入口地址或临时变量名的整数码,所以，E.Place中必须保存b在符号表中的入口地址；,x=b 翻译为( =, b, _ , x),4.4 表达式及赋值语句的翻译,1.设计6个产生式的语义子程序,(1) A i=E p=lookup(); if(p=NULL) error( ); else emit(=,E.place,_,p); ,(b) 定义语义函数lookup()，其功能是审查终结符是否出现在符号表中，是则返回在符号表的入口指针，否则返回NULL。,(c) 定义语义函数emit(op,arg1,arg2,result)，emit的功能是产生一个四元式并填入四元式表中。,4.4 表达式及赋值语句的翻译,(2) E E(1)+E(2) E.place=newtemp( ); emit(+,E(1).place, E(2).place, E.place); ,(d) 定义语义函数newtemp( )，即每次调用newtemp( )时都将回送一个代表新临时变量的整数码；临时变量名按产生的顺序可设为T1、T2,(3) E E(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); ,4.4 表达式及赋值语句的翻译,(5) E(E(1) E.place= E(1).place ;,(6) Ei p=lookup(); if(p!=NULL) E.place=p; else error ( ); ,例4.2 试分析赋值语句X= -B*(C+D)的语法制导翻译过程。 解答 赋值语句X=-B*(C+D)的语法制导翻译过程如表4.2所示(加工分析过程参考表4.1)。,其实，利用带注释的语法树进行规约的同时，就可以完成相应的语义分析（一起看黑板）。,表4.2(1) 赋值语句X=B*(C+D)的翻译过程,表4.2(2) 赋值语句X=B*(C+D)的翻译过程,4.4 表达式及赋值语句的翻译,4.4.2 布尔表达式的翻译 1、布尔表达式的组成 布尔表达式：由运算符与运算对象组成。 定义布尔变量 A、B、C、D A = bop1 B bop2 C bop3 D (1)运算符：非（单目）、与 （双目）、或 （双目） 注意：1、优先级： 2、和服从左结合 3、运算符的优先级：算术 关系布尔“=”,4.4 表达式及赋值语句的翻译,(2)运算对象(三种)： 布尔变量 布尔常量（false、true） 关系表达式 1、运算符rop ： =、 2、运算对象：算术表达式 3、返回值类型：bool类型 例：bool a,b,c; int x,y,z a = b c true (x+y = z) a = b c true x+y = z,思考：运算顺序？,4.4 表达式及赋值语句的翻译,2、布尔表达式的计算 了解1：对布尔运算、关系运算、算术运算的运算对象的类型可不区分布尔型或算术型，假定不同类型的变换工作将在需要时强制执行。 了解2：布尔表达式在程序语言中不仅用作计算布尔值，还作为控制语句(如if-else、while等)的条件表达式，用以确定程序的控制流向。无论布尔表达式的作用如何，按照程序执行的顺序，都必须先计算出布尔表达式的值。 计算布尔表达式的值有两种方法： 1、按照优先级和各变量的值，一步步求出结果； 2、优化计算： b = true; a = b c ; (不计算c, a=true) b = false; a = b c ; (不计算c, a=false),思考：C语言的强制转换？,4.4 表达式及赋值语句的翻译,2、布尔表达式的计算 所以，按照优化方式计算布尔表达式，需要给出整个表达式的真假出口。 (1) 真出口： 若E(1)为真，则E为真； 若E(2)为真，则E为真； 所以E的真出口有两个： E(1)的真出口和E(2)的真出口。 (2) 假出口： E(1)的假出口并不是E的假出口，(1)如果为假，必须计算E(2) ，因此：E(2)的假出口是整个的假出口。,(a) E = E(1)E(2),4.4 表达式及赋值语句的翻译,2、布尔表达式的计算 (1) 假出口： 若E(1)为假，则E为假； 若E(2)为假，则E为假； 所以E的假出口有两个： E(1)的假出口和E(2)的假出口。 (2) 真出口： E(1)的真出口并不是E的真出口，(1)如果为真，必须计算E(2) ，因此：E(2)的真出口是整个的真出口。 练习布尔表达式 abcd 的真假出口。,(b) E = E(1) E(2),4.4 表达式及赋值语句的翻译,布尔表达式中，每个布尔分量一般至少对应两个四元式。 例如：E = E(1)E(2) = ab if(a | b) c=1; 对应: (1)(jnz, a,_,真出口） (2)(j,_,_,3) (3)(jnz, b,_,真出口) (4)(j,_,_,假出口) (5)(=,c,_,1) (6)if语句后面的四元式 在这个例子中，真出口和假出口不能在生成四元式的当时产生；假如a和b并不是简单的布尔变量，或者条件语句后执行的语句并不是仅仅一句，所有的真假出口都无法给定。,4.4 表达式及赋值语句的翻译,3、布尔表达式的文法： (1) 普通布尔表达式文法： (2) 优化的布尔表达式文法： 好处：在句子中，如果出现 “ab”或“a b”之类的表达式，当扫描到“a”或“a ”之后就立即可以进行规约，不用去关系b的取值。,GE: EEE | EE | E | (E) | i | i rop i,GE： EEAE | EBE | E | (E) | i | i rop i EAE EBE,4.4 表达式及赋值语句的翻译,4、解决“真”、“假”出口问题的方法：拉链和回填 (1) 拉链：在同一个表达式内，每个四元式产生的时候，强制其出口为0，若后面一个四元式和它出口相同，用前面产生式的序号去填充后面产生式的跳转位置（result），从而将不同的四元式链接起来，俗称“拉链”。,假如下面三个四元式都是真出口： (i) ( _ , _ , _ , 0) (j) ( _ , _ , _ , 0) (k) ( _ , _ , _ , 0),注意：(k)为链首，(i)为链尾，链尾result=0,4.4 表达式及赋值语句的翻译,(1) 拉链算法： p1 ,p2各自是两个链首，将它们合并成一个以p2为链首的新链,merge(p1 ,p2) if(p2=0) return(p1); else p=p2; while(四元式p的第四区段内容不为0) p=四元式p的第四区段内容； 把p1填进四元式p的第四区段； return(p2); / else / merge,(r1) ( _ , _ , _ , 0) (q1) ( _ , _ , _ , r1) (p1) ( _ , _ , _ , q1),(r2) ( _ , _ , _ , 0) (q2) ( _ , _ , _ , r2) (p2) ( _ , _ , _ , q2),算法执行完，其实就是将(r2) 中的result变为p1，最终形成一个链,4.4 表达式及赋值语句的翻译,(2) 回填算法：把链首p所链接的每个四元式的第四区段(result)都改写为地址t。,Backpatch(p, int t) Q=p; while(Q!=0) q=四元式Q的第四区段内容； 把t填进四元式Q的第四区段； Q=q; / while /Backpatch,4.4 表达式及赋值语句的翻译,(3) 其它需要说明的问题： 1、对于每个非终结符E，我们需要为它赋予两个语义值 E.tc和E.fc，分别用来记录E所对应的四元式的真链和假链。 也就是说，为每个非终结符E添加两个属性：tc和fc；因此， 规约的时候，再次扩充语义栈，添加tc栈和fc栈； 2、nxq:这是一个int变量，翻译工作开始之前，初始值 是1，翻译工作开始之后，每执行一次emit()，nxq自增1， 即： nxq = 四元式个数+1；,4.4 表达式及赋值语句的翻译,5、布尔表达式的翻译 1、文法： 2、语义子程序： 例如 if(a) b;,GE： EEAE | EBE | E | (E) | i | i rop i EAE EBE,Ei （布尔值） E.tc=nxq; E.fc=nxq+1; emit(jnz,entry(i),_,0); emit(j,_,_,0); ,(2) Ei(1) rop i(2) E.tc=nxq; E.fc=nxq+1; emit(jrop, entry(i(1), entry(i(2),0); emit(j,_,_,0); ,4.4 表达式及赋值语句的翻译,说明 (5): 如果E(1)为真，表达式的值取决于之后，可以回填 E(1)的tc链，跳转到nxq ; 如果E(1)为假，那么不必计算后面， EA直接为假。,(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; ,(5) EAE(1) Backpatch( E(1).tc, nxq); EA.fc = E(1) .fc; ,(6) EEAE(2) E.tc = E(2).tc; E.fc =merge( EA.fc，E(2).fc); ,4.4 表达式及赋值语句的翻译,(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); ,说明 (8): 能使用(8)规约，说明E(1)为假， E(1)的真出口必须链接到E(2)，因此要拉链操作；E的真假出口都必须依赖于E(2) ，因此E.fc = E(2).fc; E.tc = E(2).tc;,4.4 表达式及赋值语句的翻译,3、步骤： (1) 首先规约布尔表达式，如“abcd”，通过语义子程序翻译出初始的四元式； (2) 添加真假出口的四元式标记 (3) 回填真假出口，经判断得知， 整个布尔表达式的真出口是106， 假出口是q(回填链尾为0的tc、fc),100 (jnz，a，_，102) 101 (j，_，_，104) 102 (jnz，b，_，0) 103 (j，_，_，104) 104 (j，c，d，102) 105 (j，_，_，0),T: 106 F: q,if (abcd) else ,4.4 表达式及赋值语句的翻译,例4.3 试给出布尔表达式abcd作为控制条件的四元式中间代码。,解答 设四元式序号从100开始，则布尔表达式abcd的 分析过程为：,规则： Ei Ebcd,初始输入： abcd,语义栈(tc/fc)：,四元式： 100 (jnz, a, _ , 0) 101 (j, _ , _ , 0),Ei （布尔值） E.tc=nxq; E.fc=nxq+1; emit(jnz,entry(i),_,0); emit(j,_,_,0); ,规则： EAE(1) EA bcd,语义栈(tc/fc)：,四元式： 100 (jnz, a, _ , 102) 101 (j, _ , _ , 0) nxq = 102,4.4 表达式及赋值语句的翻译,规则： Ei EA E(2)cd,语义栈(tc/fc)：,四元式： 102 (jnz, b, _ , 0) 103 (j, _ , _ , 0),规则： EEAE(2) Ecd,语义栈(tc/fc)：,四元式： 101 (j, _ , _ , 0) 103 (j, _ , _ , 101),4.4 表达式及赋值语句的翻译,规则： EBE(1) EB cd,语义栈(tc/fc)：,四元式： 101 (j, _ , _ , 104) 103 (j, _ , _ , 104),规则： Ei rop i EB E,语义栈(tc/fc)：,四元式： 104 (j, c , d , 0) 105 (j, _ , _ , 0),规则： E EBE(2) E,语义栈(tc/fc)：,四元式： 104 (j, c , d , 102),4.4 表达式及赋值语句的翻译,第一步结束，得到 abcd 的四元式如下：,100 (jnz，a，_，102) 101 (j，_，_，104) 102 (jnz，b，_，0) 103 (j，_，_，104