蒋立源编译原理第三版第二章习题与答案

1、第 2 章 习题2-1设有字母表Ai =a,b,c,？, A =0,1,，试回答下列问题:(1)字母表Ai上长度为2的符号串有多少个？(2)集合AA含有多少个元素？(3)列出集合Ai(AiUA2)*中的全部长度不大于3的符号串。2-2 试分别构造产生下列语言的文法：(1) anbn|n >0;(2) anbmcp|n,m,p >0；(3) an#bn|n >0 U cn#dn|n >0；(4) w#W# | w C 0,1 *,wr是 w的逆序排列;( 5)任何不是以0 打头的所有奇整数所组成的集合；( 6)所有由偶数个0 和偶数个1 所组成的符号串的集合。2-3 试描

2、述由下列文法所产生的语言的特点：1)A10S0S aAZ bAAra2)A SSS 1A0Z1A0Ar 83)A1AA B0Z1AAXB- B0EFCC 1C0CH* e4)A aSSSH*a2-4 试证明文法S AB|DC A aA|a B bBc|bc C cC|c D aDb|ab 为二义性文法。2-5 对于下列的文法A AB|c A bA|a B aSb|c试给出句子bbaacb 的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。2-6 化简下列各个文法(1) SH aABS|bCACdZ bAB|cSA|cCC B bAB|cSB8cS| c(2) SHaAB|EZ

3、dDA|eB bE|fCHc AB|dSD|aAeAE fA| g(3) S-ac|bAZc BC B SACbC|d2-7消除下列文法中的e-产生式(1) A aAS|b2 cS| & A aAAZ bAc| dAe| &2-8消除下列文法中的无用产生式和单产生式(1) S aB|BC A aA|c|aDbB DB|CCHbA B(2) S-SA|SB|A AtB|(S)|( )B-S| E E+T|T T -T*F|F FPf F |P P (E)|i第2章习题答案2-1 答：(1) 26*26=676 26*10=260(3) a,b,c,.,z, a0,a1,.,a9,

