第五章_2 语法制导翻译和中间代码生成

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,5.5,自下而上语法制导翻译,1,特点,当栈顶形成句柄执行,归约,时，调用相应的语义动作,;,语法分析栈与语义分析栈同步操作。,5.5,自下而上语法制导翻译,2,三种基本句型的翻译,简单算术表达式和赋值语句,布尔表达式,例：,A C B,控制语句,if-then,if-then-else,while-do,5.5.1,简单算术表达式和赋值语句的翻译,1,赋值语句的文法,Ai=E,EE+E,E,E*E,E,E,E,(E),E,i,仅含简单常变量的表达式的赋值语句。,5.5.1,简单算术表达式和赋值语句的翻译,2,需要的语义过程,newtemp(),函数：,每次调用申请一块空间，产生一个新的临时变量名字。,emit(T=arg1 op agr2):,产生一个四元式，并填入四元式表中。,lookup(i.name):,查变量,i.name,是否出现在符号表中，在则返回其指针，否则返回,NULL.,5.5.1,简单算术表达式和赋值语句的翻译,3,需要的语义变量,E.place,：,存放,E,值的变量名在符号表中的入口地址。,5.5.1,简单算术表达式和赋值语句的翻译,4,语义子程序,(1)Ai=E,(2)E,E,(1),(3)EE,(1),+E,(2),p=lookup(i.name);,if(p=NULL)error();,else emit(p=E.place);,E.place=newtemp();,emit(E.place=,E,(1),.place);,E.place=newtemp();,emit(E.place=E,(1),.place+E,(2),.place);,5.5.1,简单算术表达式和赋值语句的翻译,4,语义子程序,(4)E E,(1),*,E,(2),(5)E(E,(1),),(6)Ei,E.place=newtemp();,emit(E.place=E,(1),.place*E,(2),.place);,E.place=E,(1),.place;,p=lookup(i.name);,if(p!=NULL)E.place=p;,else error();,例 对,A=,B*(C+D)$,进行语法制导翻译，写出四元式。,E,B,E,(1)T1=,B,C,D,E,E,E,(2)T2=C+D,*,E,(3)T3=T1*T2,=,A,S,(4)A=T3,E,(,),注：,简单算术表达式的计值顺序,和四元式出现的顺序相同,5.5.2,布尔表达式的翻译,1,布尔表达式的组成,由布尔算符作用于布尔常、变量 或,关系表达式 形成。,布尔算符,关系表达式,，,E,(1),rop E,(2),E,：算术表达式,rop:,=,5.5.2,布尔表达式的翻译,2,布尔表达式的文法,EEE,EEE,EE,E(E),Ei rop i,Ei,i,是布尔变量或常量，,或是算术表达式,限制：,(1),布尔运算符的运算顺序为：,，。,且，服从左结合。,(2),关系运算优先级别高于布尔运算。,5.5.2,布尔表达式的翻译,3,布尔表达式的作用,用于,逻辑赋值语句,中布尔表达式的演算,用作,控制语句,中的条件表达式,if,E(,条件,),while,E(,条件,),5.5.2,布尔表达式的翻译,4,用于逻辑演算的翻译方法,(1)EE,(1),E,(2),(2)EE,(1),E,(2),(3)EE,E.place=newtemp();,emit(E.place=E,(1),.place,E,(2),.place);,E.place=newtemp();,emit(E.place=E,(1),.place,E,(2),.place);,E.place=newtemp();,emit(E.place=,E,(1),.place);,5.5.2,布尔表达式的翻译,4,用于逻辑演算的翻译方法,(4)E(E,(1),),(5)Ei,(1),rop i,(2),(6)Ei,E.place=E,(1),.place;,E.place=newtemp();,emit(if i,(1),.place rop i,(2),.place goto nextq+3);,emit(E.place=0);,emit(goto nextq+2);,emit(E.place=1);,E.place=i.place;,例 将布尔表达式,A=BCD,翻译成四元式。,A,=,B,E,(1)if A=B goto(4),(2)T1=0,(3)goto(5),(4)T1=1,(5)T2=CD,(6)T3=T1T2,C,D,E,E,E,E,5.5.2,布尔表达式的翻译,5,控制语句中布尔式的翻译,布尔表达式出现在控制语句中的情况：,if,E,then S,(1),if,E,then S,(1),else S,(2),while,E,do S,(1),E,的代码,S,(1),的代码,真,假,E,的代码,S,(1),的代码,S,(2),的代码,真,假,E,的代码,S,(1),的代码,Begin:,真,假,语句中,E,为真或假时的控制流向的转移，,称为布尔式,E,的真出口或假出口,。,5.5.2,布尔表达式的翻译,5,控制语句中布尔式的翻译,将,每一个,作为条件控制的布尔式都翻译,成两个四元式：,(1)if E,(1),rop E,(2),goto E.true,(2)goto E.false,或,(1)if E goto E.true,(2)goto E.false,其中：,rop,是关系运算符,;,E.ture,表示布尔式,E,的真出口,;,E.false,表示布尔式,E,的假出口。,例,1,将控制语句中的布尔表达式,af,翻译成四元式序列。,(1)if ab goto E.true,(2)goto(3),(3)if cf goto E.true,(6)goto E.false,例,2,将控制语句中的布尔表达式,a or b and c,翻译成四元式。,(1)if a goto E.true,(2)goto(3),(3)if b goto(5),(4)goto E.false,(5)if c goto E.true,(6)goto E.false,问题：,跳转语句如何得到？,E.true,和,E.false,如何得到？,5.5.2,布尔表达式的翻译,5,控制语句中布尔式的翻译,回填和拉链技术,回填,：有些四元式的转移地址在产生四元式并不知道，,初始为,0,，当运行到一些语句后，根据程序逻辑，,知道具体的转移地址后，进行回填。,拉链,：不止一条四元式跳转到同一个语句，将这些转移,方向相同的四元式拉成一条链，一旦发现具体转移地址,就沿着链回填。,回填：,例将控制语句中的布尔式,ab,c,翻译成四元式。,(1)if ab goto 0(E.true),(2)goto 0(,回填,(3),(3)if c goto 0(E.true,与,(1),拉链，,0,表链尾,),(4)goto 0(E.false),拉链：,例，把需回填,E.true,的四元式拉成一链。,(10)if goto 0(E.true),.,(20)if goto 0(E.true),(30)if goto 0(E.true),地址,30,为链头，,0,表链尾标志。,回填时从链头填起，直至链尾结束。,拉链后为：,(10)if goto 0,(20)if goto(10),(30)if goto(20),(50),(50),(50),回填和拉链,求,A,BD,的四元式。,(1)if A goto 0(E.true),(2)goto(3)(,回填,),(3)if BD goto(1)(,拉链,),(4)goto 0(E.false),5.5.3,控制语句的翻译,控制语句的三种基本句型,S,if E then S1|,if E then S1 else S2|,while E do S1,1 S,if E then S1,的翻译方法,Sif E then S1 E.true=newlable();,E.false=S.next;,S1.next=S.next;,S.code=E.code|,gen(E.true:)S1.code;,Newlable(),指产生一个新的符号标号,;,S.next,指紧跟在,S,后的第一条四元式序号。,gen(),与,emit(),功能同。,例,if cd then x=y+z,翻译成四元式。,(1)if cd goto(3),(2)goto(5),(3)T1=y+z,(4)x=T1,(5),2 S,if E then S1 else S2,的翻译方法,Sif E then S1 else S2 E.true=newlable();,E.false=newlable();,S1.next=S.next;,S2.next=S.next;,S.code=E.code|,gen(E.true:)S1.code|,gen(goto S.next)|,gen(E.false:)S2.code;,例,if cd then x=y+z,else x=y-z,翻译成四元式。,(1)if cd goto(3),(2)goto(6),(3)T1=y+z,(4)x=T1,(5)goto(8),(6)T2=y-z,(7)x=T2,(8),3 S,while E do S1,的翻译方法,Swhile E do S1 S.begin=newlable();,E.true=newlable();,E.flase=S.next;,S1.next=S.begin;,S.code=gen(S.begin:)E.code|,gen(E.true:)S1.code|,gen(goto S.begin);,例,while ab do x=y+z,翻译成四元式。,(1)if ab goto(3),(2)goto(6),(3)T1=y+z,(4)x=T1,(5)goto(1),(6),多重嵌套的例子。,将,while A,B6)then X=X-1,else Y=X+1,翻译成四元式。,(100)if A goto(104),(101)goto(102),(102)if B6 goto(106),(105)goto(109),(106)T1=X-1,(107)X=T1,(108)goto(100),(109)T2=X+1,(110)Y=T2,(111)goto(100),(112),本章小结,1,根据已知条件写出逆波兰式、四元式。,2,掌握三种基本句型的语法制导翻译方法。,补充课后题：,将,while(AD)then X=Y+Z,翻译成四元式。,