編譯原理 習(xí)題與答案修改后

1、第2章 習(xí)題2-1 設(shè)有字母表A1 =a,b,c,z，A2 =0,1,9，試回答下列問題：(1) 字母表A1上長度為2的符號串有多少個？ (2) 集合A1A2含有多少個元素？(3) 列出集合A1(A1A2)*中的全部長度不大于3的符號串。2-2 試分別構(gòu)造產(chǎn)生下列語言的文法：（1）anbn|n0；（2）anbmcp|n,m,p0；（3）an#bn|n0cn#dn|n0；（4）w#wr# | w0,1*,wr是w的逆序排列 ；（5）任何不是以0打頭的所有奇整數(shù)所組成的集合；（6）所有由偶數(shù)個0和偶數(shù)個1所組成的符號串的集合。2-3 試描述由下列文法所產(chǎn)生的語言的特點：（1）S10S0 SaA A

2、bA 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的最右推導(dǎo)，并指出各步直接推導(dǎo)所得句型的句柄；指出句子的全部短語。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 A

3、cBC BSA CbC|d2-7 消除下列文法中的-產(chǎn)生式(1) SaAS|b AcS|(2) SaAA AbAc|dAe|2-8 消除下列文法中的無用產(chǎn)生式和單產(chǎn)生式(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章 習(xí)題答案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

4、解：(1) 對應(yīng)文法為G(S)=(S,a,b, S| aSb ,S) (2) 對應(yīng)文法為G(S)=(S,X,Y,a,b,c,SaS|X, XbX|Y, YcY| ,S)(3)對應(yīng)文法為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)對應(yīng)文法為 S0A|1B|，A0S|1C ， B0C|1S， C

5、1A|0B2-3 解：(1) 本文法構(gòu)成的語言集為：L(G)=(10)nabma0n|n,m0。(2) L(G)=1n0n |n0+，該語言特點是：產(chǎn)生的句子中，0、1個數(shù)相同，并且若干相接的1后必然緊接數(shù)量相同的連續(xù)的0。(3) 本文法構(gòu)成的語言集為：L(G)=1p1n0n|p1,n01n0n0q|q1,n0，特點是具有1p1n0n 或1n0n0q形式，進(jìn)一步，可知其具有形式1n0m|n,m0,且n+m0。(4)由L(G)=a2n-1|n1可知，該語言特點是：產(chǎn)生的句子是奇數(shù)個a。2-4 證明：因為存在句子：abc，它對應(yīng)兩個最右推導(dǎo)：S AB Abc abcS DC Dc abc所以，本文

