布尔表达式的翻译.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Chapter 5.5,布尔表达式的翻译,1.,概述,布尔表达式,是布尔运算量和逻辑运算符按一定语法规则组成的式子。,逻辑运算符,通常有,、,、,三种（在某些语言中，还有,（等价）及,（蕴含）等等）；,逻辑运算对象,可以是逻辑值（,True,或,False,）、布尔变量、关系表达式以及由括号括起来的布尔表达式。,不论是布尔变量还是布尔表达式，都只能取逻辑值,True,或,False,。在计算机内通常用,1,（或非零整数）表示真值（,True,），用,0,表示假值,(,False,),。,关系表达式,是形如,E,1,Rop,E,2,的式子，其中,E,1,和,E,2,为简单算术表达式，,Rop,为关系运算符（,=,=,）。若,E,1,和,E,2,之值使该关系式成立，则此关系表达式之值为,True,，否则为,False,。,2.,布尔表达式的语义及作用,布尔表达式,的语义在于指明计算一个逻辑值的规则,.,布尔表达式,在程序设计语言中有两个基本的作用：,一是在某些控制语句中作为,实现控制转移的条件,；,另一个则是用于,计算逻辑值本身,。,约定,:,各类运算符的优先顺序（由高至低）如下：,括号,算术运算符,*、,/,+,、,-,关系运算符,、,、,=,、,逻辑运算符,3.,布尔表达式的等价解释,-,求值角度,为了方便起见，下面我们仅讨论由文法,E EE|EE|E|(E)|I|i,Rop,i,(5.1),1,）可采用类似,算术表达式,的方式来进行。例如，对于,布尔表达式,ABC,，可翻译为：,(,B,C,T1),(,A,T1,T2),3.,布尔表达式的等价解释,-,过程角度,但是，对于一个,布尔表达式,而言，我们的目的,仅仅是为了判定它的真假值,。因此，有时只需计算它的一个子表达式，便能确定整个,布尔表达式,的真假值。例如，对于,AB,，只要知道,A,为真，则无论,B,取何值，表达式的结果一定为真。,可见，对于三种常见逻辑运算，可作如下等价的解释：,AB,(A)?B:0(5.2),AB,(A)?1:B(5.3),A (A)?0:1(5.4),4.,布尔表达式的出口,对于,布尔表达式,A,（,B,（,CD,）,),，其等价的表述是,A,？,1,：（,B,？（,C,？,0,：,1,）？,1,：,D,）：,0,）,显然，采用此种结构可产生更为有效的中间代码。这里需假定原,布尔表达式,的计算过程中不含有任何的,副作用,。,在上式的计算中，根据,A,、,B,、,C,、,D,的取值不同，计算的结果以及运算的终止点亦不同。例如，当,A=1,（真）时，结果为,1,且终止于左边第一个,1,处。,这样终止的点我们称为该,布尔表达式,的,出口,，同时，把使,布尔表达式,取值为,真,的,出口,称为,真出口,，反之称为,假出口,。,对一个,布尔表达式,而言，它至少有一个,真出口,和一个,假出口,（当然可以有多个）。在用于控制流程的,布尔表达式,E,的计算中，这些,出口,分别指出当,E,值为,真,和,假,时，,控制所应转向的目标,（即某一四元式的序号）。,5.,控制语句中的布尔表达式,if,E,then,S1,else,S2,或,while,E,do,S,T,E,的代码,S,1,的代码,S,2,的代码,E,的代码,S,的代码,T,F,F,(a),if,语句,(b),while,语句,6.,布尔表达式真假值的确定,一个布尔表达式,E,的真假值的确定，是在语法翻译过程中，根据,(5.2)-(5.4),等价解释式逐步进行的。,例如，对于布尔表达式,E=E,(1),E,(2),若,E,(1),为真，则,E,必为真，故,E,(1),的,真出口,必是,E,的,真出口,(,之一,);,若,E,(1),为假，则,E,的真假值取决于,E,(2),的真假值，此时，需对,E,(2),进行计算，由此可见，,E,(1),的,假出口,应为,E,(2),对应的四元式的序号,(,E,(2),的入口,),，同时,E,(2),的真、假出口也是,E,的真、假出口。,类似地，可确定,E,(1),E,(2),、,E,及更复杂的表达式的,真、假出口,。,7.,条件语句的翻译结果,在设计布尔表达式翻译算法（即编写语义动作）时，可定义和使用如下三类四元式：,(,jnz,A1,p),当,A1,为真,(,非零,),时，转向第,p,四元式；,(jrop,A1,A2,p),当关系,A1,rop,A2,成立时，转向第,p,四元式；,(j,p),无条件转向第,p,四元式,例如，对于条件语句,if,ABC,then,S,1,else,S,2,经翻译后，可得四元式序列：,(1)(,jnz,A,-,5),(2)(,j,-,-,3),(3)(,j,B,C,5),(4)(,j,-,-,p+1),(5),S,1,相应的四元式序列,(p)(,j,-,-,q),(p+1),S,2,相应的四元式序列,(q),其中，表达式,A,的真出口为,5,（也是整个表达式的真出口），假出口为,3,（即表达式,BC,的第一四元式）；,BC,的真、假出口也分别是整个表达式的真、假出口。,8.,拉链与回填,在自底向上的,语法制导翻译,时（或者说，在,S-,属性翻译文法,中,),在产生一个,(,无,),条件转移四元式时,它所要转向的那个四元式有时尚未产生，故无法立即产生一个完全的控制转移四元式。,例如，在上例中，在产生第一个四元式时，由于语句,S,1,的中间代码尚未产生，即,A,的真出口确切位置并不知道，故此时只能产生一个,空缺转移目标,的四元式,(,jnz,A,-,0,),并将此四元式的序号,(,即,1,),作为语义信息存起来，待开始翻译,S,1,时，再将,S,1的第一四元式的序号,(,即,5,),回,填,这个不完全的四元式。,另外，在翻译过程中，常常会出现,若干转移四元式转向同一目标,，但此目标的具体位置又尚未确定的情况，此时我们可将这些四元式用,拉链,的办法将它们链接起来，用一指针指向链头，在确定了目标四元式的位置之后，再,回填,这个,链,。,对于一个布尔表达式,E,来说，它应有两条链：,真出口链,(,称为,T,链,，记作,TC,),和,假出口链,(,称为,F,链,，记作,FC,),。它们就是非终结符,Expr,的两个属性,Expr.TC,及,Expr.FC,。,例如，对于上述,if,语句中的布尔式,E,=,A,B,0,时,它给出本链的后继四元式的序号，,Result,=,0,时表示本四元式是链尾结点。,(1)(jnz,A,-,0),(2)(j,-,-,3),E.TC,(3)(j,B,C,1),E.FC,(4)(j,-,-,0),ABC,的四元式,序列及其,TC,链和,FC,链,9.,文法的“拆分”,为便于实现布尔表达式的语法制导翻译，我们先改写文法，以便能在翻译过程中的适当时机获得所需的语义属性值。例如，可将文法,(,5.1),改写为：,Expr,Expr,Expr,|,Expr,Expr,|,Expr,|,iden,|,iden,Rop,iden,|(,Expr,),Expr,Expr,Expr,Expr,(5.7),将文法进行“拆分,”的,目的,:,1.,在翻译完运算符,（,）左侧的表达式后，能够及时获取其语义属性,TC,及,FC,2.,完成用下一四元式序号（即运算符右侧表达式的第一四元式之序号）回填前一表达式的相应真（假）链,TC,（,FC,），,3.,将其另一链,FC,（,TC,）作为产生式左部符号的综合属性,FC,（,TC,）传播之。,10.,语义变量及辅助语义函数,1.,NXQ,全局变量，用于指示所要产生的下一四元式的序号；,2.,GEN,（,）,其意义同前,每次调用,NXQ,+,；,3.,int,Merge,(,int,p1,int,p2,),将链首“指针”分别为,p1,和,p2,的两条链合并为一条，并返回新链的链首“指针”（此处的“指针”实际上是四元式的序号，应为整型值）我们假定四元式是以一结构形式表示（存储）的：,struct,_Quadruple,int,Op,arg1,arg2,Result,;,QuadrupleList,;,4.,void,BackPatch,(,int,p,int,t,),用四元式序号,t,回填以,p,为首的链，将链中每个四元式的,Result,域改写为,t,的值。,函数,Merge,(),及,BackPatch,(),的程序见书,11.,翻译布尔表达式的属性文法,1.Expriden,$.TC=NXQ;$.FC=NXQ+1;,GEN(jnz,Entry($1),0,0,);GEN(j,0,0,0,);,|,iden,rop,iden,$.TC=NXQ;$.FC=NXQ+1;,GEN(jrop,Entry($1),Entry($3),0,);,GEN(j,0,0,0,);,|(,Expr,),$.TC=$2.TC;$.FC=$2.FC;,|,Expr,$.TC=$2.FC;$.FC=$2.TC;,|,Expr,Expr,$.TC=$2.TC;$.FC=Merge($1.FC,$2.FC);,|,Expr,Expr,$.FC=$2.FC;$.TC=Merge($1.TC,$2.TC);,|,Expr,Expr,BackPatch($1.TC,NXQ);$.FC=$1.FC;,|,Expr,Expr,BackPatch($1.FC,NXQ);$.TC=$1.TC;,