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

,第二级,第三级,第四级,第五级,第 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(i.name);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,(i.name);if(p=NULL)error(,);else,emit,(=,E.place,_,p);,(b)定义语义函数,lookup,(i.name)，其功能是审查终结符i.name是否出现在符号表中，是则返回i.name在符号表的入口指针，否则返回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(i.name);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类型,4.4 表达式及赋值语句的翻译,2、布尔表达式的计算,了解1：,对,布尔运算、关系运算、算术运算的运算对象的类型,可,不区分布尔型或算术,型。,在计算中默认强制转换。,a=b,c,true,(x+y=z),了解2：,布尔表达式在程序语言,中：,用作,计算,布尔值；,作为,控制语句(如if-else、while等)的条件,表达式。,4.4 表达式及赋值语句的翻译,2、布尔表达式的计算,计算布尔表达式的值有两种方法：,1、按照优先级和各变量的值，一步步求出结果；,2、优化计算：,b=,true,;a=b,c,;(不计算c,a=,true,),b=,false,;a=b,c,;(不计算c,a=,false,),例：a=b,c,true,(x+y=z),思考：运算顺序？,4.4 表达式及赋值语句的翻译,3、真假出口之一：,E=E,(1),E,(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 表达式及赋值语句的翻译,3、真假出口之二：,E=E,(1),E,(2),(1)假出口：,若,E,(1,),为假，则E为,假,；,若,E,(2),为假，,则E,为,假,；,所以E的假出口,有两个：,E,(1),的,假,出口和,E,(2),的,假,出口。,(2)真出口：,E,(1,),的,真,出口并不是E的,真,出口，,(1),如果为,真,，必须计算,E,(2),，因此：,E,(2,),的,真,出口是,整个的真出口。,练习布尔表达式,a,bc,d,的真假出口。,(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)(=,1,_,c ),(6),if语句后面的四元式,在这个例子中，真出口和假出口不能在生成四元式的当时产生；假如a和b并不是简单的布尔变量，或者条件语句后执行的语句并不是仅仅一句，所有的真假出口都无法给定。,4.4 表达式及赋值语句的翻译,4、布尔表达式的文法：,(1)普通布尔表达式文法：,(2)优化的布尔表达式文法：,好处：在句子中，如果出现“a,b,”或,“,a,b”之类的表达式，当扫描到,“a,”或,“a,”之后就立即可以进行规约，不用去关系b的取值。,GE:,EEE|EE|E|(E)|i|i rop i,GE：,EE,A,E|E,B,E|E|(E)|i|i rop i,E,A,E E,B,E,4.4 表达式及赋值语句的翻译,5、解决“真”、“假”出口问题的方法：拉链和回填,(1)拉链：在同一个表达式内，当前i号四元式产生的时候，强制其出口为0，若j号（ji）四元式和它出口相同，用,i,去填充,j,号四元式的（result），从而将不同的,四元式,链接起来，俗称“拉链”。,假如下面三个四元式都是真出口：,(i)(_,_,_,0,),(j)(_,_,_,0,),(k)(_,_,_,0,),注意：(k)为链首，(i)为链尾，链尾result=0,(i)(_,_,_,0),(j)(_,_,_,i),(k)(_,_,_,j),4.4 表达式及赋值语句的翻译,(1)拉链,算法,：,p,1,p,2,各自是两个链首，将它们合并成一个以,p,2,为链首的新链,merge(p,1,p,2,)if(p,2,=0)return(p,1,);else p=p,2,;while(四元式p的第四区段内容不为0)p=四元式p的第四区段内容；把p,1,填进四元式p的第四区段；return(p,2,);/else /merge,(,r,1,)(_,_,_,0),(,q,1,)(_,_,_,r,1,),(,p,1,)(_,_,_,q,1,),(,r,2,)(_,_,_,0,),(,q,2,)(_,_,_,r,2,),(,p,2,)(_,_,_,q,2,),算法执行完，其实就是将(,r,2,)中的result变为,p,1,，最终形成一个链,4.4 表达式及赋值语句的翻译,(2)回填,算法,：把链首p所链接的每个四元式的第四区段(result)都改写为地址t。,(r)(_,_,_,0),(q)(_,_,_,r),(p)(_,_,_,q),Backpatch(p,int,t)Q=p;while(Q!=0)q=四元式Q的第四区段内容；把t填进四元式Q的第四区段；Q=q;/while/Backpatch,(r)(_,_,_,t,),(q)(_,_,_,t,),(p)(_,_,_,t,),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 表达式及赋值语句的翻译,例4.3,试给出布尔表达式,abcd,作为控制条件的四元式中间代码。,解答,设四元式序号从,100,开始，则布尔表达式,abcd,的,分析过程为：,规则：,(1)Ei,E,bcd,初始输入：,a,bcd,语义栈(tc/fc)：,E,E.tc=100,E.fc=101,四元式：,100(jnz,a,_,0),101(j,_,_,0),nxq=102,(1)Ei（,布尔值,）E.tc=nxq;E.fc=nxq+1;emit(jnz,entry(i),_,0);,emit(j,_,_,0);,规则：,(5)E,A,E,(1),E,A,bcd,语义栈(tc/fc)：,四元式：,100(jnz,a,_,102,),101(j,_,_,0),nxq=102,4.4 表达式及赋值语句的翻译,(5)E,A,E,(1),Backpatch