《编译原理习题解答.ppt》由会员分享，可在线阅读，更多相关《编译原理习题解答.ppt（45页珍藏版）》请在三一办公上搜索。
1、1.从下列文法中消除左递归，提取左公因子,SAa|Ab|cAAd|Se|f,先消除直接的左递归ASeA|fAAdA|再消除间接左递归：SSeAa|SeAb|fAa|fAb|cSfAaS|fAbS|cSS eAaS|eAbS|,SfAaS|fAbS|cSS eAaS|eAbS|AdA|提取左公因子：SfAB|cSBaS|bSSeAC|CaS|bSA dA|,P81 1.Sa|(T)TT,S|S,消除左递归：,Sa|(T)TSTT，ST|,Procedure TBegin S;TEnd,Procedure SIf sym=(thenBegin Advance;T If sym=)then adva
2、nce Else errorEndElse if sym=then advanceElse if sym=a then advanceElse error,Procedure TIf sym=,thenBegin Advance;S;TEnd,(2)判断是否为LL(1),First(T)=,，First(T)=First(S)=a，,(Follow(S)=#，,，）Follow(T)=）Follow(T)=）,T有两个候选，但first(T)follow(T)=文法是LL(1)的,构造预测分析表：,2.ETEE+E|TFTTT|FPFF*F|P(E)|a|b|,FIRST(E)=(,a,b;F
3、IRST(E)=+,;FIRST(T)=(,a,b;FIRST(T)=(,a,b,;FIRST(F)=(,a,b;FIRST(F)=*,;FIRST(P)=(,a,b;,FOLLOW(E)=),#;FOLLOW(E)=),#;FOLLOW(T)=+,),#;FOLLOW(T)=+,),#;FOLLOW(F)=+,(,),a,b,#;FOLLOW(F)=+,(,),a,b,#;FOLLOW(P)=+,*,(,),a,b,#;,因为：E+E|FIRST(+E)FOLLOW(E)=+),#=;TT|FIRST(T)FOLLOW(T)=(,a,b+,),#=;F*F|FIRST(*F)FOLLOW(F
4、)=*+,(,),a,b,#=;P(E)|a|b|FIRST(“(E)”)FIRST(a)FIRST(b)FIRST()=;所以是LL(1)文法。,构造预测分析表：,4.E-EE(E)|VTT-E|VidFF(E)|,FIRST(E)=-,(,id;FIRST(V)=id;FIRST(T)=-,;FIRST(F)=(,;,FOLLOW(E)=),#;FOLLOW(V)=-,),#;FOLLOW(T)=),#;FOLLOW(F)=-,),#;,第五章,3.Sa|(T)TT,S|S,FIRSTVT(S)=a,(,;FIRSTVT(T)=a,(,;,LASTVT(S)=a,),;LASTVT(T)=
5、a,),;,文法G2的优先关系表：,表中没有冲突，所以是算符优先文法。,优先函数：,fa,f,f(,g),f),f,f#,g#,ga,g,g(,g,逐次加1法：初始：fa=ga=f=g=f(=g(=f)=g)=f,=g,=f#=g#=1,由：a),所以：fa=g)+1=2;由：),所以：f=g)+1=2;由：(),所以：f)=g)+1=2;由：,),所以：f,=g)+1=2;由：,所以：f,=g,+1=3;,分析过程,补充题：SbAbA(B|aBAa),FIRSTVT(S)=b;FIRSTVT(A)=a,(;FIRSTVT(B)=a,(;,LASTVT(S)=b;LASTVT(A)=a,(,)
6、;LASTVT(B)=);,由SbAb，有：bb,b=b;由A(B|a，有：(a,a=);,该文法的优先关系表：,表中有冲突，所以不是算符优先文法。,5.文法SAS|b ASA|a,拓广文法为：SS(0)SAS(1)Sb(2)ASA(3)Aa(4),该文法的LR(0)项目集规范族为：,I2go(I0,A),SASS.ASS.bA.SAA.a,I3go(I0,b)=Sb.,I4go(I0,a)=Aa.,I5go(I1,A),I7go(I2,S),S.SS.ASS.bA.SAA.a,I1go(I0,S):,SS AS.A A.SAA.aS.ASS.b,I0:,ASA.SA.SS.ASS.bA.SA
7、A.a,SAS.AS.AA.SAA.aS.ASS.b,I6go(I1,S),AS.AA.SAA.aS.ASS.b,0,1,2,S,A,A,4,3,b,a,5,A,S,6,7,S,a,b,b,a,b,a,b,a,转到2,A,S,A,S,A,转到6,S,b,a,I1,I5,I7存在归约-移进冲突,求S，A，S的FOLLOW集：,FIRST(S)=FIRST(A)=a,b;,FOLLOW(S)=#;,FOLLOW(S)=#FIRST(A)=a,b,#;,FOLLOW(A)=FIRST(S)=a,b;,对于I1，FOLLOW(S)=#a,b=.可以用SLR方法解决；,对于I5，FOLLOW(A)=a,
8、ba,b;存在移进归约冲突，而且不能用SLR方法解决；,该文法不是SLR文法。,5.文法SAS|b ASA|a,拓广文法为：SS(0)SAS(1)Sb(2)ASA(3)Aa(4),该文法的LR(1)项目集规范族为：,FIRST(S)=FIRST(A)=a,b,I2go(I0,A),SAS,#/a/bS.AS,#/a/bS.b,#/a/bA.SA,a/bA.a,a/b,I3go(I0,b)Sb.,#/a/b,I4go(I0,a)Aa.,a/b,I5go(I1,A),S.S,#S.AS,#/a/bS.b,#/a/bA.SA,a/bA.a,a/b,I1go(I0,S):,SS,#AS.A,a/bA.
9、SA,a/bA.a,a/bS.AS,a/bS.b,a/b,I0:,ASA.,a/bSA.S,a/bS.AS,a/bS.b,a/bA.SA,a/bA.a,a/b,I6go(I1,S),AS.A,a/bA.SA,a/bA.a,a/bS.AS,a/bS.b,a/b,I7go(I1,b)Sb.,a/b,I8go(I2,S),SAS.,#/a/bAS.A,a/bA.SA,a/bA.a,a/bS.AS,a/bS.b,a/b,I9go(I5,S),SAS.,a/bAS.A,a/bA.SA,a/bA.a,a/bS.AS,a/bS.b,a/b,I10go(I5,A),SAS,a/bS.AS,a/bS.b,a/b
10、A.SA,a/bA.a,a/b,I5,I8,I9存在归约-移进冲突,该文法不是LR(1)文法，也不是LALR文法。,SAAAb|bBaB aAc|a|aAb,7 证明下列文法是SLR(1)的,但不是LR(0)的。,FIRST(A)=bFIRST(B)=a,FOLLOW(S)=#FOLLOW(A)=#,b,cFOLLOW(B)=a,(0)SS(1)SA(2)AAb(3)AbBa(4)B aAc(5)B a(6)B aAb,拓广文法为：,LR(0)项目集规范族为：,I0:,I1=go(I0,S):,S.SS.AA.AbA.bBa,SS.,I2=go(I0,A):,SA.AA.b,I3=go(I0,
11、b):,Ab.BaB.aAcB.aB.aAb,I4=go(I2,b):,AAb.,I5=go(I3,B):,I6=go(I3,a):,AbB.a,B a.AcB a.B a.AbA.AbA.bBa,I7=go(I5,a):,AbBa.,I8=go(I6,A):,go(I6,b)=I3,B aA.cB aA.bAA.b,I9=go(I8,c):,B aAc.,I10=go(I8,b):,B aAb.AAb.,LR(0)分析表(有冲突),SLR(1)分析表（没有冲突）,8.证明下列文法是LL(1)的但不是SLR(1)的,SAaAb|BbBaAB,该文法没有左递归和左公因子,FIRST(A)=FIR
12、ST(B)=,FIRST(AaAb)FIRST(BbBa)=ab=,所以该文法是LL(1)文法。,FOLLOW(S)=#,FOLLOW(A)=FOLLOW(B)=a,b,拓广文法为：(0)SS(1)SAaAb(2)SBbBa(3)A(4)B,LR(0)项目集规范族为：,I0:,S.SS.AaAbS.BbBaA.B.,I1=go(I0,S):,SS.,I2=go(I0,A)=SA.aAb,I3=go(I0,B)=SB.bBa,I4=go(I2,a):,SAa.AbA.,I5=go(I3,b):,SBb.BaB.,I6=go(I4,A):,SAaA.b,I7=go(I5,B):,SBbB.a,I8
13、=go(I6,b):,SAaAb.,I9=go(I7,a):,SBbBa.,I0中，有FOLLOW(A)FOLLOW(B)=a,b,有归约归约冲突，不能用FOLLOW集消除，不是SLR文法,9.拓广文法为：,(0)SS(1)SAa(2)SbAc(3)SBc(4)SbBa(5)Ad(6)Bd,合并同心集法：,构造LR(1)项目集规范族：,I0:,S.S,#S.Aa,#S.bAc,#S.Bc,#S.bBa,#A.d,aB.d,c,I1=go(I0,S),SS.,#,I2=go(I0,A),SA.a,#,I3=go(I0,b),Sb.Ac,#Sb.Ba,#A.d,cB.d,a,I4=go(I0,B)
14、,SB.c,#,I5=go(I0,d),Ad.,aBd.,c,I6=go(I2,a),SAa.,#,I7=go(I3,A),SbA.c,#,I8=go(I3,B),SbB.a,#,I9=go(I3,d),Ad.,cBd.,a,I11=go(I7,c),SbAc.,#,I12=go(I8,a),SbBa.,#,I10=go(I4,c),SBc.,#,LR(1)分析表为：,同心集只有I5和I9，合并同心集后：,I59：Ad.,a/cBd.,a/c,产生归约归约冲突，不是LALR(1)文法。,构造LR(0)项目集规范族：,I0:,S.SS.AaS.bAcS.BcS.bBaA.dB.d,I1=go(I
15、0,S),SS.,I2=go(I0,A),SA.a,I3=go(I0,b),Sb.AcSb.BaA.dB.d,I4=go(I0,B),SB.c,I5=go(I0,d),Ad.Bd.,I6=go(I2,a),SAa.,I7=go(I3,A),SbA.c,I8=go(I3,B),SbB.a,I9=go(I4,c),SBc.,I10=go(I7,c),SbAc.,I11=go(I8,a),SbBa.,求核法：,LR(0)项目集的核为：,I0:S.SI1:SS.I2:SA.aI3:Sb.AcI3:Sb.Ba,I4:SB.cI5:Ad.I5:Bd.I6:SAa.I7:SbA.c,I8:SbB.aI9:SBc.I10:SbAc.I11:SbBa.,计算closure(S.S,#):,S.S,#S.Aa,#S.bAc,#,S.Bc,#S.bBa,#A.d,aB.d,c,计算closure(Sb.Ac,#):,Sb.Ac,#A.d,c,搜索符的传播表：,计算closure(Sb.Ba,#):,Sb.Ba,#B.d,a,
