编译原理习题解答.ppt

1、1.从下列文法中消除左递归，提取左公因子,SAa|Ab|c AAd|Se|f,先消除直接的左递归 ASeA|fA AdA| 再消除间接左递归： SSeAa|SeAb|fAa|fAb|c SfAaS|fAbS|cS S eAaS|eAbS| ,SfAaS|fAbS|cS S eAaS|eAbS| AdA| 提取左公因子： SfAB|cS BaS|bS SeAC| CaS|bS A dA| ,P81 1.Sa|(T) TT,S|S,消除左递归：,Sa|(T) TST T，ST|,Procedure T Begin S;T End,Procedure S If sym=( then Begin Ad

2、vance;T If sym=) then advance Else error End Else if sym= then advance Else if sym=a then advance Else error,Procedure T If sym=, then Begin Advance; S;T End,(2)判断是否为LL(1),First(T)=,， First(T) = First(S) =a， ,( Follow(S)=#，,，） Follow(T)=） Follow(T)=）,T有两个候选， 但first(T)follow(T)= 文法是LL(1)的,构造预测分析表：,2.

3、 ETE E+E| TFT TT| FPF F*F| P(E)|a|b|,FIRST(E)=(,a,b; FIRST(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| FIRS

4、T(+E)FOLLOW(E)=+ ) ,#=; TT| FIRST(T)FOLLOW(T)=(,a,b+,),#=; F*F| FIRST(*F)FOLLOW(F)=*+, ( , ),a,b,#=; P(E)|a|b| FIRST(“(E)”)FIRST(a) FIRST(b) FIRST()=; 所以是LL(1)文法。,构造预测分析表：,4.E-E E(E)|VT T-E| VidF F(E)| ,FIRST(E)=-,(,id; FIRST(V)=id; FIRST(T)=-, ; FIRST(F)=(, ;,FOLLOW(E)=),#; FOLLOW(V)=-,),#; FOLLOW(

5、T)=),#; FOLLOW(F)=-,),#;,第五章,3.Sa|(T) TT,S|S,FIRSTVT(S)=a,(,; FIRSTVT(T)=a,(, ,;,LASTVT(S)=a,),; LASTVT(T)=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,=

6、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,(,); 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),SAS S.AS S.b A.

7、SA A.a,I3go(I0,b)=Sb.,I4go(I0,a)=Aa.,I5go(I1,A),I7go(I2,S),S.S S.AS S.b A.SA A.a,I1go(I0, S):,SS AS.A A.SA A.a S.AS S.b,I0:,ASA. SA.S S.AS S.b A.SA A.a,SAS. AS.A A.SA A.a S.AS S.b,I6go(I1,S),AS.A A.SA A.a S.AS S.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存在归约-移

8、进冲突,求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,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,

9、A),SAS,#/a/b S.AS,#/a/b S.b,#/a/b A.SA,a/b A.a,a/b,I3go(I0,b) Sb.,#/a/b,I4go(I0,a) Aa.,a/b,I5go(I1,A),S.S,# S.AS,#/a/b S.b,#/a/b A.SA,a/b A.a,a/b,I1go(I0, S):,SS,# AS.A, a/b A.SA,a/b A.a,a/b S.AS,a/b S.b,a/b,I0:,ASA. ,a/b SA.S ,a/b S.AS,a/b S.b,a/b A.SA,a/b A.a,a/b,I6go(I1,S),AS.A, a/b A.SA,a/b A.a,

10、a/b S.AS,a/b S.b,a/b,I7go(I1,b) Sb.,a/b,I8go(I2,S),SAS. ,#/a/b AS.A ,a/b A.SA,a/b A.a,a/b S.AS,a/b S.b,a/b,I9go(I5,S),SAS. ,a/b AS.A ,a/b A.SA,a/b A.a,a/b S.AS,a/b S.b,a/b,I10go(I5,A),SAS,a/b S.AS,a/b S.b,a/b A.SA,a/b A.a,a/b,I5,I8,I9存在归约-移进冲突,该文法不是LR(1)文法，也不是LALR文法。,SA AAb|bBa B aAc|a|aAb,7 证明下列文法是

11、SLR(1)的,但不是LR(0)的。,FIRST(A)=b FIRST(B)=a,FOLLOW(S)=# FOLLOW(A)=#,b,c FOLLOW(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.S S.A A.Ab A.bBa,SS.,I2=go(I0,A):,SA. AA.b,I3=go(I0,b):,Ab.Ba B .aAc B .a B .aAb,I4=go(I2,b):,AAb.,I5=go(I3,B):,I6=go(I3

12、,a):,AbB.a,B a.Ac B a. B a.Ab A.Ab A.bBa,I7=go(I5,a):,AbBa.,I8=go(I6,A):,go(I6,b) = I3,B aA.c B aA.b AA.b,I9=go(I8,c):,B aAc.,I10=go(I8,b):,B aAb. AAb.,LR(0)分析表(有冲突),SLR(1)分析表（没有冲突）,8.证明下列文法是LL(1)的但不是SLR(1)的,SAaAb|BbBa A B,该文法没有左递归和左公因子,FIRST(A)=FIRST(B)=,FIRST(AaAb)FIRST(BbBa) =ab=,所以该文法是LL(1)文法。,F

13、OLLOW(S)=#,FOLLOW(A)=FOLLOW(B)=a,b,拓广文法为：(0)SS (1)SAaAb (2)SBbBa (3)A (4)B,LR(0)项目集规范族为：,I0:,S.S S.AaAb S.BbBa A. B.,I1=go(I0,S):,SS.,I2=go(I0,A)= SA.aAb,I3=go(I0,B)= SB.bBa,I4=go(I2,a):,SAa.Ab A.,I5=go(I3,b):,SBb.Ba B.,I6=go(I4,A):,SAaA.b,I7=go(I5,B):,SBbB.a,I8=go(I6,b):,SAaAb.,I9=go(I7,a):,SBbBa.,

14、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,a B.d,c,I1=go(I0,S),SS. ,#,I2=go(I0,A),SA.a,#,I3=go(I0,b),Sb.Ac,# Sb.Ba,# A.d,c B.d,a,I4=go(I0,B),SB.c,#,I5=go(I0,d),Ad

15、. ,a Bd. ,c,I6=go(I2,a),SAa. ,#,I7=go(I3,A),SbA.c,#,I8=go(I3,B),SbB.a,#,I9=go(I3,d),Ad. ,c Bd. ,a,I11=go(I7,c),SbAc. ,#,I12=go(I8,a),SbBa. ,#,I10=go(I4,c),SBc. ,#,LR(1)分析表为：,同心集只有I5和I9，合并同心集后：,I59：Ad. ,a/c Bd. ,a/c,产生归约归约冲突，不是LALR(1)文法。,构造LR(0)项目集规范族：,I0:,S.S S.Aa S.bAc S.Bc S.bBa A.d B.d,I1=go(I0,S),SS.,I2=go(I0,A),SA.a,I3=go(I0,b),Sb.Ac Sb.Ba A.d B.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.S I1: S