编译原理第二章 习题与答案(修改后).doc
如有侵权，请联系网站删除，仅供学习与交流编译原理第二章 习题与答案(修改后)【精品文档】第 7 页第2章 习题2-1 设有字母表A1 =a,b,c,z，A2 =0,1,9，试回答下列问题：(1) 字母表A1上长度为2的符号串有多少个？ (2) 集合A1A2含有多少个元素？(3) 列出集合A1(A1A2)*中的全部长度不大于3的符号串。2-2 试分别构造产生下列语言的文法：（1）anbn|n0；（2）anbmcp|n,m,p0；（3）an#bn|n0cn#dn|n0；（4）w#wr# | w0,1*,wr是w的逆序排列 ；（5）任何不是以0打头的所有奇整数所组成的集合；（6）所有由偶数个0和偶数个1所组成的符号串的集合。2-3 试描述由下列文法所产生的语言的特点：（1）S10S0 SaA AbA Aa （2）SSS S1A0 A1A0 A（3）S1A SB0 A1A AC BB0 BC C1C0 C（4）SaSS Sa2-4 试证明文法 SAB|DC AaA|a BbBc|bc CcC|c DaDb|ab为二义性文法。2-5 对于下列的文法SAB|c AbA|a BaSb|c试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。2-6 化简下列各个文法(1) SaABS|bCACd AbAB|cSA|cCC BbAB|cSB CcS|c(2) SaAB|E AdDA|e BbE|f CcAB|dSD|a DeA EfA|g(3) Sac|bA AcBC BSA CbC|d2-7 消除下列文法中的-产生式(1) SaAS|b AcS|(2) SaAA AbAc|dAe|2-8 消除下列文法中的无用产生式和单产生式(1) SaB|BC AaA|c|aDb BDB|C Cb DB(2) SSA|SB|A AB|(S)|( ) BS| (3) EE+T|T TT*F|F FPF|P P(E)|i第2章 习题答案2-1 答：(1) 26*26=676(2) 26*10=260(3) a,b,c,.,z, a0,a1,.,a9, aa,.,az,.,zz, a00,a01,.,zzz,共有26+26*36+26*36*36=34658个2-2 解：(1) 对应文法为G(S)=(S,a,b, S| aSb ,S) (2) 对应文法为G(S)=(S,X,Y,a,b,c,SaS|X, XbX|Y, YcY| ,S)(3)对应文法为G(S)=(S,X,Y,a,b,c,d,#, SX, SY, XaXb|#, YcYd|# ,S)(4) G(S)=(S,W,R,0,1,#, SW#, W0W0|1W1|# ,S)(5) G(S)=(S,A,B,I,J,0,1,2,3,4,5,6,7,8,9,SJ|IBJ, B0B|IB|, IJ|2|4|6|8, J1|3|5|7|9,S)(6)对应文法为 S0A|1B|，A0S|1C ， B0C|1S， C1A|0B2-3 解：(1) 本文法构成的语言集为：L(G)=(10)nabma0n|n,m0。(2) L(G)=1n0n |n0+，该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同的连续的0。(3) 本文法构成的语言集为：L(G)=1p1n0n|p1,n01n0n0q|q1,n0，特点是具有1p1n0n 或1n0n0q形式，进一步，可知其具有形式1n0m|n,m0,且n+m>0。(4)由L(G)=a2n-1|n1可知，该语言特点是：产生的句子是奇数个a。2-4 证明：因为存在句子：abc，它对应两个最右推导：S Þ AB Þ Abc Þ abcS Þ DC Þ Dc Þ abc所以，本文法具有二义性。2-5 解：句子bbaacb的最右推导为：S Þ AB Þ AaSb Þ Aacb Þ bAacb Þ bbAacb Þ bbaacb上面推导中，下划线部分为当前句型的句柄。与句子bbaacb相应的语法树为：全部的短语为：第一个a（a(1)）是句子bbaacb相对于非终结符A (A(1) (产生式Aa）的短语（直接短语）；b(1)a(1)是句子bbaacb相对于非终结符A(2)的短语；b(2)b(1)a(1)是句子bbaacb相对于非终结符A(3)的短语；c是句子bbaacb相对于非终结符S(1)（产生式Sc）的短语（直接短语）；a(2)cb(3)是句子bbaacb相对于非终结符B的短语；b(2)b(1)a(1)a(2)cb(3)是句子bbaacb相对于非终结符S(2)的短语；注：符号的上标是为了描述方便加上去的。2-6 解：(1) 因为由非终结符号B推导不出终结符号串，因此B是无用符号，含有B的产生式BBab,BcSB, SaABS和AbAB都是无用产生式，应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为SbCACd AcSA|cCC CcS|c(2) 因为由文法的开始符号推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式CcAB|dSD|a都是无用产生式，也应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为SaAB|E AdDA|e Bf DeA EfA|g(3) 因为由非终结符号A,B推导不出终结符号串，因此A,B是无用符号，删除含有A,B的产生式SBa, AcBC和BSA后得到文法GS: Sac CbC|d又因为由文法GS的开始符号S推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式CbC|d都是无用产生式，也应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法GS为 Sac2-7 解：(1) 对于G，我们可得到W=A；再按如下步骤得到产生式集P：对于产生式SaAS，将产生式SaAS及SaS放入P；对于产生式Sb，直接将产生式Sb放入P；对于产生式AcS，将产生式AcS放入P。于是得到消除-产生式后的文法为：SaAS|aS|b AcS(2) 对于G，我们可得到W=A；再按如下步骤得到产生式集P：对于产生式SaAA，将产生式SaAA及SAa和Sa放入P；对于产生式AbAc，将产生式AbAc及Abc放入P；对于产生式AdAe，将产生式AdAe及Ade放入P。于是得到消除-产生式后的文法为：SaAA|aA|a AbAc|bc|dAe|de2-8 解：(1) 首先求出如下集合W(S)=S, W(A)=A, W(B)=B,C, W(C)=C, W(D)=D,B,C然后按如下步骤得到产生式集P：将P中的所有非单产生式添加到P中：SaB|BC AaA|c|aDb BDB Cb因为CW(B)，故将C的所有非单产生式的右部作为B-产生式的右部添加到P中：Bb因为BW(D)，故将B的所有非单产生式的右部作为D-产生式的右部添加到P中：DDB因为CW(D)，故将C的所有非单产生式的右部作为D-产生式的右部添加到P中：Db由此得到消除单产生式后的文法如下：SaB|BCAaA|c|aDbBDB|bCbDb|DB因为由文法的开始符号推导不出含有非终结符号A的句型，因此A是无用符号，含有A的产生式AaA|c|aDb都是无用产生式，应予以删除。于是得到消除无用产生式和单产生式后的文法如下：SaB|BCBDB|bCbDb|DB(2) 首先求出如下集合W(S)=S,A,B, W(A)=A,B, W(B)=B然后按如下步骤得到产生式集P：将P中的所有非单产生式添加到P中：SSA|SB A(S)|( ) BS| 因为AW(S)，故将A的所有非单产生式的右部作为S-产生式的右部添加到P中：S(S)|( ) 因为BW(S)，故将B的所有非单产生式的右部作为S-产生式的右部添加到P中：SS| 因为BW(A)，故将B的所有非单产生式的右部作为A-产生式的右部添加到P中：AS| 由此得到消除单产生式后的文法如下：SSA|SB|(S)|( )|S| A(S)|( )|S| BS| (3) 首先求出如下集合W(E)=E,T,F,P, W(T)=T,F,P, W(F)=F,P, W(P)=P然后按如下步骤得到产生式集P：将P中的所有非单产生式添加到P中：EE+T TT*F FPF P(E)|i因为T,F,PW(E)，故将T,F,P的所有非单产生式的右部作为E-产生式的右部添加到P中：ET*F EPF E(E)|i 因为F,PW(T)，故将F,P的所有非单产生式的右部作为T-产生式的右部添加到P中：TPF T(E)|i 因为PW(F)，故将P的所有非单产生式的右部作为F-产生式的右部添加到P中：F(E)|i由此得到消除单产生式后的文法如下：EE+T|T*F|PF|(E)|iTT*F|PF|(E)|i FPF|(E)|i P(E)|i
