编译原理第7章中间语言(3)

1、 语法制导翻译器语法制导翻译器的的结构，结构，可描述为：可描述为： 扩展的扩展的语法分析器语法分析器 翻译文法翻译文法+ + 自顶向下自顶向下翻译文法翻译文法的要求：的要求： 源文法应满足自顶向下分析要求源文法应满足自顶向下分析要求( (如如 LL(1)LL(1)文法文法) )； 属性是自顶向下可求值的属性是自顶向下可求值的( (属性计算不发生冲突属性计算不发生冲突) )； 动作符号可插入到产生式右部任何位置。动作符号可插入到产生式右部任何位置。 自底向上自底向上翻译文法翻译文法的要求：的要求： 源文法应满足自底向上分析要求源文法应满足自底向上分析要求( (如如 LR( )LR( )文法文法)

2、 )； 属性是自底向上可求值的属性是自底向上可求值的( (属性计算不发生冲突属性计算不发生冲突) )； 动作符号只能位于产生式的最右端。动作符号只能位于产生式的最右端。L-L-属性翻译文法属性翻译文法S-S-属性翻译文法属性翻译文法其中其中 设置设置语义栈：语义栈：SEMmSEMm四元式区：四元式区：QTqQTq 翻译文法设计翻译文法设计 递归子程序的扩展递归子程序的扩展 动作符号在哪，就在哪执行之；动作符号在哪，就在哪执行之； 主控程序主控程序(Z - E )(Z - E )功能：功能：初始化；初始化； 结果输出。结果输出。E - T + TE - T + T GEQ(+)GEQ(+) |-

3、 T|- T GEQ(-)GEQ(-) T - F T - F * * F F GEQ(GEQ(* *) ) |/ T|/ T GEQ(/)GEQ(/) F - iF - i PUSH(i)PUSH(i) | ( E )| ( E )G1(E):G1(E):【例【例7.107.10】算术表达式四元式算术表达式四元式翻译器的设计翻译器的设计1 1：-暂存运算对象的属性值。暂存运算对象的属性值。-四元式生成结果的存储区。四元式生成结果的存储区。 R R2 2 入口入口出口出口NEXT(w)T + +Tyn - -nNEXT(w)TyGEQ(+)GEQ(+)GEQ(-)GEQ(-)子程序子程序 E

4、R R3 3 R R1 1主主程程序序 Z 开始开始 结束结束结果输出结果输出 初始化初始化 #NEXT(w)err0ynR R0 0E RiRi 返回地址返回地址 R R5 5 入口入口出口出口NEXT(w)F * *Fyn / /nNEXT(w)FyGEQ(GEQ(* *) )GEQ(/)GEQ(/)子程序子程序 T R R6 6 R R4 4入口入口出口出口 i (err1NEXT(w)err2NEXT(w)E )yyynnn子程序子程序 F R R7 7PUSH(i)PUSH(i)RiRi 返回地址返回地址 设设 待翻译的表达式：待翻译的表达式： a a* *(b/c)#(b/c)#

5、QTq QTqSEMmSEMm w w 返回地址栈返回地址栈递归子程序栈递归子程序栈Z Z E ER R0 0 a aT TR R1 1F FR R4 4a a * *Z Z E E T T R R0 0R R1 1 ( (Z Z E E T T F FR R0 0R R1 1R R5 5a aa a b bZ Z E E T T F F E ER R0 0R R1 1R R5 5R R7 7T TR R1 1F FR R4 4a a b b / /Z Z E E T T F FR R0 0R R1 1R R5 5R R7 7R R1 1a a c cZ Z E E T T F FF FR R

6、0 0R R1 1R R5 5R R7 7R R1 1R R6 6a ac cZ Z E E T T F FR R0 0R R1 1R R5 5R R7 7R R1 1) )a a(/b,c,t(/b,c,t1 1) )a a t t1 1) )Z Z E E T T F FR R0 0R R1 1R R5 5R R7 7) )a aZ Z E E T T F FR R0 0R R1 1R R5 5 # #a aZ Z E E T TR R0 0R R1 1( (* *a,t1,ta,t1,t2 2) )t t2 2 # #Z Z E ER R0 0 # #t t2 2Z ZOk!Ok!b b

