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

《编译原理：第七章 中间语言(3)》由会员分享，可在线阅读，更多相关《编译原理：第七章 中间语言(3)（20页珍藏版）》请在金锄头文库上搜索。

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

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

3、：初始化；初始化； 结果输出。结果输出。E - T + TE - T + T GEQ(+)GEQ(+) |- T|- T GEQ(-)GEQ(-) T - F * FT - 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：-暂存运算对象的属性值。暂存运算对象的属性值。-四元式生成结果的存储区。四元式生成结果的存储区。 算术表达式算术表达式翻译文法翻译文法的递归子程序：的

4、递归子程序： R R2 2 入口入口出口出口NEXT(w)T + +Tyn - -nNEXT(w)TyGEQ(+GEQ(+) )GEQ(-)GEQ(-)子程序子程序 E 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)err2NEX

5、T(w)E )yyynnn子程序子程序 F R R7 7PUSH(iPUSH(i) )RiRi 返回地址返回地址 算术表达式算术表达式四元式四元式翻译翻译过程过程 ： 设设 待翻译的表达式：待翻译的表达式： a*(b/c)#a*(b/c)# 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

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

7、 F FR R0 0R R1 1R R5 5 # #a aZ Z E E T TR R0 0R R1 1(*a,t1,t(*a,t1,t2 2) )t t2 2 # #Z Z E ER R0 0 # #t t2 2Z ZOk!Ok!b bb bb b c ct t1 1t t1 1E E T TE E T TE E T TE EZ,EZ,E子程序子程序T,FT,F子程序子程序递归子程序递归子程序调用算法调用算法入口时： 把返回地址压入返回地址栈并进入；出口时： 把返回地址弹出返回地址栈并返回。7.4.2 LL(1)7.4.2 LL(1)翻译法翻译法【例例7.117.11】算术表达式四元式算术表

8、达式四元式翻译器的设计翻译器的设计2 2： 设置设置语义栈：语义栈：SEMmSEMm四元式区：四元式区：QTqQTq语法栈：语法栈：SYNn SYNn ; ; 翻译文法设计翻译文法设计E - T EE - T E E E- - + + T T GEQ(+)GEQ(+) E E| | - - 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

9、(1)分析器的扩展分析器的扩展 当当动作符号动作符号位于栈顶时，执行之；位于栈顶时，执行之； 当产生式当产生式( (逆序逆序) )压栈时，压栈时，动作符号动作符号也不例外也不例外； 算术表达式算术表达式四元式四元式翻译翻译过程过程 ：LL(1) LL(1) 分析表：分析表：* */ / ( () )T TTTF FEEE E# #- -+ +i i设设 待翻译的表达式：待翻译的表达式： a+b*c#a+b*c#SEMmSEMm QTq QTq 操作操作w wx x SYNn SYNn#E#Ea aE EPUSHPUSHR R# #ETETT Ta a PUSHPUSHR RTFTF#E#EF

10、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 aNEXT(w)NEXT(w)b b#E#EGEQ(+)GEQ(+)T TT TPUSHPUSHR Ra a#E#EGEQ(+)GEQ(+)TFTFF Fb b PUSHPUSHR Ra a接下页接下页翻译翻译文法文法( ( ( (接上页接上页接上页接上页) ) ) )设设

11、 待翻译的表达式：待翻译的表达式： a+b*c#a+b*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(+)TT* *TTababPUSHPUSHR R#E#EGEQ(+GEQ(+) )TTGEQ(*)GEQ(*)F*F* * *abab* * NEXT(w)NEXT(w)c c#E#EGEQ(+)GEQ(+)TTGEQ

12、(*)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(cPUSH(c) )c c#E#EGEQ(+)GEQ(+)TTGEQ(*GEQ(*) )# #abcabc(*b,c,t(*b,c,t1 1) )#E#EGEQ(+)GEQ(+)TT# #a aTT#E#EGEQ(+GEQ(+) )# #atat1 1(+a,t(+a,t1 1,t,t2 2) )#E#Et

13、t2 2# #EEt t1 1# # #t t2 2okok翻译文法翻译文法分析表分析表7.4.3 LR()7.4.3 LR()翻译法翻译法【例例7.127.12】算术表达式四元式算术表达式四元式翻译器的设计翻译器的设计3 3： 设置设置 翻译文法翻译文法设计设计( (带有状态编码带有状态编码) )语义栈：语义栈：SEMmSEMm四元式区：四元式区：QTqQTq语法栈：语法栈：SYNn SYNn ; ; LR() LR() 分析表的扩展分析表的扩展 LR() LR()分析表中的分析表中的 r(i)r(i) 执行下述执行下述两种操作两种操作： 首先执行首先执行动作符号动作符号( (翻译函数翻译函

