蔣立源編譯原理第三版第二章習題與答案

1、第 2 章 習題2-1設有字母表Ai =a,b,c,？, A =0,1,，試回答下列問題:(1)字母表Ai上長度為2的符號串有多少個？(2)集合AA含有多少個元素？(3)列出集合Ai(AiUA2)*中的全部長度不大于3的符號串。2-2 試分別構(gòu)造產(chǎn)生下列語言的文法：(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 打頭的所有奇整數(shù)所組成的集合；( 6)所有由偶數(shù)個0 和偶數(shù)個1 所組成的符號串的集合。2-3 試描

2、述由下列文法所產(chǎn)生的語言的特點：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-產(chǎn)生式(1) A aAS|b2 cS| & A aAAZ bAc| dAe| &2-8消除下列文法中的無用產(chǎn)生式和單產(chǎn)生式(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)本文法構(gòu)成的語言集為：L(G尸(10) nabma0n|n,m >00(2) L(G)=1 n0n |n >0+,該語言特點是：產(chǎn)生的句子中，0、1個數(shù)相同，并且若干相接的1后必然緊接數(shù)量相同的連續(xù)的0o(3)本文法構(gòu)成的語言集為：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可知，該語言特點是：產(chǎn)生的句子是奇數(shù)個a。2-4 證明：因為存在句子：abc,它對應兩個最右推導：SABAbc abcSDCDcabc所以，本文法具有二義性。2-5 解：句子bbaacb的最右推導為：S AB AaSb Aacb bAacb bbAacb bbaacb上面推導中，下劃線部分為當前句型的句柄。與句子bbaacb相應的語法樹為：全部的短語為：第一個a (a)是句子bbaacb相對于非終結(jié)符 A (A)(產(chǎn)生式 Za)的短語(直接短語)；ba是句子bbaacb相對于非終結(jié)符 A的短語；bb

7、a是句子bbaacb相對于非終結(jié)符 A的短語；c是句子bbaacb相對于非終結(jié)符 S(產(chǎn)生式SHc)的短語(直接短語)；acb是句子bbaacb相對于非終結(jié)符 B的短語；bbaacb(3)是句子bbaacb相對于非終結(jié)符 S(2)的短語；注：符號的上標是為了描述方便加上去的。2-6 解：(1)因為由非終結(jié)符號 B推導不出終結(jié)符號串，因此 B是無用符號，含有B的產(chǎn)生 式B Bab,B cSB, S- aABS ZbAB都是無用產(chǎn)生式，應予以刪除。因此我們最后得到與原文法等價且不含無用符號及無用產(chǎn)生式的文法為AbCACdZcSA| cCCCHcS| c(2)因為由文法的開始符號推導不出含有非終結(jié)符

8、號C的句型，因此C是無用符號，含有C的產(chǎn)生式CHcAB|dSD|a都是無用產(chǎn)生式，也應予以刪除。因此我們最后得到與原文法等價且不含無用符號及無用產(chǎn)生式的文法為AaAB|EZdDA|eEfAeA E fA| g(3) 因為由非終結(jié)符號A,B 推導不出終結(jié)符號串，因此 A,B 是無用符號，刪除含有A,B的產(chǎn)生式 A Ba, Z cBC和B SA后得到文法 G' S:A acCH bC|d又因為由文法 G S的開始符號S推導不出含有非終結(jié)符號 C的句型，因此C是無 用符號，含有C的產(chǎn)生式CH bC|d都是無用產(chǎn)生式，也應予以刪除。因此我們最后得到與原文法等價且不含無用符號及無用產(chǎn)生式的文法G

9、 S 為S- ac2-7 解：(1)對于G,我們可得到 W=A;再按如下步驟彳#到產(chǎn)生式集P':對于產(chǎn)生式 S- aAS,將產(chǎn)生式 A aAS及 A aS放入P'對于產(chǎn)生式S-b,直接將產(chǎn)生式 S- b放入P'對于產(chǎn)生式 ZcS,將產(chǎn)生式 ZcS放入P'。SH aAS|aS| b(2)對于G我們可得到 W=A；再按如下步驟彳#到產(chǎn)生式集 P'： 對于產(chǎn)生式 S aAA,將產(chǎn)生式 A aAA及 A A a和 A a放入P'； 對于產(chǎn)生式 A bAc,將產(chǎn)生式 A bAc及A bc放入P'對于產(chǎn)生式 Z dAe,將產(chǎn)生式 Z dAe及X de

10、放入P'。于是得到消除 一產(chǎn)生式后的文法為：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然后按如下步驟得到產(chǎn)生式集P':將P中的所有非單產(chǎn)生式添加到P,中：A aB|BC A aA|c|aDbBK DBCHbB-產(chǎn)生式的右部添加到 P中:因為CC W(B),故將C的所有非單產(chǎn)生式的右部作為BHb因為BC W(D),故將B的所有非單產(chǎn)生式的右部作為D-產(chǎn)生式的右部添加到 P'中:A DB因為CC W(D),故將C的所有非單產(chǎn)生式的右部作為D-

11、產(chǎn)生式的右部添加到 P中:EKb由此得到消除單產(chǎn)生式后的文法如下:A aB|BCAK aA|c|aDbBK DB|bCKbDK b| DB因為由文法的開始符號推導不出含有非終結(jié)符號A的句型，因此A是無用符號，含有A的產(chǎn)生式 Z aA|c|aDb都是無用產(chǎn)生式，應予以刪除。于是得到消除無用產(chǎn)生式和單產(chǎn)生式后的文法如下：SH aB|BCBK DB|bCbAb| DB(2) 首先求出如下集合W(S)=S,A,B, W(A)=A,B, W(B)=B然后按如下步驟得到產(chǎn)生式集P':將P中的所有非單產(chǎn)生式添加到P,中：SHSA|SBZ (S)|( )B S|S-產(chǎn)生式的右部添加到 P中:S-產(chǎn)生式

12、的右部添加到 P中:A-產(chǎn)生式的右部添加到 P中:因為AC W(S),故將A的所有非單產(chǎn)生式的右部作為A (S)|()因為BC W(S),故將B的所有非單產(chǎn)生式的右部作為A S|因為BC W(A),故將B的所有非單產(chǎn)生式的右部作為z S|由此得到消除單產(chǎn)生式后的文法如下: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然后按如下步驟得到產(chǎn)生式集P':將P中的所有非單產(chǎn)生式添加到P,中：1 E+T T T*FFPfFP (E)|i因為T,F,P C W(E),故將T,F,P的所有非單產(chǎn)生式的右部作為E-產(chǎn)生式的右部添加到P'中：E- T*FEPfFE (E)|i因為