7、b bb b c ct t1 1t t1 1E E T TE E T TE E T TE EZ,EZ,E子程序子程序T,FT,F子程序子程序递归子程序递归子程序调用算法调用算法入口时： 把返回地址压入返回地址栈并进入；出口时： 把返回地址弹出返回地址栈并返回。【例【例7.117.11】算术表达式四元式算术表达式四元式翻译器的设计翻译器的设计2 2： 设置设置语义栈：语义栈：SEMmSEMm四元式区：四元式区：QTqQTq语法栈：语法栈：SYNn ;SYNn ; 翻译文法设计翻译文法设计E - T EE - T E E E - - + + T T GEQ(+)GEQ(+) E E | | - -

8、 T T GEQ(-)GEQ(-) E E | | T - F TT - F T T T - - * * F F GEQ(GEQ(* *) ) T T | | / / F F GEQ(/)GEQ(/) T T | | F - iF - i PUSH(i)PUSH(i) | ( E ) | ( E ) LL(1) LL(1)分析器的扩展分析器的扩展 当当动作符号动作符号位于栈顶时，执行之；位于栈顶时，执行之； 当产生式当产生式( (逆序逆序) )压栈时，压栈时，动作符号动作符号也不例外也不例外；LL(1) LL(1) 分析表：分析表：* */ / ( () )T TTTF FEEE E# #-

9、-+ +i i设设 待翻译的表达式：待翻译的表达式： a+ba+b* *c#c#SEMmSEMm QTq QTq 操作操作w wx x SYNn SYNn#E#Ea aE EPUSHPUSHR R# #ETETT Ta a PUSHPUSHR RTFTF#E#EF Fa a PUSHPUSHR R#ET#ETPUSH(a)PUSH(a)a aa aa a#ET#ETPUSH(a)PUSH(a)+ +NEXT(w)NEXT(w)a a#ET#ETTT + +a aPUSHPUSHR R#E#EEE + + PUSHPUSHR Ra a# #EEGEQ(+)GEQ(+)T+T+ + +a aNEX

10、T(w)NEXT(w)b b#E#EGEQ(+)GEQ(+)T TT TPUSHPUSHR Ra a#E#EGEQ(+)GEQ(+)TFTFF Fb b PUSHPUSHR Ra a接下页接下页翻译翻译文法文法设设 待翻译的表达式：待翻译的表达式： a+ba+b* *c#c# SEMmSEMm QTq QTq 操作操作w wx x SYNn SYNn接上页接上页#E#EGEQ(+)GEQ(+)TTPUSH(b)PUSH(b)b b b b b b NEXT(w)NEXT(w) a a#E#EGEQ(+)GEQ(+)TTPUSH(b)PUSH(b)* *a ab b#E#EGEQ(+)GEQ(+

11、)TT* *TTababPUSHPUSHR R#E#EGEQ(+)GEQ(+)TTGEQ(GEQ(* *) )F F* * * *abab* * NEXT(w)NEXT(w)c c#E#EGEQ(+)GEQ(+)TTGEQ(GEQ(* *) )F FababF FPUSHPUSHR R#E#EGEQ(+)GEQ(+)TTGEQ(GEQ(* *) )c cababPUSH(c)PUSH(c)c cc cNEXT(w)NEXT(w)# #abab#E#EGEQ(+)GEQ(+)TTGEQ(GEQ(* *) )PUSH(c)PUSH(c)c c#E#EGEQ(+)GEQ(+)TTGEQ(GEQ(*

12、*) )# #abcabc( (* *b,c,tb,c,t1 1) )#E#EGEQ(+)GEQ(+)TT# #a aTT#E#EGEQ(+)GEQ(+)# #atat1 1(+a,t(+a,t1 1,t,t2 2) )#E#Et t2 2# #EEt t1 1# # #t t2 2okok翻译文法翻译文法分析表分析表【例【例7.127.12】算术表达式四元式算术表达式四元式翻译器的设计翻译器的设计3 3： 设置设置 翻译文法翻译文法设计设计( (带有状态编码带有状态编码) )语义栈：语义栈：SEMmSEMm四元式区：四元式区：QTqQTq语法栈：语法栈：SYNn ;SYNn ; LR() L

