语法制导翻译和中间代码生成.ppt

《语法制导翻译和中间代码生成.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译和中间代码生成.ppt（36页珍藏版）》请在金锄头文库上搜索。

1、第七讲第七讲 语法制导翻译和中间代码语法制导翻译和中间代码n n7.1属性文法n n7.2语法制导翻译概论n n7.3中间代码n n7.4一些语句的翻译属性文法属性文法属性文法属性文法(attribute grammar)是一个三元是一个三元组组:A=(G,V,F)F F：关于属性的属性断言或谓词集关于属性的属性断言或谓词集关于属性的属性断言或谓词集关于属性的属性断言或谓词集. .每个断言与一个产每个断言与一个产每个断言与一个产每个断言与一个产生式相联生式相联生式相联生式相联. .而此断言只引用该产生式左端或右端的终结而此断言只引用该产生式左端或右端的终结而此断言只引用该产生式左端或右端的终结

2、而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性符或非终结符相联的属性符或非终结符相联的属性符或非终结符相联的属性V V：有穷的属性集，每个属性与文法的一个终结符或非终有穷的属性集，每个属性与文法的一个终结符或非终有穷的属性集，每个属性与文法的一个终结符或非终有穷的属性集，每个属性与文法的一个终结符或非终结符相连结符相连结符相连结符相连G G：是一个上下文无关文法是一个上下文无关文法是一个上下文无关文法是一个上下文无关文法表达式文法表达式文法 ET+T| T or TET+T| T or T T n | true | false T n | true | falseE E T T1

3、 1 + T+ T2 2 T T1 1.type = .type = intint AND T AND T2 2.type = T.type = T1 1. type . type E.type := E.type :=intint E E T T1 1 or T or T2 2 T T1 1.type = .type = boolbool AND T AND T2 2.type= T.type= T1 1.type.type E.type := E.type :=boolbool T n T.type := T n T.type := intint T true T.type := T tr

4、ue T.type := boolbool T false T.type := T false T.type := boolbool 类型检查的属性文法：类型检查的属性文法： 语 义 规 则 L EE E1+TE TT T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval产 生 式综合属性综合属性val综合属性综合属性n在分析树中，如果一个结点的某一个属性由其子结点的属在分析树中，如果一个

5、结点的某一个属性由其子结点的属性确定，则称这种属性为该结点的综合属性。性确定，则称这种属性为该结点的综合属性。产生副作用产生副作用的语义规则的语义规则，如打印一个如打印一个值、向符号值、向符号表中插入信表中插入信息或更新一息或更新一个全程变量个全程变量等。等。语义规则函数都不具有副作用的语法语义规则函数都不具有副作用的语法制导定义称为制导定义称为属性文法。属性文法。 在语法制导定义中，一条语义规则完成一个计算属在语法制导定义中，一条语义规则完成一个计算属在语法制导定义中，一条语义规则完成一个计算属在语法制导定义中，一条语义规则完成一个计算属性值的动作。性值的动作。性值的动作。性值的动作。dig

6、itdigit是终结符，只使用综合属性，且其是终结符，只使用综合属性，且其是终结符，只使用综合属性，且其是终结符，只使用综合属性，且其属性值由词法分析器提供，通常不要计算属性值。属性值由词法分析器提供，通常不要计算属性值。属性值由词法分析器提供，通常不要计算属性值。属性值由词法分析器提供，通常不要计算属性值。LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树如果一个语法制如果一个语法制导定义仅仅使

7、用导定义仅仅使用综合属性，则称综合属性，则称这种语法制导定这种语法制导定义为义为S属性定义属性定义。通常采用通常采用自底向自底向上的方法上的方法对其分对其分析树加注释，即析树加注释，即从树叶到树根，从树叶到树根，按照语义规则计按照语义规则计算每个节点的属算每个节点的属性值。性值。继承属性继承属性n n一个结点的继承属性值是由此结点的父结点和一个结点的继承属性值是由此结点的父结点和一个结点的继承属性值是由此结点的父结点和一个结点的继承属性值是由此结点的父结点和/ /或或或或兄弟结点的某些属性来决定的。兄弟结点的某些属性来决定的。兄弟结点的某些属性来决定的。兄弟结点的某些属性来决定的。生 产 式语