14、数) )； 然后执行然后执行归约操作归约操作( (按产生式按产生式 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 SLR(1) SLR(1)分析表的构造：分析表的构造：Z-EZ-E1 1 (0)(0)E-EE-E2 2 + +3 3 T T4 4GEQ(+)GEQ(+)|T|T5 5 T-TT-T6 6 * *7

15、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*7r(1)r(1)4,64,6r(2)r(2)r(2)r(2)*7*7r(2)r(2)5,65,6F8F8(11(11i10i1

16、07 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)r(6)r(6)r(6)r(6)r(6)r(6)r(6)1313 算术表达式算术表达式四元式四元式翻译翻译过程过程 ：设设 待翻译的

17、表达式：待翻译的表达式： a*b+c#a*b+c#SEMmSEMm QTqQTq动作符号动作符号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,6 * *7 7F F8 88 8+ +abab# #0 0T T5,65,65,

18、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# # GEQ(+)GEQ(+)t t1 1c c(+ t(+ t1 1 c tc t2 2)

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

20、动作，后规约 ；E-E + T E-E + T GEQ(+)GEQ(+)| T| TT-T * F T-T * F GEQ(*)GEQ(*)| F| F F-F-i iPUSH(iPUSH(i)|( E )|( E )(3)(3)归约后，得到的非终结符不必入栈。归约后，得到的非终结符不必入栈。 算术表达式算术表达式四元式四元式翻译翻译过程过程 ： + * i ( ) # + * i ( ) # OK算符优先算符优先 分析表：分析表：设设 待翻译的表达式：待翻译的表达式：a+ba+b*c#*c#翻译翻译文法文法 SYN SYN 关系关系 W W 操作操作 SEMSEM QTqQTq #a移进，读

21、移进，读#规约，不读规约，不读a#+移进，读移进，读#+b移进，读移进，读#+规约，不读规约，不读a b#+*移进，读移进，读#+*c移进，读移进，读#+*规约，不读规约，不读a b c#+规约，不读规约，不读a b c(*,b,c,t1)t1 #规约，不读规约，不读a t1(+,a,t1,t2)#t2 OK7.4.5 7.4.5 翻译文法翻译文法的变换问题的变换问题1 1 1 1 自底向上自底向上中间代码翻译，要求：翻译文法中间代码翻译，要求：翻译文法的的动作符号动作符号必须位于产生式的必须位于产生式的最右端最右端。 . 赋值语句的属性翻译文法：赋值语句的属性翻译文法：G(S): S - v

22、G(S): S - v PUSH(v)PUSH(v) = E= E ASSIASSI(=)(=) ; ;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) 不满足此条件的属性翻译文法，需要通过不满足此条件的属性翻译文法，需要通过文法变换来解决。文法变换来解决。7.4.5 7.4.5 翻译文法翻译文法的变换问题的变换问题2 2 2 2. . 标号、转向语句属性翻译文法：标号、转向语句属性翻译文法： G(S): S -

23、i G(S): S - i PUSH(i)PUSH(i) : : LABER(i)LABER(i) S S ; ; S - S - gotogoto i i GOTO(i)GOTO(i) ; ;令令 SiSi - i - i PUSH(i)PUSH(i) 令令 S Sl l - - SiSi : : LABER(i)LABER(i) 则有则有G(S): S - G(S): S - S Sl l S ; S ; S Sl l - i : - i : LABER(i)LABER(i) SiSi - i - i PUSH(i)PUSH(i) 7.4.5 7.4.5 翻译文法翻译文法的变换问题的变换问

24、题3 3 3 3. . 条件语句翻译文法条件语句翻译文法 : : S - if(R)S - if(R) IF(if)IF(if) S S; ; S - S - SifSif S S; ; SelSel S SIE(ieIE(ie) ) 令令 SelSel-else-else EL(el)EL(el) 令令 S Sifif- if(R)- if(R) IFIF(if)(if) 则有则有 G(S):G(S):SifSif- if(R)- if(R) IF(if)IF(if) SelSel- else- else EL(el)EL(el) elseelse EL(el)EL(el) S SIE(ie

25、IE(ie) ) 7.4.5 7.4.5 翻译文法翻译文法的变换问题的变换问题4 4 4 4. . 循环语句的翻译文法循环语句的翻译文法 G(S): G(S): S - whileS - while WH()WH() (R)(R) DO(do)DO(do) S S WE(we)WE(we);S - S - SwhSwh SdoSdo S S WE(we)WE(we) 令令 SdoSdo- (R)- (R) DO(do)DO(do) 令令 SwhSwh- while- while WH()WH() 则有则有 G(S):G(S):SwhSwh- while- while WH()WH() SdoS

26、do- (R)- (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()LR()。【习题习题7.107.10】试对下述试对

27、下述四元式属性翻译文法四元式属性翻译文法进行进行文法变换文法变换，以便适应以便适应自底向上自底向上翻译的要求翻译的要求： S - v S - v PUSH(v)PUSH(v) =E=E ASSI(=)ASSI(=) ; ; 【习题习题7.107.10】P218_11P218_11 SLR(1) SLR(1)分析表的构造：分析表的构造：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) |(|(1

28、111 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*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)r(6)r(6)r(6)r(6)r(6)r(6)r(6)1313谢谢收看！谢谢收看！