编译原理 第七章习题

《编译原理 第七章习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．给出下面表达式的逆波兰表示（后缀式）：a*(-b+c)a+b*(c+d/e)notAornot(CornotD)(AandB)or(notCorD)后缀式分别为：ab-c+*abcde/+*+AnotCDnotornotorABandCnotDoror3.请将表达式-（a+b）*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。三元式：(0)（+，a,b）(1)(-,(0),_)(2)(+,c,d)(3)(*,(1),(2))(4)（+，a,b）(5)(+,(4),c)(6)(-,(3),(5))间接三元式：(1)（+，a,b）(2)(-,(1),_)(3

2、)(+,c,d)(4)(*,(2),(3))(5)(+,(1),c)(6)(-,(4),(5))间接代码：（1）（2）（3）（4）（1）（5）（6）四元式：（0）（+，a,b,T1）（1）（-，T1,_,T2）（2）（+，c,d,T3）（3）（*,T2,T3,T4）（4）（+，a,b,T5）（5）（+，T5,c,T6）（6）（-，T4,T6,T7）7.用7.5.1节的方法，把下面语句翻译成四元式序列：WhileA

3、D,104）103（j,_,_,115）104（j=,A,1,106）105（j,_,_,109）106（+,C,1,T1）107（:=,T1,_,C）108（j,_,_,114）109（j≤,A,D,111）110（j,_,_,115）111（+,A,2,T2）112（:=,T2,_,A）113（j,_,_,109）114（j,_,_,100）115第十章3.试对以下基本块B1和B2：B1：A:=B*CD:=B/CF:=2*EG:=B*CH:=G*GF:=H*GL:=FM:=LB2：B:=3D:=A+CE:=A*CG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L

4、:=K+JM:=L分别应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：（1）假设只有G,L,M在基本块后面还要被引用；（2）假设只有L在基本块后面还要被引用。n91n11n21n51n441n31解：B1：F,L,Mn61*En81H2+*A,GD/*BCB1优化后：A:=B*C(1)G:=B*C(2)G:=B*CD:=B/CH:=G*GH:=G*GE:=A+DL:=G*HL:=G*HG:=AM:=LH:=G*GF:=H*GL:=FM:=LB2：n10L,M+n81J+E,In4n51D,Hn71G+*n1n31n91n61n2*KBF315ACB2优化后

5、：B:=3(1)G:=3*F(2)H:=A+CD:=A+CH:=A+CI:=A*CE:=A*CI:=A*CJ:=H+IG:=B*FJ:=H+IL:=15+JH:=DL:=15+JI:=EM:=LJ:=H+IK:=15L:=K+JM:=L5.以下程序是某程序的最内循环，试对它进行循环优化A:=0I:=1L1：B:=J+1C:=B+IA:=C+AIfI=100GOTOL2I:=I+1GOTOL1L2：解：代码外提：B:=J+1删除归纳变量I：由C:=B+I可知I和C成线性关系所以I=100和C=B+100等价，即替换为：R:=100+BIFC=BGOTOL2同理I:=I+1可替换成

6、C:=C+1综上所述代码优化后为：A:=0B:=J+1C:=B+1R:=100+BL1：A:=C+AIfC=RGOTOL2C:=C+1GOTOL1L2：第五章5．文法S->AS

7、bA->SA

8、a(1)列出所有LR(0)项目(2)构造LR(0)项目集规范族及识别活前缀的DFA(3)该文法是SLR的么？若是构造它的SLR分析表。解：扩展文法：S’->SSI6:A->S·AA->SA·A->·aS->·ASS->·bS->AS

9、bA->SA

10、abI1:S’->S·A->S·AA->·aS->·ASS->·bI0:S’->·SS->·AS　S->·bA->·SAA->·aAaSI5:A

11、->SA·S->A·SS->·ASS->·bA->·SAA->·aAaSbAI2:S->A·S　S->·ASS->·bA->·SAA->·aI3:S->b·bbSI4:A->a·aaI7:S->AS·A->S·AA->·SA　A->·aS->·ASS->·bSAbAaaSbA(3)　　　　　　　　　　FollowFirstS’#a,bS#,a,ba,bAa,ba,b冲突项目I１中：有接受项目和移进冲突，可解决.　　　　　＃a,bI5,I7存在移进，归约冲突，不可解决．∵Follow(S)∩a