4、 aa,.,az,.,zz, a00,a01,.,zzz,共有26+26*36+26*36*36=34658 个2-2 解： 对应文法为 G(S)=(S,a,b, S -e| aSb ,S)(2)对应文法为 G(S)=(S,X,Y,a,b,c,S-aS|X, X-bX|Y, YcY| £ ,S)(3)对应文法为 G(S)=(S,X,Y,a,b,c,d,#,S-X, AY,XaXb|#,AcYd|# ,S)W#, W 0W0|1W1|# ,S) G(S尸(S,W,R,0,1,#, S(5) G(S)=(S,A,B,I,J,0,1,234,5,6,7,8,9,S- J|IBJ,BK 0B

5、|IB|eI-J|2|4|6|8, J - 1|3|5|7|9,S)(6)对应文法为 S 0A|1B| e , X0S|1C , B-0C|1S,CH 1A|0B2-3 解：(1)本文法构成的语言集为：L(G尸(10) nabma0n|n,m >00(2) L(G)=1 n0n |n >0+,该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同的连续的0o(3)本文法构成的语言集为：L(G)=1 p1n0n|p >1,n >0 U 1 n0n0q|q >1,n>0,特点 是具有1p1n0n或1n0n0q形式，进一步，可知其具有形式

6、1 n0m|n,m>0,且n+m>0。(4)由L(G)=a 2n-1|n >1可知，该语言特点是：产生的句子是奇数个a。2-4 证明：因为存在句子：abc,它对应两个最右推导：SABAbc abcSDCDcabc所以，本文法具有二义性。2-5 解：句子bbaacb的最右推导为：S AB AaSb Aacb bAacb bbAacb bbaacb上面推导中，下划线部分为当前句型的句柄。与句子bbaacb相应的语法树为：全部的短语为：第一个a (a)是句子bbaacb相对于非终结符 A (A)(产生式 Za)的短语(直接短语)；ba是句子bbaacb相对于非终结符 A的短语；bb

7、a是句子bbaacb相对于非终结符 A的短语；c是句子bbaacb相对于非终结符 S(产生式SHc)的短语(直接短语)；acb是句子bbaacb相对于非终结符 B的短语；bbaacb(3)是句子bbaacb相对于非终结符 S(2)的短语；注：符号的上标是为了描述方便加上去的。2-6 解：(1)因为由非终结符号 B推导不出终结符号串，因此 B是无用符号，含有B的产生 式B Bab,B cSB, S- aABS ZbAB都是无用产生式，应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为AbCACdZcSA| cCCCHcS| c(2)因为由文法的开始符号推导不出含有非终结符

8、号C的句型，因此C是无用符号，含有C的产生式CHcAB|dSD|a都是无用产生式，也应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为AaAB|EZdDA|eEfAeA E fA| g(3) 因为由非终结符号A,B 推导不出终结符号串，因此 A,B 是无用符号，删除含有A,B的产生式 A Ba, Z cBC和B SA后得到文法 G' S:A acCH bC|d又因为由文法 G S的开始符号S推导不出含有非终结符号 C的句型，因此C是无 用符号，含有C的产生式CH bC|d都是无用产生式，也应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法G

9、 S 为S- ac2-7 解：(1)对于G,我们可得到 W=A;再按如下步骤彳#到产生式集P':对于产生式 S- aAS,将产生式 A aAS及 A aS放入P'对于产生式S-b,直接将产生式 S- b放入P'对于产生式 ZcS,将产生式 ZcS放入P'。SH aAS|aS| b(2)对于G我们可得到 W=A；再按如下步骤彳#到产生式集 P'： 对于产生式 S aAA,将产生式 A aAA及 A A a和 A a放入P'； 对于产生式 A bAc,将产生式 A bAc及A bc放入P'对于产生式 Z dAe,将产生式 Z dAe及X de

10、放入P'。于是得到消除 一产生式后的文法为：S-aAA|aA| aZbAc|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,中：A aB|BC A aA|c|aDbBK DBCHbB-产生式的右部添加到 P中:因为CC W(B),故将C的所有非单产生式的右部作为BHb因为BC W(D),故将B的所有非单产生式的右部作为D-产生式的右部添加到 P'中:A DB因为CC W(D),故将C的所有非单产生式的右部作为D-

11、产生式的右部添加到 P中:EKb由此得到消除单产生式后的文法如下:A aB|BCAK aA|c|aDbBK DB|bCKbDK b| DB因为由文法的开始符号推导不出含有非终结符号A的句型，因此A是无用符号，含有A的产生式 Z aA|c|aDb都是无用产生式，应予以删除。于是得到消除无用产生式和单产生式后的文法如下：SH aB|BCBK DB|bCbAb| DB(2) 首先求出如下集合W(S)=S,A,B, W(A)=A,B, W(B)=B然后按如下步骤得到产生式集P':将P中的所有非单产生式添加到P,中：SHSA|SBZ (S)|( )B S|S-产生式的右部添加到 P中:S-产生式

12、的右部添加到 P中:A-产生式的右部添加到 P中:因为AC W(S),故将A的所有非单产生式的右部作为A (S)|()因为BC W(S),故将B的所有非单产生式的右部作为A S|因为BC W(A),故将B的所有非单产生式的右部作为z S|由此得到消除单产生式后的文法如下:A SASB|(S)|( )|S|z (S)|( )|S|BH S|(3) 首先求出如下集合W(E)=E,T,F,P, W(T)=T,F,P, W(F)=F,P, W(P)=P然后按如下步骤得到产生式集P':将P中的所有非单产生式添加到P,中：1 E+T T T*FFPfFP (E)|i因为T,F,P C W(E),故将T,F,P的所有非单产生式的右部作为E-产生式的右部添加到P'中：E- T*FEPfFE (E)|i因为