13、R() 分析表的扩展分析表的扩展 LR() LR()分析表中的分析表中的 r(i)r(i) 执行下述执行下述两种操作两种操作： 首先执行首先执行动作符号动作符号( (翻译函数翻译函数) )； 然后执行然后执行归约操作归约操作( (按产生式按产生式 i i 归约归约) )。Z-EZ-E1 1 (0)(0)E-EE-E2 2 + +3 3 T T4 4GEQ(+)GEQ(+)|T|T5 5 T-TT-T6 6 * *7 7 F F8 8GEQ(GEQ(* *)|F|F9 9 F-iF-i1010PUSH(i)PUSH(i) |(|(1111 E E1212 ) )13 13 Z-EZ-E1 1 (

14、0)(0)E-EE-E2 2 + +3 3 T T4 4GEQ(+)GEQ(+)|T|T5 5 T-TT-T6 6 * *7 7 F F8 8GEQ(GEQ(* *)|F|F9 9 F-iF-i1010PUSH(i)PUSH(i) |(|(1111 E E1212 ) )13 13 0 0F FT TE E# #) )( (* *+ +i i 确定的确定的SLR(1)SLR(1)分析表分析表构造算法：构造算法：F9F9T5,6T5,6E1,2E1,2(11(11i10i10OKOK+3+31,21,2F9F9T4,6T4,6(11(11i10i103 3r(1)r(1)r(1)r(1)* *7

15、 7r(1)r(1)4,64,6r(2)r(2)r(2)r(2)* *7 7r(2)r(2)5,65,6F8F8(11(11i10i107 7r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)8 8r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)9 9r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)1010F9F9T5,6T5,6E12,2E12,2(11(11i10i101111)13)13+3+312,212,2r(6)r(6)r(6)r(6)r(6

16、)r(6)r(6)r(6)r(6)r(6)r(6)r(6)1313设设 待翻译的表达式：待翻译的表达式： a a* *b+c#b+c#SEMmSEMmQTqQTq动作符号动作符号w wSYNnSYNn# #0 00 0a a# #0 0a a10101010* * PUSH(a)PUSH(a)a a# #0 0F F9 99 9* *a a# #0 0T T5,65,65,65,6* *a a# #0 0T T5,65,6* *7 77 7b ba a# #0 0T T5,6 5,6 * *7 71010+ +a aPUSH(b)PUSH(b)b bb b1010# #0 0T T5,6 5,

17、6 * *7 7F F8 88 8+ +abab# #0 0T T5,65,65,65,6+ +GEQ(GEQ(* *) )( (* * a b t a b t1 1) )t t1 1# #0 0E E1,21,21,21,2+ +t t1 1# #0 0E E1,21,2 + +3 33 3c ct t1 1# #0 0E E1,2 1,2 + +3 3c c10101010# #t t1 1# #0 0E E1,2 1,2 + +3 3F F9 99 9# #PUSH(c)PUSH(c)c ct t1 1c c# #0 0E E1,2 1,2 + +3 3T T4,64,64,64,6#

18、# GEQ(+)GEQ(+)t t1 1c c(+ t(+ t1 1 c tc t2 2) )# #0 0E E1,21,21,21,2# #结束结束查查SLR(1)SLR(1)分析表分析表【例【例7.127.12】算术表达式四元式算术表达式四元式翻译器的设计翻译器的设计4 4： 设置设置语义栈：语义栈：SEMmSEMm四元式区：四元式区：QTqQTq语法栈：语法栈：SYNn ;SYNn ; 翻译文法设计翻译文法设计 算符优先分析器的扩展算符优先分析器的扩展归约时，只要产生式右部的终结符排列和栈顶归约时，只要产生式右部的终结符排列和栈顶 中的终结符匹配上即可；中的终结符匹配上即可； 规约时，先

19、执行语义动作，后规约规约时，先执行语义动作，后规约 ；E-E + T E-E + T GEQ(+)GEQ(+)| T| TT-T T-T * * F F GEQ(GEQ(* *)| F| F F-iF-iPUSH(i)PUSH(i)|( E )|( E )(3)(3)归约后，得到的非终结符不必入栈。归约后，得到的非终结符不必入栈。 + * i ( ) # + * i ( ) # OK算符优先算符优先 分析表：分析表：设设 待翻译的表达式：待翻译的表达式：a+ba+b* *c#c#翻译翻译文法文法 SYN SYN 关系关系 W W 操作操作 SEM SEM QTq QTq#a移进，读移进，读#规

20、约，不读规约，不读a#+移进，读移进，读#+b移进，读移进，读#+规约，不读规约，不读a b#+*移进，读移进，读#+*c移进，读移进，读#+*规约，不读规约，不读a b c#+规约，不读规约，不读a b c(*,b,c,t1)t1 #规约，不读规约，不读a t1(+,a,t1,t2)#t2 OK 自底向上自底向上中间代码翻译，要求：翻译文法中间代码翻译，要求：翻译文法的的动作符号动作符号必须位于产生式的必须位于产生式的最右端最右端。 . 赋值语句的属性翻译文法：赋值语句的属性翻译文法：G(S): S - vG(S): S - v PUSH(v)PUSH(v) = E= E ASSIASSI(

21、=)(=) ; ;G(S): S - Sa = EG(S): S - Sa = E ASSI(=)ASSI(=) ; ;令令 Sa - vSa - v PUSH(v)PUSH(v) 则有则有 Sa - v Sa - v PUSH(v)PUSH(v) 不满足此条件的属性翻译文法，需要通过不满足此条件的属性翻译文法，需要通过文法变换来解决。文法变换来解决。. . 标号、转向语句属性翻译文法：标号、转向语句属性翻译文法： G(S): S - i G(S): S - i PUSH(i)PUSH(i) : : LABER(i)LABER(i) S ; S ; S - goto iS - goto i G

22、OTO(i)GOTO(i) ; ;令令 Si - i Si - i PUSH(i)PUSH(i) 令令 S Sl l - Si : - Si : LABER(i)LABER(i) 则有则有G(S): S - SG(S): S - Sl l S ; S ; S Sl l - i : - i : LABER(i)LABER(i) Si - i Si - i PUSH(i)PUSH(i) . . 条件语句翻译文法条件语句翻译文法 : : S - if(R)S - if(R) IF(if)IF(if) S S; ; S - Sif S - Sif S S; ; Sel Sel S SIE(ie)IE(

23、ie) 令令 Sel-elseSel-else EL(el)EL(el) 令令 S Sifif- if(R)- if(R) IFIF(if)(if) 则有则有 G(S):G(S):Sif- if(R)Sif- if(R) IF(if)IF(if) Sel- elseSel- else EL(el)EL(el) elseelse EL(el)EL(el) S SIE(ie)IE(ie) . . 循环语句的翻译文法循环语句的翻译文法 G(S): G(S): S - whileS - while WH()WH() (R)(R) DO(do)DO(do) S S WE(we)WE(we);S - Sw

24、h S - Swh Sdo SSdo S WE(we)WE(we) 令令 Sdo- (R)Sdo- (R) DO(do)DO(do) 令令 Swh- whileSwh- while WH()WH() 则有则有 G(S):G(S):Swh- whileSwh- while WH()WH() Sdo- (R)Sdo- (R) DO(do)DO(do) 【习题【习题7.87.8】根据】根据语法制导翻译器语法制导翻译器的实现结构：的实现结构： 【习题【习题7.97.9】根据【例】根据【例7.137.13】表达式的】表达式的四元式属性翻译文法，四元式属性翻译文法，写出写出 a+b/c-d#a+b/c-d#的的 LL(1)LL(1)翻译过程翻译过程。扩展的扩展的语法分析器语法分析器 属性翻译文法属性翻译文法+ + 分别指出下述分别指出下述语法分析器语法分析器式怎样扩展的：式怎样扩展的： 递归子程序，递归子程序， LL(1) LL(1)， LR()