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

1、5.5 自下而上语法制导翻译,1 特点 当栈顶形成句柄执行归约时，调用相应的语义动作; 语法分析栈与语义分析栈同步操作。,5.5 自下而上语法制导翻译,2 三种基本句型的翻译 简单算术表达式和赋值语句 布尔表达式 例：A C B 控制语句 if-then, if-then-else, while-do,5.5.1 简单算术表达式和赋值语句的翻译,1 赋值语句的文法 Ai=E EE+E EE*E EE E(E) Ei,仅含简单常变量的表达式的赋值语句。,5.5.1 简单算术表达式和赋值语句的翻译,2 需要的语义过程 newtemp()函数： 每次调用申请一块空间，产生一个新的临时变量名字。 em

2、it(T=arg1 op agr2): 产生一个四元式，并填入四元式表中。 lookup(): 查变量是否出现在符号表中，在则返回其指针，否则返回NULL.,5.5.1 简单算术表达式和赋值语句的翻译,3 需要的语义变量 E.place： 存放E值的变量名在符号表中的入口地址。,5.5.1 简单算术表达式和赋值语句的翻译,4 语义子程序 (1)Ai=E (2)EE(1) (3)EE(1) +E(2),p=lookup(); if(p=NULL) error(); else emit(p = E.place);,E.place=newtemp(); emit(

3、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(); if(p!=NULL) E.place=p; else error();,例 对A=B*(C+D)$ 进行语法制导

4、翻译，写出四元式。,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)布尔运算符的运算顺

5、序为： ，。 且，服从左结合。 (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=

6、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

7、 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

8、控制语句中布尔式的翻译 将每一个作为条件控制的布尔式都翻译成两个四元式： (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 af goto E.true (6) goto E.false,例2 将控制语句中的布尔表达式 a or b and c 翻译成四元式。 (1) if a goto E.t

9、rue (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，当运行到一些语句后，根据程序逻辑， 知道具体的转移地址后，进行回填。,拉链：不止一条四元式跳转到同一个语句，将这些转移 方向相同的四元式拉成一条链，一旦发现具体转移地址 就沿着链回填。,回填： 例将控制语句中的布尔式

10、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

11、(20) ,(50),(50),(50),回填和拉链 求ABD的四元式。 (1) if A goto 0 (E.true) (2) goto (3) (回填) (3) if BD goto (1) (拉链) (4) goto 0 (E.false),5.5.3 控制语句的翻译,控制语句的三种基本句型 Sif E then S1 | if E then S1 else S2 | while E do S1,1 Sif E then S1的翻译方法 Sif E then S1 E.true=newlable(); E.false=S.next; S1.next=S.next; S.code=E.c

12、ode| 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 Sif 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.c

13、ode=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 Swhile 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 AB6) then X=X-1 else Y=X+1 翻译成四元式。,(100) if A goto (104) (101) goto