第七章语义分析和中间代码产生.ppt

国防科技大学计算机系,602,教研室,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七章 语义分析和中间代码产生,静态语义检查,类型检查,控制流检查,一致性检查,相关名字检查,名字的作用域分析,语法分,析器,中间代码,产生器,静态检,查器,中间代码,优化器,国防科技大学计算机系,602,教研室,中间语言(复杂性界于源语言和目标语言之间)的好处：,便于进行与机器无关的代码优化工作,易于移植,使编译程序的结构在逻辑上更为简单明确,源语言,程序,目标语,言程序,中间语,言程序,Compiler,Front End,Compiler,Back End,国防科技大学计算机系,602,教研室,常用的中间语言：,后缀式，逆波兰表示,图表示：,DAG,、抽象语法树,三地址代码,三元式,四元式,间接三元式,7.1 中间语言,国防科技大学计算机系,602,教研室,7.1.1,后缀式,后缀式,表示法：,Lukasiewicz,发明的一种表示表达式的方法，又称,逆波兰,表示法。,一个表达式,E,的后缀形式可以如下定义：,1.如果,E,是一个变量或常量，则,E,的后缀式是,E,自身。,2.如果,E,是,E,1,op E,2,形式的表达式，其中,op,是任何二元操作符，则,E,的后缀式为,E,1,E,2,op，,其中,E,1,和,E,2,分别为,E,1,和,E,2,的后缀式。,3.如果,E,是(,E,1,),形式的表达式，则,E,1,的后缀式就是,E,的后缀式。,国防科技大学计算机系,602,教研室,逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。,后缀式的计算,用一个栈实现。,一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到,k,目运算符就把它作用于栈顶的,k,个项，并用运算结果代替这,k,个项,。,国防科技大学计算机系,602,教研室,7.1.2 图表示法,图表示法,DAG,抽象语法树,国防科技大学计算机系,602,教研室,7.1.2 图表示法,无循环有向图(,Directed Acyclic Graph，,简称,DAG,),对表达式中的每个子表达式，,DAG,中都有一个结点,一个,内部结点,代表一个,操作符,，它的孩子代表操作数,在一个,DAG,中代表公共子表达式的结点具有多个父结点,国防科技大学计算机系,602,教研室,a:=b*(-c)+b*(-c),的图表示法,assign,a,+,*,b,uminus,c,DAG,assign,a,+,*,b,uminus,c,抽象语法树,*,b,uminus,c,国防科技大学计算机系,602,教研室,抽象语法树,对应的代码：,T,1,:=-c,T,2,:=b*T,1,T,3,:=-c,T,4,:=b*T,3,T,5,:=T,2,+T,4,a:=T,5,assign,a,+,*,b,uminus,c,抽象语法树,*,b,uminus,c,国防科技大学计算机系,602,教研室,DAG,对应的代码：,T,1,:=-c,T,2,:=b*T,1,T,5,:=T,2,+T,2,a:=T,5,assign,a,+,*,b,uminus,c,DAG,抽象语法树,对应的代码：,T,1,:=-c,T,2,:=b*T,1,T,3,:=-c,T,4,:=b*T,3,T,5,:=T,2,+T,4,a:=T,5,国防科技大学计算机系,602,教研室,产生赋值语句抽象语法树的属性文法,产 生 式语义规则,Sid:=E,S.nptr:=mknode(assign,mkleaf(id,id.place),E.nptr),EE,1,+E,2,E.nptr:=mknode(+,E,1,.nptr,E,2,.nptr),EE,1,*E,2,E.nptr:=mknode(*,E,1,.nptr,E,2,.nptr),E-E,1,E.nptr:=mknode(uminus,E,1,.nptr),E(E,1,),E.nptr:=E,1,.nptr,Eid,E.nptr:=mkleaf(id,id.place),国防科技大学计算机系,602,教研室,7.1.3 三地址代码,三地址代码,x:=y op z,三地址代码可以看成是抽象语法树或,DAG,的一种线性表示,国防科技大学计算机系,602,教研室,a:=b*(-c)+b*(-c),的图表示法,assign,a,+,*,b,uminus,c,DAG,assign,a,+,*,b,uminus,c,抽象语法树,*,b,uminus,c,国防科技大学计算机系,602,教研室,T,1,:=-c T,1,:=-c,T,2,:=b*T,1,T,2,:=b*T,1,T,3,:=-cT,5,:=T,2,+T,2,T,4,:=b*T,3,a:=T,5,T,5,:=T,2,+T,4,a:=T,5,对于抽象语法树的代码对于,DAG,的代码,国防科技大学计算机系,602,教研室,三地址语句的种类,x:=y op z,x:=op y,x:=y,goto L,if x relop y goto L,或,if a goto L,param x,和,call p,n，,以及返回语句,return y,x:=yi,及,xi:=y,的索引赋值,x:=&y,x:=*y,和*,x:=y,的地址和指针赋值,国防科技大学计算机系,602,教研室,生成三地址代码时，临时变量的名字对应抽象语法树的内部结点,id:=E,对表达式,E,求值并置于变量,T,中值,id.place:=T,国防科技大学计算机系,602,教研室,从赋值语句生成三地址代码的,S-,属性文法,非终结符号,S,有综合属性,S.code，,它代表赋值语句,S,的三地址代码。,非终结符号,E,有如下两个属性：,E.place,表示存放,E,值的名字。,E.code,表示对,E,求值的三地址语句序列。,函数,newtemp,的功能是，每次调用它时，将返回一个不同临时变量名字,如,T,1,T,2,。,国防科技大学计算机系,602,教研室,为赋值语句生成三地址代码的,S-,属性文法定义,产生式语义规则,Sid:=ES.code:=E.code|gen(id.place:=E.place),EE,1,+E,2,E.place:=newtemp;,E.code:=E,1,.code|E,2,.code|,gen(E.place:=E,1,.place+E,2,.place),EE,1,*E,2,E.place:=newtemp;,E.code:=E,1,.code|E,2,.code|,gen(E.place:=E,1,.place*E,2,.place),E-E,1,E.place:=newtemp;,E.code:=E,1,.code|,gen(E.place:=uminus E,1,.place),E(E,1,)E.place:=E,1,.place;,E.code:=E,1,.code,Eid E.place:=id.place;,E.code=,国防科技大学计算机系,602,教研室,三地址语句,四元式,一个带有四个域的记录结构，这四个域分别称为,op,arg1,arg2,及,result,oparg1arg2result,(0)uminuscT,1,(1)*bT,1,T,2,(2)uminuscT,3,(3)*bT,3,T,4,(4)+T,2,T,4,T,5,(5):=T,5,a,国防科技大学计算机系,602,教研室,三地址语句,三元式,通过计算临时变量值的语句的位置来引用这个临时变量,三个域：,op、arg1,和,arg2,oparg1arg2,(0)uminusc,(1)*b(0),(2)uminusc,(3)*b(2),(4)+(1)(3),(5)assigna(4),国防科技大学计算机系,602,教研室,三地址语句,xi:=y,op arg1 arg2,(0)=x i,(1)y,x:=yi,op arg1 arg2,(0)=y i,(1)assign x (0),国防科技大学计算机系,602,教研室,三地址语句,间接三元式,为了便于优化，用 三元式表+间接码表 表示中间代码,间接码表:一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。,优点:方便优化，节省空间,国防科技大学计算机系,602,教研室,例如，语句,X:=(A+B)*C;,Y:=D(A+B),的间接三元式表示如下表所示。,国防科技大学计算机系,602,教研室,7.2 说明语句,国防科技大学计算机系,602,教研室,7.3 赋值语句的翻译,7.3.1 简单算术表达式及赋值语句,国防科技大学计算机系,602,教研室,为赋值语句生成三地址代码的,S-,属性文法定义,产生式语义规则,Sid:=ES.code:=E.code|gen(id.place:=E.place),EE,1,+E,2,E.place:=newtemp;,E.code:=E,1,.code|E,2,.code|,gen(E.place:=E,1,.place+E,2,.place),EE,1,*E,2,E.place:=newtemp;,E.code:=E,1,.code|E,2,.code|,gen(E.place:=E,1,.place*E,2,.place),E-E,1,E.place:=newtemp;,E.code:=E,1,.code|,gen(E.place:=uminus E,1,.place),E(E,1,)E.place:=E,1,.place;,E.code:=E,1,.code,Eid E.place:=id.place;,E.code=,国防科技大学计算机系,602,教研室,产生赋值语句三地址代码的翻译模式,Sid:=E p:=,lookup,(id.name);,if p,nil then,emit(p:=E.place),else error ,EE,1,+E,2,E.place:=newtemp;,emit(E.place:=E,1,.place+E,2,.place),EE,1,*E,2,E.place:=newtemp;,emit(E.place:=E,1,.place*E,2,.place),Sid:=E S.code:=E.code|gen(id.place:=E.place),EE,1,+E,2,E.place:=newtemp;,E.code:=E,1,.code|E,2,.code|gen(E.place:=E,1,.place+E,2,.place),EE,1,*E,2,E.place:=newtemp;,E.code:=E,1,.code|E,2,.code|gen(E.place:=E,1,.place*E,2,.place),国防科技大学计算机系,602,教研室,产生赋值语句三地址代码的翻译模式,E-E,1,E.place:=newtemp;,emit(E.place:=uminusE,1,.place),E(E,1,)E.place:=E,1,.place,Eid p:=lookup(id.name);,if p,nil then,E.place:=p,else error,E-E,1,E.place:=newtemp;,E.code:=E,1,.code|gen(E.place:=uminus E,1,.place),E(E,1,)E.place:=E,1,.place;,E.code:=E,1,.code,Eid E.place:=id.place;,E.code=,国防科技大学计算机系,602,教研室,7.3.2 数组元素的引用,数组元素地址的计算：,国防科技大学计算机系,602,教研室,设,A,为,n,维数组，每个元素宽度为,w，low,i,为第,i,维,的下界，,n,i,是为第,i,维,可取值的个数,base,为,A,的第一个元素相对地址,元素,Ai,1,i,2,i,k,相对地址公式,(,i,1,n,2,+i,2,)n,3,+i,3,)n,k,+i,k,)w+,base-(low,1,n,2,+low,2,)n,3,+low,3,)n,k,+low,k,)w,C=base-(low,1,n,2,+low,2,)n,3,+low,3,)n,k,+low,k,)w,国防科技大学计算机系,602,教研室,id,出现的地方也允许下面产生式中的,L,出现,L id Elist|id,ElistElist,E|E,为了便于处理，文法改写为,L,Elist,|id,ElistElist,E|,id E,国防科技大学计算机系,602,教研室,引入下列语义变量或语义过程:,Elist.ndim：,下标个数计数器,Elist.place：,表示临时变量，用来临时存放已形成的,Elist,中的下标表达式计算出来的值,limit(array，j)：,函数过程，它给出数组,array,的第,j,维的长度,国防科技大学计算机系,602,教研室,每个代表变量的非终结符,L,有两项语义值,L.place：,若,L,为,简单变量,i,指变量,i,的符号表入口,若,L,为,下标变量,，指存放,CONSPART,的 临时变量的整数码,L.offset：,若,L,为,简单变量,，,null，,若,L,为,下标变量,，指存放,VARPART,的临时变量的整数码,国防科技大学计算机系,602,教研室,(1),SL:=E,(2)EE+E,(3)E(E),(4)EL,(5)LElist,(6)Lid,(7)Elist Elist,E,(8)Elistid E,国防科技大学计算机系,602,教研室,(1)SL:=E,if L.offset=null then/*L,是简单变量*/,emit(L.place:=E.place),else emit(,L.place L.offset ,:=E.place),(2)EE,1,+E,2,E.place:=newtemp;,emit(E.place:=E,1,.place+E,2,.place),国防科技大学计算机系,602,教研室,(3),E(E,1,)E.place:=E,1,.place,(4)EL,if L.offset=null then,E.place:=L.place,else begin,E.place:=newtemp;,emit(E.place:=,L.place L.offset,),end,国防科技大学计算机系,602,教研室,A,i,1,i,2,i,k,(,i,1,n,2,+i,2,)n,3,+i,3,)n,k,+i,k,)w+base-(low,1,n,2,+low,2,)n,3,+low,3,)n,k,+low,k,)w,(8),Elistid E,Elist.place:=,E.place,;,Elist.ndim:=1;,Elist.array:=id.place ,国防科技大学计算机系,602,教研室,A i,1,i,2,i,k,(,(,i,1,n,2,+i,2,)n,3,+i,3,),n,k,+,i,k,)w+base-(low,1,n,2,+low,2,)n,3,+low,3,)n,k,+low,k,)w,(7),Elist Elist,1,E,t:=newtemp;,m:=Elist,1,.ndim+1;,emit(t:=,Elist,1,.place,*,limit(Elist,1,.array,m),);,emit(t:=t +,E.place,);,Elist.array:=Elist,1,.array;,Elist.place:=t;,Elist.ndim:=m,国防科技大学计算机系,602,教研室,Ai,1,i,2,i,k,(,i,1,n,2,+i,2,)n,3,+i,3,)n,k,+i,k,),w,+,base,-,(low,1,n,2,+low,2,)n,3,+low,3,)n,k,+low,k,)w,(5),LElist,L.place:=newtemp;,emit(L.place:=,Elist.array,C,);,L.offset:=newtemp;,emit(L.offset:=,w*,Elist.place,),(6),Lid L.place:=id.place;L.offset:=null,国防科技大学计算机系,602,教研室,类型转换,用,E.type,表示非终结符,E,的类型属性,对应产生式,E,E,1,op E,2,的语义动作中关于,E.type,的语义规则可定义为：,if E,1,.type=integer andE,2,.type=integer,E.type:=integer,else E.type:=real ,算符区分为整型算符,int op,和实型算符,real op，,国防科技大学计算机系,602,教研室,x:=yi*j,其中,x、y,为实型；,i、j,为整型。这个赋值句产生的三地址代码为：,T,1,:=i,int*,j,T,3,:=,inttoreal,T,1,T,2,:=y,real+,T,3,x:=T,2,国防科技大学计算机系,602,教研室,关于产生式,EE,1,E,2,的语义动作,E.place:=newtemp;,if E,1,.type=integer and E,2,.type=integer then begin,emit(E.place:=E,1,.place int+E,2,.place);,E.type:=integer,end,else if E,1,.type=real and E,2,.type=real then begin,emit(E.place:=E,1,.place real+E,2,.place);,E.type:=real,end,国防科技大学计算机系,602,教研室,else if E,1,.type=integer and E,2,.type=real then begin,u:=newtemp;,emit(u:=inttoreal E,1,.place);,emit(E.place:=u real+E,2,.palce);,E.type:=real,end,else if E,1,.type=real and E,1,.type=integer then begin,u:=newtemp;,emit(u :=inttoreal E,2,.place);,emit(E.place:=E,1,.place real+u);,E.type:=real,end,else E.type:=type_error,国防科技大学计算机系,602,教研室,7.3.3 记录中域的引用,符号表表项之中保存记录中的域的类型和相对地址信息,国防科技大学计算机系,602,教研室,7.4 布尔表达式的翻译,布尔表达式的两个基本作用:,用于逻辑演算,计算逻辑值;,用于控制语句的条件式.,产生布尔表达式的文法:,EE,or,E|E,and,E|,E|(E)|i rop i|i,国防科技大学计算机系,602,教研室,计算布尔表达式通常采用两种方法:,1.如同计算算术表达式一样,一步步算,1,or,(,n,ot,0,and,0),or,0,=1,or,(1,and,0),or,0,=1,or,0,or,0,=1,or,0,=1,2.采用某种优化措施,把,A,or,B,解释成,if A then true else B,把,A,and,B,解释成,if A then B else false,把,A,解释成,if A then false else true,国防科技大学计算机系,602,教研室,两种不同的翻译方法:,第一种翻译法：,A,or,B,and C=D,翻译成,(1)(=,C,D,T,1,),(2)(and,B,T,1,T,2,),(3)(or,A,T,2,T,3,),第二种翻译法适合于作为条件表达式的布尔表达式使用.,国防科技大学计算机系,602,教研室,7.4.1 数值表示法,a or b and not c,翻译成,T,1,:=not c,T,2,:=b and T,1,T,3,:=a or T,1,ab,的关系表达式可等价地写成,if ab then 1 else 0，,翻译成,100:,if ab goto 103,101:T:=0,102:goto 104,103:T:=1,104:,国防科技大学计算机系,602,教研室,关于布尔表达式的数值表示法的翻译模式,过程,emit,将三地址代码送到输出文件中,nextstat,给出输出序列中下一条三地址语句的地址索引,每产生一条三地址语句后，过程,emit,便把,nextstat,加1,国防科技大学计算机系,602,教研室,关于布尔表达式的数值表示法的翻译模式,EE,1,or E,2,E.place:=newtemp;,emit(E.place:=E,1,.place or E,2,.place),EE,1,and E,2,E.place:=newtemp;,emit(E.place:=E,1,.place and E,2,.place),Enot E,1,E.place:=newtemp;,emit(E.place:=not E,1,.place),E(E,1,)E.place:=E,1,.place,国防科技大学计算机系,602,教研室,关于布尔表达式的数值表示法的翻译模式,E,id,1,relop id,2,E.place:=newtemp;,emit(if id,1,.place relop.op id,2,.place,goto nextstat+3);,emit(E.place:=0);,emit(goto nextstat+2);,emit(E.place:=1),Eid E.place:=id.place,ab,翻译成,100:,if ab goto 103,101:T:=0,102:goto 104,103:T:=1,104:,国防科技大学计算机系,602,教研室,布尔表达式,ab,or,cd,and,ef,的翻译结果,100:,if ab goto 103,101:T,1,:=0,102:goto 104,103:T,1,:=1,104:if cd goto 107,105:T,2,:=0,106:goto 108,107:T,2,:=1,108:if ec,or,b,c goto L2 “,真”出口,goto L1,L1:if bd goto L2 “,真”出口,goto L3 “,假”出口,L2:(,关于,S1,的三地址代码序列),goto Lnext,L3:(,关于,S2,的三地址代码序列),Lnext:,国防科技大学计算机系,602,教研室,每次调用函数,newlabel,后都返回一个新的符号标号,对于一个布尔表达式,E，,引用两个标号,E.true,是,E,为真时控制流转向的标号,E.false,是,E,为假时控制流转向的标号,国防科技大学计算机系,602,教研室,产生布尔表达式三地址代码的语义规则,产生式语义规则,EE,1,or E,2,E,1,.true:=E.true;,E,1,.false:=newlabel;,E,2,.true:=E.true;,E,2,.false:=E.false;,E.code:=E,1,.code|,gen(E,1,.false:)|E,2,.code,E,1,.,code,To E.true,To E,1,.false,E,2,.,code,To E.true,To E.false,国防科技大学计算机系,602,教研室,产生布尔表达式三地址代码的语义规则,产生式语义规则,EE,1,and E,2,E,1,.true:=newlabel;,E,1,.false:=E.false;,E,2,.true:=E.true;,E,2,.false:=E.fasle;,E.code:=E,1,.code|,gen(E,1,.true:)|E,2,.code,E,1,.,code,To E.,false,To E,1,.,true,E,2,.,code,To E.true,To E.false,国防科技大学计算机系,602,教研室,产生布尔表达式三地址代码的语义规则,产生式语义规则,Enot E,1,E,1,.true:=E.false;,E,1,.false:=E.true;,E.code:=E,1,.code,E(E,1,)E,1,.true:=E.true;,E,1,.false:=E.false;,E.code:=E,1,.code,国防科技大学计算机系,602,教研室,产生布尔表达式三地址代码的语义规则,产生式语义规则,Eid,1,relop id,2,E.code:=gen(if id,1,.place,relop.op id,2,.place goto E.true)|,gen(goto E.false),Etrue E.code:=gen(goto E.true),Efalse E.code:=gen(goto E.false),国防科技大学计算机系,602,教研室,考虑如下表达式：,ab or cd and ef,假定整个表达式的真假出口已分别置为,Ltrue,和,Lfalse，,则按定义将生成如下的代码：,if ab goto Ltrue,goto L,1,L,1,:if cd goto L,2,goto Lfalse,L,2,:if ef goto Ltrue,goto Lfalse,国防科技大学计算机系,602,教研室,布尔表达式的翻译,两遍扫描,为给定的输入串构造一棵语法树；,对语法树进行深度优先遍历，进行语义规则中规定的翻译。,一遍扫描,国防科技大学计算机系,602,教研室,一遍扫描实现布尔表达式的翻译,采用四元式形式,把四元式存入一个数组中，数组下标就代表四元式的标号,约定,四元式(,jnz,a,-,p),表示,if a goto p,四元式(,jrop,x,y,p),表示,if x rop y goto p,四元式(,j,-,-,p),表示,goto p,国防科技大学计算机系,602,教研室,有时,四元式转移地址无法立即知道,我们只好把这个未完成的四元式地址作为,E,的语义值保存,待机回填。,国防科技大学计算机系,602,教研室,为非终结符,E,赋予两个综合属性,E.truelist,和,E.falselist。,它们分别记录布尔表达式,E,所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表,例如:假定,E,的四元式中需要回填真出口的,p，q，r,三个四元式，则,E.truelist,为下列链:,(,p)(x，x，x，0),(,q)(x，x，x，p),(r)(x，x，x，q),链尾,E.,truelist,=r,国防科技大学计算机系,602,教研室,为了处理,E.truelist,和,E.falselist，,引入下列语义变量和过程:,变量,nextquad，,它指向下一条将要产生但尚未形成的四元式的地址(标号)。,nextquad,的初值为1，每当执行一次,emit,之后，,nextquad,将自动增1。,函数,makelist(i)，,它将创建一个仅含,i,的新链表，其中,i,是四元式数组的一个下标(标号)；函数返回指向这个链的指针。,函数,merge(p,1,p,2,)，,把以,p,1,和,p,2,为链首的两条链合并为一，作为函数值，回送合并后的链首。,过程,backpatch(p,t)，,其功能是完成“回填”，把,p,所链接的每个四元式的第四区段都填为,t。,国防科技大学计算机系,602,教研室,布尔表达式的文法,(1),EE,1,or M E,2,(2)|E,1,and M E,2,(3)|not E,1,(4)|(E,1,),(5)|id,1,relop id,2,(6)|id,(7)M,国防科技大学计算机系,602,教研室,布尔表达式的翻译模式,(7)M,M.quad:=nextquad,国防科技大学计算机系,602,教研室,布尔表达式的翻译模式,(1),EE,1,or M E,2,backpatch(E,1,.falselist,M.quad);,E.truelist:=merge(E,1,.truelist,E,2,.truelist);,E.falselist:=E,2,.falselist,(2)EE,1,and M E,2,backpatch(E,1,.truelist,M.quad);,E.truelist:=E,2,.truelist;,E.falselist:=merge(E,1,.falselist,E,2,.falselist),E,1,.,code,To E.true,To E,1,.false,E,2,.,code,To E.true,To E.false,E,1,.,code,To E.,false,To E,1,.,true,E,2,.,code,To E.true,To E.false,国防科技大学计算机系,602,教研室,布尔表达式的翻译模式,(3)Enot E,1,E.truelist:=E,1,.falselist;,E.falselist:=E,1,.truelist,(4)E(E,1,),E.truelist:=E,1,.truelist;,E.falselist:=E,1,.falselist,国防科技大学计算机系,602,教研室,布尔表达式的翻译模式,(5)Eid,1,relop id,2,E.truelist:=makelist(nextquad);,E.falselist:=makelist(nextquad+1);,emit(j relop.op,id,1,.place,id,2,.place,0);,emit(j,0),(6)Eid,E.truelist:=makelist(nextquad);,E.falselist:=makelist(nextquad+1);,emit(jnz,id,.place,0)；,emit(j,-,-,0),国防科技大学计算机系,602,教研室,布尔表达式的翻译模式,作为整个布尔表达式的真假出口(转移目标)仍待回填.,国防科技大学计算机系,602,教研室,ab or cd and ef,100(,j,a,b,0),101(j,-,-,102),102(j,c,d,104),103(j,-,-,0),104(j,e,f,100,),truelist,105(j,-,-,103,),falselist,国防科技大学计算机系,602,教研室,计算布尔表达式通常采用两种方法:,1.如同计算算术表达式一样,一步步算,1,or,(,n,ot,0,and,0),or,0,=1,or,(1,and,0),or,0,=1,or,0,or,0,=1,or,0,=1,2.采用某种优化措施,把,A,or,B,解释成,if A then true else B,把,A,and,B,解释成,if A then B else false,把,A,解释成,if A then false else true,回顾：布尔表达式的翻译,国防科技大学计算机系,602,教研室,关于布尔表达式的数值表示法的翻译模式,E,id,1,relop id,2,E.place:=newtemp;,emit(if id,1,.place relop.op id,2,.place goto nextstat+3);,emit(E.place:=0);,emit(goto nextstat+2);,emit(E.place:=1),Eid,E.place:=id.place,EE,1,or E,2,E.place:=newtemp;,emit(E.place:=E,1,.place or E,2,.place),EE,1,and E,2,E.place:=newtemp;,emit(E.place:=E,1,.place and E,2,.place),国防科技大学计算机系,602,教研室,回顾：布尔表达式的翻译,作为条件控制的布尔式翻译,一遍扫描实现布尔表达式的翻译,国防科技大学计算机系,602,教研室,7.4.2 作为条件控制的布尔式翻译,条件语句,if E then S,1,else S,2,赋予,E,两种出口:一真一假,E,.,code,S,1,.,code,S,2,.,code,To E.true,To E.false,goto S.next,S.next,E.true:,E.false:,国防科技大学计算机系,602,教研室,产生布尔表达式三地址代码的语义规则,产生式语义规则,EE,1,or E,2,E,1,.true:=E.true;,E,1,.false:=newlabel;,E,2,.true:=E.true;,E,2,.false:=E.false;,E.code:=E,1,.code|,gen(E,1,.false:)|E,2,.code,E,1,.,code,To E.true,To E,1,.false,E,2,.,code,To E.true,To E.false,国防科技大学计算机系,602,教研室,产生布尔表达式三地址代码的语义规则,产生式语义规则,EE,1,and E,2,E,1,.true:=newlabel;,E,1,.false:=E.false;,E,2,.true:=E.true;,E,2,.false:=E.fasle;,E.code:=E,1,.code|,gen(E,1,.true:)|E,2,.code,E,1,.,code,To E.,false,To E,1,.,true,E,2,.,code,To E.true,To E.false,国防科技大学计算机系,602,教研室,产生布尔表达式三地址代码的语义规则,产生式语义规则,Enot E,1,E,1,.true:=E.false;,E,1,.false:=E.true;,E.code:=E,1,.code,E(E,1,)E,1,.true:=E.true;,E,1,.false:=E.false;,E.code:=E,1,.code,国防科技大学计算机系,602,教研室,产生布尔表达式三地址代码的语义规则,产生式语义规则,Eid,1,relop id,2,E.code:=gen(if id,1,.place,relop.op id,2,.place goto E.true)|,gen(goto E.false),Etrue E.code:=gen(goto E.true),Efalse E.code:=gen(goto E.false),国防科技大学计算机系,602,教研室,回顾：布尔表达式的翻译,作为条件控制的布尔式翻译,一遍扫描实现布尔表达式的翻译,国防科技大学计算机系,602,教研室,布尔表达式的文法,(1),EE,1,or M E,2,(2)|E,1,and M E,2,(3)|not E,1,(4)|(E,1,),(5)|id,1,relop id,2,(6)|id,(7)M,国防科技大学计算机系,602,教研室,布尔表达式的翻译模式,(1),EE,1,or M E,2,backpatch(E,1,.falselist,M.quad);,E.truelist:=merge(E,1,.truelist,E,2,.truelist);,E.falselist:=E,2,.falselist,(2)EE,1,and M E,2,backpatch(E,1,.truelist,M.quad);,E.truelist:=E,2,.truelist;,E.falselist:=merge(E,1,.falselist,E,2,.falselist),(3)En