8、 义 规 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)继承属性继承属性L.in语句：语句：语句：语句：real id1real id1， id2 id2， id3 id3的分析树，采用自上而的分析树，采用自上而的分析树，采用自上而的分析树，采用自上而下的分析方法下的分析方法下的分析方法下的分析方法 产 生 式语 义 规 则D TL T int T real L L1,idL idL.in:

9、=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.，语法制导翻译概论n n在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。参见P.157-159对表达式2+3*5进行的分析中间代码的形成n n中间代码的常见形式：中间代码的常见形式：n n逆波兰记号逆波兰记号逆波兰记号逆波兰

10、记号n n三元式（树形表示）三元式（树形表示）三元式（树形表示）三元式（树形表示）n n间接三元式间接三元式间接三元式间接三元式n n四元式四元式四元式四元式逆波兰记号（后缀式）n n将运算对象写在前面，把运算符号写在后将运算对象写在前面，把运算符号写在后面面表达式表达式逆波兰式逆波兰式a+ba+babab+ +a+b*ca+b*cabcabc*+*+( (a+b)*ca+b)*cab+cab+c* *a:=b*c+b*da:=b*c+b*dabcabc* *bdbd*+:=*+:=计算方法：自左向右扫描逆波兰式，遇到运算对计算方法：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数

11、目的运算对象出象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈栈计算后结果入栈。逆波兰记号的扩充用途- i- ii iGotoGoto L LL L jumpjumpif E then Sif E then S1 1 else S else S2 2ESES1 1S S2 2￥AnmAnmnmAnmA subssubs复杂性：复杂性：压栈的可能是地址（如变量赋值），不是值；压栈的可能是地址（如变量赋值），不是值；栈中不一定产生结果。栈中不一定产生结果。逆波兰示例 把下述产生式定义的算术表达式映射到后缀式把下述产生式定义的算术表达式映射到后缀式表示：表示： EE+T E T T T F

12、 T F F (E) F a E = ET+ E = T T = TF T = F F = E F = a 产生式 翻译成分n n确定输入确定输入确定输入确定输入a+aa+a a a的输出：的输出：的输出：的输出： ( (E,E)E,E)(E+T(E+T，ET+)ET+) (T+T (T+T，TT+)TT+) (F+T (F+T，FT+)FT+) ( (a+Ta+T，aTaT+)+) ( (a+Ta+T F F，aTFaTF +)+) ( (a+Fa+F F F，aFFaFF +)+) ( (a+aa+a F F，aaFaaF +)+) ( (a+aa+a a a，aaaaaa +)+) EE

13、+T E T T T F T F F (E) F a E = ET+ E = T T = TF T = F F = E F = a 产生式 翻译成分将下列语句翻译成后缀式：后缀式： if xy then y=y+z else x=x+z错误的翻译：错误的翻译： （if E then Sif E then S1 1 else S else S2 2 翻译成：翻译成：ESES1 1S S2 2￥）￥）xyyzy+ =z+xx=￥正确的翻译：正确的翻译：x yy zy+=z +x x=L1JzJzL2JmpJmp L1 L2三元式和树形表示三元式和树形表示n n格式：(算符, 第一运算对象, 第二运

14、算对象)n n如：a := b*c + b*d(1) ( *，b，c )(2) ( *，b，d )(3) ( +，(1)，(2) )(4) ( :=，(3)，a ):=a+*bcbd三元式表示三元式表示树形表示树形表示间接三元式间接三元式n n执行表执行表n n三元式表三元式表例如：例如：x:=(a+b)*c b:=a+b y:=c*(a+b)n n三元式：三元式：(1)(1)( +， a ，b )(2)(2)( *， (1)，c )(3)(3)( :=，(2)，x )(4)(4)( +， a ，b )(5)(5)( :=，(4)，b )(6)(6)( +， a， b )(7)(7)( *，

15、c，(6) )(8)(8)( :=，(7)，y )n n间接三元式：间接三元式： 三元式表三元式表三元式表三元式表 执行表执行表执行表执行表(1)(1)( +，a，b ) (1)(1)(2)(2)( *，(1)，c ) (2)(2)(3)(3)( :=，(2)，x ) (3)(3)(4)(4)( :=，(1)，b ) (1)(1)(5)(5)( :=，(2)，y ) (4)(4) (1)(1) (2)(2) (5)(5)四元式n n格式：格式：格式：格式：( (算符算符算符算符, , 第一运算对象第一运算对象第一运算对象第一运算对象, , 第二运算对象第二运算对象第二运算对象第二运算对象, ,

16、 结果结果结果结果) )n n如：如：如：如：a:=b*c+b*da:=b*c+b*d (1) (1)( *( *， b b， c c， t1 ) t1 ) (2) (2)( *( *， b b， d d， t2 ) t2 ) (3) (3)( +( +， t1 t1，t2t2， t3 ) t3 ) (4) (4)( :=( :=，t3t3， ， a ) a )四元式的特点n n类似于三地址指令n n利于优化和代码生成四元式的直观表示n nt1 := b * ct2 := b * dt3 := t1 + t2a := t3n n(jump， ， ，L) goto Ln n(jrop，B，C，L

17、) if B rop C goto L简单赋值语句的翻译四元式形式四元式形式四元式形式四元式形式 : : t :=arg1 op arg2t :=arg1 op arg2语义属性：语义属性：语义属性：语义属性：id.name, E.placeid.name, E.place 函数：函数：函数：函数：lookup(id.name) ;lookup(id.name) ; 过程：过程：过程：过程：emit(t := arg1 op arg2); emit(t := arg1 op arg2); newtempnewtemp; ; 返回指向返回指向id的指针的指针输出四元式输出四元式生成临时变量生成临

