《哈工大编译原理6-2.1》由会员分享，可在线阅读，更多相关《哈工大编译原理6-2.1（62页珍藏版）》请在金锄头文库上搜索。
1、1,本节考虑由如下文法生成的布尔表达式：,布尔表达式的作用：1. 用作计算逻辑值2. 用作控制流语句如if-then，if-then-else和while-do等之中的条件表达式,布尔表达式: 用布尔运算符号(and,or,not)作用到布尔变量或关系表达式上而组成,7.2.3 布尔表达式,EE or E|E and E| not E|(E）|id relop id |true|false,2,优先级：not、and、or And、or左结合not右结合,1、表示一个布尔表达式的值,一、 翻译布尔表达式的方法,例 1 or (not 0 and 0) or 0,方法一：用数值表示真和假，从而对
2、布尔表达式的求值可以象对算术表达式的求值那样一步一步地来计算,=1 or (1 and 0)or 0,=1 or 0 or 0,=1 or 0,=1,3,方法二用于翻译控制流语句中的布尔表达式尤其方便。,方法二：另一种方法是根据布尔表达式的特点，采用了某种优化措施。,例：A or B 如果A为真，那么B的值就不必计算，此时A or B 的值已定，为真。,同理，A and B 如果A为假，那么B的值就不必计算，此时A and B 的值已定，为假。,4,布尔表达式：a or b and not c 翻译成三地址代码序列：100 ： t1:=not c 101 ： t2:=b and t1102 ：
3、 t3:=a or t1,用1表示真，0表示假来实现布尔表达式的翻译,二、 数值表示法,5,关系表达式：ab,100 ： if ab goto l03 101 ： t：=0 102 ： goto l04。 103 : t:=1 104：,等价于if ab then 1 else 0,翻译成三地址代码序列：,四元式序列：,100:(j,a,b,103) 101: (= ,0, ,t) 102:(j , , ,104) 103 : (= ,1, ,t) 104:,6,emit用于将一个三地址语句输送到文件中,Nextquat是一个计数器，,每执行一次emit后，nextquat自动加1,三、布尔表
4、达式的数值表示法的翻译模式,也就是即将生成的三地址语句序号。,100:(j,a,b,103) 101: (= ,0, ,t) 102: (j , , ,104) 103 : (= ,1, ,t) 104,nextquat,指向下一个三地址语句在输出序列中的索引序号,7,EE1 or E2 E.place:=newtemp; emit(E.place:=E1.placeor E2.place),Enot E1 E.place:=newtemp; emit(E.place:= not E1.place),EE1 and E2 E.place:=newtemp; emit(E.place:=E1.p
5、laceand E2.place),8,Eture E.place:=newtemp; emit(E.place:= 1),Efalse E.place:=newtemp; emit(E.place:= 0),Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop.op id2.placegoto nextstart+3); emit(E.place:= 0); emit(gotonextstat+2); emit(E.place:= 1),9,例：布尔表达式 ab and cd and ef对应的语法树,a b and c d and
6、 e f,E,E,E,E,E,语义动作执行顺序： ,10,例：布尔表达式 ab and cd and ef可以生成如下的三地址码,100:if ab goto 103 101:t1=0 102:goto 104 103:t1=1,104:if cd goto 107 105:t2=0 106:goto 104 107:t2=1,E.place=newtemp;emit(if id1.place relop.opid2.place goto nextstart+3) emit(E.place = 0) emit(goto nextstart+2) emit(E.place = 1),E.plac
7、e=newtemp;emit(E.place =E1.place andE2.place),108:t3=t1 and t2,E.place=newtemp;emit(if id1.place relop.opid2.place goto nextstart+3) emit(E.place = 0) emit(goto nextstart+2) emit(E.place = 1),109:if ef goto 112 110:t4=0 111:goto 113 112:t4=1,E.place=newtemp;emit(E.place =E1.place andE2.place),113:t5
8、=t3 and t4,11,四、 控制流语句中的布尔表达式的翻译,对于出现在条件语句 if E then s1 else s2中的布尔表达式E，其作用就是控制对S1和S2的选择,因此，作为条件的布尔表达式，把它设计成两个出口：E.true 和 E.false,考虑E的上下文，对于IF语句，E.true 指向S1， E.false指向S2；,对于while语句E.true 指向循环的开始， E.false指向while 的下一语句,12,三地址表示：E.true: if ab goto E.true （真出口）E.false: goto E.false （假出口）,1、基本思想: 假定E 形如a
9、d,则将生成如下的E的代码：,四元式表示： E.true: （j, a , b , E.true) （真出口）E.false: (j , , , E.false ) （假出口）,13,布尔表达式： E and E E or E、 not E,14,2、优化代码结构：,E E1 and E2,E1的代码,E2的代码,E1.true,E2.true,E.true,E.false,E2.false,E1.false,E E1 or E2,E1的代码,E2的代码,E1.false,E2.false,E.false,E1.true,E2.true,E.true,15,产生式,语义规则,EE1 or E2
10、,E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false E.code:=E1.code| gen(E1.false:)|E2.code,3、语法制导定义,16,产生式,语义规则,EE1 and E2,E1.true:= newlabel; E1.false:= E.false; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code gen(E1.true:) E2.code,Enot E1,E1.true:= E.false; E1.false:= E.t
11、rue; E.code:=E1.code,17,产生式,语义规则,Eid1 relop id2,E.code:=gen(if id1.place relop.op id2.placegoto E.true)| gen(goto E.false),Etrue,E.code:=gen(goto E.true) ,Efalse,E.code:=gen(goto E.false) ,E的true和false属性都是继承属性,E(E1),E1.true:= E.true; E1.false:= E.false; E.code:=E1.code,18,If ef goto ltrue Goto Lfals
12、e,If c d goto L2 Goto Lfalse,If a b goto L1 Goto Lfalse,L2,L1,考虑如下表达式 ab and cd and eb的四元式真假出口可以表示为：（J, a , b , p)(j , , , q),若将其作为条件表达式，例如：,if ab then s1 else s2,（J,a,b ,p) p为s1的第一个代码序号(j , , , q) q为s2的第一个代码序号,21,前面例子产生的三地址码的四元式形式if ab goto L1goto Lfalse L1:if cd goto l2goto Lfalse L2:if ef goto Lt
13、ruegoto Lfalse,(J,a,b,102)(j, , ,Lfalse)(J,c,d,104)(j, , ,Lfalse)(J,e,f,L.true)(j, , ,Lfalse),If ab and cd and ef then s1 else s2,22,5、回填,两遍扫描：,一遍扫描：语法制导翻译技术是属于一遍扫描分析。,从给定的输入构造出一棵语法树；,对语法树按深度优先遍历，来进行语义分析。,存在的问题：if ab then x=0 else x=1,23,对于每一条这样的指令作适当的记录，,再将它“回填”到相应的指令中。,一旦目标标号被确定下来，,先产生暂时没有填写目标标号的转移指令。,解决方法：,if ab then x=0 else x=1,（j, a , b , )(J , , , ),24,要解决的问题：在一遍扫描中，生成跳转语句时,不知道控制要转向的语句标号,解决方法：生成跳转语句时，将其E.true和E.false链成一个链表，记录在E.truelist 和E.falselist中,等到转移目标确定以后，再将转移出口填入E.truelist和E.falselist中,回填,25,(J,a,b,102)(j, , ,Lfalse)(J,c,d,104)(j, , ,Lfalse)(J,e,f,L.true)(j, , ,Lfalse),