6、法具有二義性。2-5 解：句子bbaacb的最右推導(dǎo)為：S AB AaSb Aacb bAacb bbAacb bbaacb上面推導(dǎo)中，下劃線部分為當(dāng)前句型的句柄。與句子bbaacb相應(yīng)的語法樹為：全部的短語為：第一個a（a(1)）是句子bbaacb相對于非終結(jié)符A (A(1) (產(chǎn)生式Aa）的短語（直接短語）；b(1)a(1)是句子bbaacb相對于非終結(jié)符A(2)的短語；b(2)b(1)a(1)是句子bbaacb相對于非終結(jié)符A(3)的短語；c是句子bbaacb相對于非終結(jié)符S(1)（產(chǎn)生式Sc）的短語（直接短語）；a(2)cb(3)是句子bbaacb相對于非終結(jié)符B的短語；b(2)b(1

7、)a(1)a(2)cb(3)是句子bbaacb相對于非終結(jié)符S(2)的短語；注：符號的上標(biāo)是為了描述方便加上去的。2-6 解：(1) 因為由非終結(jié)符號B推導(dǎo)不出終結(jié)符號串，因此B是無用符號，含有B的產(chǎn)生式BBab,BcSB, SaABS和AbAB都是無用產(chǎn)生式，應(yīng)予以刪除。因此我們最后得到與原文法等價且不含無用符號及無用產(chǎn)生式的文法為SbCACd AcSA|cCC CcS|c(2) 因為由文法的開始符號推導(dǎo)不出含有非終結(jié)符號C的句型，因此C是無用符號，含有C的產(chǎn)生式CcAB|dSD|a都是無用產(chǎn)生式，也應(yīng)予以刪除。因此我們最后得到與原文法等價且不含無用符號及無用產(chǎn)生式的文法為SaAB|E Ad

8、DA|e Bf DeA EfA|g(3) 因為由非終結(jié)符號A,B推導(dǎo)不出終結(jié)符號串，因此A,B是無用符號，刪除含有A,B的產(chǎn)生式SBa, AcBC和BSA后得到文法GS: Sac CbC|d又因為由文法GS的開始符號S推導(dǎo)不出含有非終結(jié)符號C的句型，因此C是無用符號，含有C的產(chǎn)生式CbC|d都是無用產(chǎn)生式，也應(yīng)予以刪除。因此我們最后得到與原文法等價且不含無用符號及無用產(chǎn)生式的文法GS為 Sac2-7 解：(1) 對于G，我們可得到W=A；再按如下步驟得到產(chǎn)生式集P：對于產(chǎn)生式SaAS，將產(chǎn)生式SaAS及SaS放入P；對于產(chǎn)生式Sb，直接將產(chǎn)生式Sb放入P；對于產(chǎn)生式AcS，將產(chǎn)生式AcS放入P

9、。于是得到消除-產(chǎn)生式后的文法為：SaAS|aS|b AcS(2) 對于G，我們可得到W=A；再按如下步驟得到產(chǎn)生式集P：對于產(chǎn)生式SaAA，將產(chǎn)生式SaAA及SAa和Sa放入P；對于產(chǎn)生式AbAc，將產(chǎn)生式AbAc及Abc放入P；對于產(chǎn)生式AdAe，將產(chǎn)生式AdAe及Ade放入P。于是得到消除-產(chǎn)生式后的文法為：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然后按如下步驟得到產(chǎn)生式集P：將P中的所有非單產(chǎn)生式添加到P中：SaB|BC AaA|c|aDb BDB Cb因

10、為CW(B)，故將C的所有非單產(chǎn)生式的右部作為B-產(chǎn)生式的右部添加到P中：Bb因為BW(D)，故將B的所有非單產(chǎn)生式的右部作為D-產(chǎn)生式的右部添加到P中：DDB因為CW(D)，故將C的所有非單產(chǎn)生式的右部作為D-產(chǎn)生式的右部添加到P中：Db由此得到消除單產(chǎn)生式后的文法如下：SaB|BCAaA|c|aDbBDB|bCbDb|DB因為由文法的開始符號推導(dǎo)不出含有非終結(jié)符號A的句型，因此A是無用符號，含有A的產(chǎn)生式AaA|c|aDb都是無用產(chǎn)生式，應(yīng)予以刪除。于是得到消除無用產(chǎn)生式和單產(chǎn)生式后的文法如下：SaB|BCBDB|bCbDb|DB(2) 首先求出如下集合W(S)=S,A,B, W(A)=A

11、,B, W(B)=B然后按如下步驟得到產(chǎn)生式集P：將P中的所有非單產(chǎn)生式添加到P中：SSA|SB A(S)|( ) BS| 因為AW(S)，故將A的所有非單產(chǎn)生式的右部作為S-產(chǎn)生式的右部添加到P中：S(S)|( ) 因為BW(S)，故將B的所有非單產(chǎn)生式的右部作為S-產(chǎn)生式的右部添加到P中：SS| 因為BW(A)，故將B的所有非單產(chǎn)生式的右部作為A-產(chǎn)生式的右部添加到P中：AS| 由此得到消除單產(chǎn)生式后的文法如下：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然后按如下步驟得到產(chǎn)生式集P：將P中的所有非單產(chǎn)生式添加到P中：EE+T TT*F FPF P(E)|i因為T,F,PW(E)，故將T,F,P的所有非單產(chǎn)生式的右部作為E-產(chǎn)生式的右部添加到P中