18、时变量E.place:值值E的位置的位置产生式和语义描述：产生式和语义描述：(1) S id := E P:=lookup (id.name) ; if P nil then emit( P“:=”E.place) else error (2) EE1+E2 E.place:= newtemp; emit(E.place“:=” E1.place“+”E2.place)(3) EE1*E2 E.place:= newtemp; emit(E.place“:=” E1.place“*”E2.place)返回返回(4) E - E1 E.place:=newtemp; emit(E.place“:

19、=”“uminus” E1.place)(5) E( E1) E.place:= E1.place(6) Eid P:=lookup(id.name); if P nil then E.place:=P else error返回返回例：将下列语句翻译成四元式形式：例：将下列语句翻译成四元式形式：例：将下列语句翻译成四元式形式：例：将下列语句翻译成四元式形式： A:=-B*(C+D)A:=-B*(C+D)# A:=-B*(C+D)#查看语意义子程序查看语意义子程序13查看语意义子程序查看语意义子程序46 栈栈 余留输入字符余留输入字符 语意义动作语意义动作 产生的四元式产生的四元式#idA :=

20、-B*(C+D)#idA := -B*(C+D)#idA :=- B*(C+D)#idA :=-idB *(C+D)#idA :=-EB *(C+D)# Sub6#idA :=ET1 *(C+D)# Sub4 (，B， ，T1）#idA := ET1 * (C+D)#idA := ET1 * ( C+D)#idA := ET1 * (idC +D)#idA := ET1 * (EC +D)# Sub6#idA := ET1 * (EC+ D)#查看语意义子程序查看语意义子程序13查看语意义子程序查看语意义子程序46 栈栈 余留输入字符余留输入字符 语意义动作语意义动作 产生的四元式产生的四元式

21、#idA := ET1 * (EC+ D)#idA := ET1 * (EC+idD )#idA := ET1 * (EC+ED )# Sub6#idA := ET1 * (ET2 )# Sub2 (+，C，D，T2）#idA := ET1 * (ET2) #idA := ET1 * ET2 # Sub5#idA := ET3 # Sub3 (*，T1，T2，T3）#S # Sub1 (:=，T3， ，A）语句语句语句语句 A:=-B*(C+D) A:=-B*(C+D) 翻译成四元式形式为：翻译成四元式形式为：翻译成四元式形式为：翻译成四元式形式为：(1) （ ， B ， ， T1 ）(2)

22、（ +， C ， D， T2 ）(3) （ *， T1 ，T2， T3 ）(4) （ :=，T3 ， ， A ）类类 型型 转转 换换 的的 语语 义义 处处 理理EE1*E2 E.place := E.place := newtempnewtemp; ; if E if E1 1.type=.type=intint AND E AND E2 2.type=.type=intint then then Begin emit(E.place, :=, E Begin emit(E.place, :=, E1 1.place, *.place, *i i, E, E2 2.place,).plac

23、e,)； E.type = E.type = intint； End End else if E else if E1 1.type=real AND E.type=real AND E2 2.type=real then.type=real then Begin emit(E.place, :=, E Begin emit(E.place, :=, E1 1.place, *.place, *r r, E, E2 2.place,).place,)； E.type = real E.type = real； End End else if E else if E1 1.type=.type=

