编译原理-第5章习题解答

第五章习题解答5.1设一NDPDA识别由下述CFG定义的语言，试给出这个NDPDA的完整形式描述。S→SASCS→εA→AaA→bC→DcDD→d5.2消除下列文法的左递归：①G[A]:A→BXCZWB→AbBcC→AxByCp②G[E]:E→ET+ET–TT→TF*TF/FF→(E)i③G[X]:X→YaZbcY→ZdXefZ→XeYfa④G[A]:A→Ba|Aa|cB→Bb|Ab|d5.3设文法G[语句]：语句→变量:=表达式|if表达式then语句|if表达式then语句else语句变量→i表达式→项|表达式+项项→因子|项*因子因子→变量|′(′表达式′)′试构造该文法的递归下降子程序。5.4设文法G[E]：E→TEE→+ET→FTT→TF→PFF→*FP→(E)a^①构造该文法的递归下降分析程序；②求该文法的每一个非终结符的FIRST集合和FOLLOW集合；③构造该文法的LL（1）分析表，并判断此文法是否为LL（1）文法。5.5设文法G[S]：S→SbAaAB→SbA→Bc①将此文法改写为LL（1）文法；②求文法的每一个非终结符的FIRST集合和FOLLOW集合；③构造相应的LL（1）分析表。5.6设文法G[S]：S→aABbcdA→ASdB→SAheCC→SfCgD→aBD①求每一个非终结符的FOLLOW集合；②对每一个非终结符的产生式选择，构造FIRST集合；③该文法是LL（1）文法。5.7设文法G[E]：E→AaBbA→cAeBB→bd试画出其自上而下分析程序框图。第五章习题参考答案5.1解：NDPDAM=(Q,∑,H,δ,q0,F,Z0)Q={q}∑={a,b,c,d}H={S,A,C,D,a,b,c,d}q0=qF={q}Z0=Sδ:δ(q,,S)={(q,SASC),(q,)}δ(q,,A)={(q,Aa),(q,b)}δ(q,,C)={(q,DCD)}δ(q,,D)={(q,d)}δ(q,a,a)=(q,)δ(q,b,b)=(q,)δ(q,c,c)=(q,)δ(q,d,d)=(q,)5.2解：①利用消除左递归的算法，将非终结符排序为U1=A，U2=B，U3=C，则i=1,j=0时，对文法无影响。i=2,j=1时，因为Ui=B→Ab，Uj=A→Bx|Cz|w所以将B改写为B→Bxb|Czb|wb|Bc消除产生式B的左递归：B→CzbB′|wbB′B′→xbB′|cB′|i=3,j=1时，因为Ui=C→Ax，Uj=A→Bx|Cz|w所以将C改写为C→Bxx|Czx|wx|By|Cpj=2时，因为Ui=C→Bxx|By，Uj=B→CzbB′|wbB′所以将产生式C改写为C→CZbB′xx|CzbB′y|wbB′xx|wbB′y|Czx|wx|Cp消除产生式C的左递归：C→wbB′xxC′|wbB′yC′|wxC′C′→zbB′xxC′|zbB′yC′|zxC′|pC′|所以，文法消除左递归后变为A→Bx|Cz|wB→CzbB′|wbB′B′→xbB′|cB′|C→wbB′xxC′|wbB′yC′|wxC′C′→zbB′xxC′|zbB′yC′|zxC′|pC′|②利用消除左递归的算法，将非终结符排序为：U1=E，U2=T，U3=F则i=1,j=0时，无代入。消除产生式E的左递归：E→T{(T+|T-)}i=2,j=1时，无代入。消除产生式T的左递归：T→{F*|F/F}i=3,j=1时，无代入，也无产生式左递归，不改写产生式。所以，文法消除左递归后变为E→T{(T+|T-)}T→{F*|F/F}F→(E)|I③利用消除左递归的算法，将非终结符排序为:U1=X，U2=Y，U3=Z则i=1,j=0时，无代入i=2,j=1时，因为Ui=Y→Zd|Xe|f，Uj=X→Ya|Zb|c所以将Y改写为Y→Zd|Yae|Zbe|ce|f消除左递归，得到Y→ZdY′|ZbeY′|ceY′|fY′Y′→aeY′|i=3,j=1时，因为Ui=Z→Xe|Yf|a，Uj=X→Ya|Zb|c所以将Z改写为Z→Yae|Zbe|ce|Yf|aj=2时,Ui=Z→Yae|Yf,Uj=Y→ZdY′|ZbeY′|ceY′|fY′所以将Z改写为Z→ZdY′ae|ZbeY′ae|ceY′ae|fY′ae|ZdY′f|ZbeY′f|ceY′f|fY′f|Zbe|ce|a对Z消除左递归得到：Z→ceY′aeZ′|fY′aeZ′|ceY′fZ′|fY′fZ′|ceZ′|aZ′Z′→dY′aeZ′|beY′aeZ′|dY′fZ′|beY′fZ′|beZ′|所以，文法消除左递归以后变为：X→Ya|Zb|cY→ZdY′|ZbeY′|ceY′|fY′Y′→aeY′|Z→ceY′aeZ′|fY′aeZ′|ceY′fZ′|fY′fZ′|ceZ′|aZ′Z′→dY′aeZ′|beY′aeZ′|dY′fZ′|beY′fZ′|beZ′|④利用消除左递归的算法，将非终结符排序为U1=A，U2=B则i=1,j=0时，由于产生式A→Ba|Aa|c存在直接左递归，将其修改为A→BaA′|cA′A′→aA′|i=2,j=1时，因为Ui=B→Ab，Uj=A→BaA′|cA′，所以将产生式B修改为B→Bb|BaA′b|cA′b|d消除产生式B的左递归，得B→cA′bB′|dB′B′→bB′|aA′bB′|所以文法消除左递归后变为A→BaA′|cA′A′→aA′|B→cA′bB′|dB′B′→bB′|aA′bB′|5.3解：首先改写文法，使其满足递归下降分析法对文法的要求。对产生式语句提取最左公共因子得语句→变量:=表达式|if表达式then语句语句′语句′→else语句|对产生式表达式、项消除左递归得表达式→项表达式′表达式′→+项表达式′|项→因子项′项′→*因子|得到等价的文法：语句→变量:=表达式|if表达式then语句语句′语句′→else语句|变量→i表达式→项表达式′表达式′→+项表达式′|项→因子项′项′→*因子|因子→变量|′(′表达式′)′构造该文法的递归下降分析程序如下：PROCEDURE语句；BEGINIFSYMINFIRST(变量)THENBEGIN变量；IFSYM=′:=′THENBEGINREADAWORD；表达式ENDELSEERRORENDELSEIFSYM=′if′THENBEGINREADAWORD；表达式；IFSYM=′then′THENBEGINREADAWORD；语句；语句′ENDELSEERRORENDELSEERROREND；PROCEDURE语句′；BEGINIFSYM=′else′THENBEGINREADAWORD；语句ENDELSEIFNOT(SYMINFOLLOW(语句′))THENERROREND；PROCEDURE变量；BEGINIFSYM=′i′/*i表示标识符*/THENREADAWORDELSEERROREND；PROCEDURE表达式；BEGIN项；表达式′END；PROCEDURE表达式′；BEGINIFSYM=′+′THENBEGINREADAWORD；项；表达式′ENDELSEIFNOT(SYMINFOLLOW(表达式′))THENERROREND；PROCEDURE项；BEGIN因子；项′END；PROCEDURE项′；BEGINIFSYM=′*′THENBEGINREADAWORD；因子ENDELSEIFNOT(SYMINFOLLOW(项′))THENERROREND；PROCEDURE因子；BEGINIFSYM=′(′THENBEGINREADAWORD；表达式；IF(SYM=′)′)THENREADAWORDELSEERRORENDELSEIFSYMINFIRST(变量)THEN变量ELSEERROREND；5.4解：(1)步骤和方法与5.3中类似，略。(2)根据FIRST、FOLLOW集合的求法可以得到：FIRST(E)={(,a,^};FIRST(E′)={+,}FIRST(T)={(,a,^};FIRST(T′)={(,a,^,}FIRST(F)={(,a,^};FIRST(F′)={*,}FIRST(P)={(,a,^}.FOLLOW(E)={),$};FOLLOW(E′)={),$};FOLLOW(T)={+,),$};FOLLOW(T′)={+,),$};FOLLOW(F)={(,a,^,+,),$};FOLLOW(F′)={(,a,^,+,),$};FOLLOW(P)={(,a,^,+,),$,*};(3)根据求得的FIRST、FOLLOW集合可以得到SELECT集合，进而构造出LL(1)分析表如下：+*()a^$EE→TE′E→TE′E→TE′E′E′→+EE′→E′→E′→TT→FT′T→FT′T→FT′T′T′→T′→T′→TT′→T′→TT′→TT′→FF→PF′F→PF′F→PF′F→PF′F′F′→F′→F′→*FF′→F′→F′→F′→F′→PP→(E)P→aP→^空白处为ERROR。表中每一元素的表达式都是唯一的，因此该文法是LL(1)文法。5.5解:(1)改写文法为LL(1)文法。因为S→SbA|aA有左递归，故将其改写为S→aA{bA}文法变为S→aA{bA}B→SbA→Bc这样的文法满足LL(1)文法的条件。(2)文法每一个非终结符号的FIRST集合为FIRST(S)={a}FIRST(A)={a}FIRST(B)={a}文法每一个非终结符号的FOLLOW集合为因为S为开始符号，且有产生式S→aA{bA}和B→Sb所以FOLLOW(S)={#}∪FIRST(b)={#，b}因为S→aA{bA}所以FOLLOW(A)=FOLLOW{S}∪FIRST(bA)={#，b}因为A→Bc所以FOLLOW(B)=FIRST{c}={c}(3)构造相应的LL(1)分析表因为FIRST(aA{bA})={a}所以M[S,a]=“S→aA{bA}”因为FIRST(A)={a}所以M[A,a]=“A→Bc”因为FIRST(B)={a}所以M[B,a]=“B→Sb”文法G[S]的分析表如下表所示(空白处是ERROR)。abc#SS→aA{bA}AA→BcBB→Sb文法G[S]的分析表5.6解：首先将文法压缩，得到S→aABbcd|A→ASd|B→SAh|eC|C→Sf|Cg|(1)求每一个非终结符号的FOLLOW集合：因为S为开始符号，且有产生式A→ASd，B→SAh，C→Sf所以FOLLOW(S)={#}∪FIRST(d)∪FIRST(Ah)∪FIRST(f)={#，d，a，h，f}因为S→aABbcd，A→ASd，B→SAh所以FOLLOW(A)=FIRST{Bbcd}∪FIRST{Sd}∪FIRST{h}={b，a，d，h，e}因为S→aABbcd所以FOLLOW(B)=FIRST{bcd}={b}因为B→eC，C→Cg所以FOLLOW(C)=FOLLOW(B)∪FIRST(g)={b，g}(2)对每一个非终结符号的产生式选择，构造FIRST集合对S：FIRST(aABbcd)={a}FIRST()={}对A：FIRST(ASd)={a，d}FIRST()={}对B：FIRST(SAh)={a，d，h}FIRST(eC)={e}FIRST()={}对C：FIRST(Sf)={a，f}FIRST(Cg)={a