24、intint /* E/* E2 2.type=real */ .type=real */ thenthen Begin t := Begin t := newtempnewtemp; emit(t, :=, ; emit(t, :=, irtirt, E, E1 1.place,).place,)； emit(E.place, :=, t, * emit(E.place, :=, t, *r r, E, E2 2.place,).place,)； E.type = real E.type = real； End End else else /* E/* E1 1.type=.type= re

25、alreal AND AND E E2 2.type= .type= intint */ */ Begin t := Begin t := newtempnewtemp; ; emit(temit(t, :=, , :=, irtirt, E, E2 2.place).place)； emit(E.placeemit(E.place, :=, E, :=, E1 1.place, *.place, *r r, t), t)； E.typeE.type = real = real； End End E.false控制语句中布尔表达式的翻译控制语句控制语句Sif E then S1 else S2

26、 E的代码的代码 E.true E.true: S1的代码的代码 goto outE.false: S2的代码的代码out:1 . 把条件转移的布尔表达式把条件转移的布尔表达式 E 翻译成仅含翻译成仅含 条件真条件真 转转 和和 无条件无条件 转转 的四元式的四元式 E：a rop b ?if a rop b goto E.true goto E.false如如 ：ab or cd and ef 可可 翻译成如下四元式：翻译成如下四元式：(1) if ab goto E.true(2) goto (3)(3) if cd goto (5)(4) goto E.false(5) if ef go

27、to E.true(6) goto E.false (翻译翻译 不是最优不是最优)2拉链返填拉链返填 （10） goto L （10）goto 0 链尾链尾 （10）（20） goto L （20）goto 10 （30） goto L (30) goto 20 链头链头（30）（40）L： （40）L: ?语句语句if ab or cd and ef then S1 else S2的四元式的四元式(1) if ab goto (7) (E.true ) (1)和和(5）(2) goto (3) 拉链拉链（真）（真）(3) if cd goto (5)(4) goto (p+1)(E.fals

28、e)(4) 和和(6)(5) if ef goto (7)拉链拉链（假）（假）(6) goto (p+1)(7)( S1的四元式的四元式 (p-1) ）(p) goto (q)(p+1) (S2的四元式的四元式(q-1) ）(q)(1) if ab goto (E.true )(2) goto (3)(3) if cd goto (5)(4) goto (E.false)(5) if ef goto (E.true ) (6) goto (E.false) (E.true)( S1的四元式序列的四元式序列 ）(p) goto (q)(E.false) (S2的四元式序列的四元式序列(q-1)

29、）(q)语义描述使用的变量和过程：语义描述使用的变量和过程： E.true ： “真真”链，链， E.false ： “假假”链链 。 E.codebegin ： E的第一个四元式的第一个四元式 Nextstat： 下一四元式地址下一四元式地址 过程：过程： emit( ) 输出一条四元式输出一条四元式 merge(p1, p2) 把把p1的链头填在的链头填在p2的链尾的链尾例：例： merge(p1, p2)(p10) 0 p1链链 (p100) p10(p1) p100(p20) 0p2链链 (p200) p20(p2) p200 backpatch(p,t) 把把p所链接的每个四元式所链

30、接的每个四元式的第四区段都填为的第四区段都填为t语义描述使用的变量和过程：语义描述使用的变量和过程： E.true ： “真真”链，链， E.false ： “假假”链链 。 E.codebegin ： E的第一个四元式的第一个四元式 Nextstat： 下一四元式地址下一四元式地址 过程：过程： emit( ) 输出一条四元式输出一条四元式 merge(p1, p2) 把把p1的链头填在的链头填在p2的链尾的链尾例：例： merge(p1, p2)(p10) 0 p1链链 (p100) p10(p1) p100(p20) p100p2链链 (p200) p20(p2) p200 backpa

31、tch(p,t) 把把p所链接的每个四元式所链接的每个四元式的第四区段都填为的第四区段都填为t自下而上分析中的一种翻译方案：自下而上分析中的一种翻译方案：(1) EE1 or E2 backpatch(E1.false, E2.Codebegin); E.Codebegin:= E1.codebegin; E.true:=merge(E1.true, E2.true) E.false:= E2.false(2) EE1 and E2 backpatch(E1.true, E2.codebegin); E.Codebegin:= E1.codebegin; E.true:= E2.true; E.false:= merge(E1.false, E2false);(3) Enot E1 E.true:= E1.false; E.Codebegin:= E1.codebegin; E.false:= E1.true