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

1、 2-1 設(shè)有字母表A=a,b,c,z，A=0,1,9，試回答下列問題： 2 1 (1) 字母表A上長(zhǎng)度為2的符號(hào)串有多少個(gè)？ 1(2) 集合AA含有多少個(gè)元素？ 21*中的全部長(zhǎng)度不大于3的符號(hào)串。 )列出集合A(AA(3) 211 2-2 試分別構(gòu)造產(chǎn)生下列語(yǔ)言的文法： nn|n0； b（1）apmn |n,m,p0；）abc（2nnnn |n0（3）a#bc#d|n0；r*r w的逆序排列； w#w（4）# | w0,1,w是 打頭的所有奇整數(shù)所組成的集合；）任何不是以0（5 1所組成的符號(hào)串的集合。（6）所有由偶數(shù)個(gè)0和偶數(shù)個(gè) 試描述由下列文法所產(chǎn)生的語(yǔ)言的特點(diǎn)：2-3 （1）S10S

2、0SaA AbA Aa AA1A0 S1A0（2）SSS A1ASB0 AC）S1A（3 CC1C0 BB0 BC Sa （4）SaSS 2-4 試證明文法 aDb|abAB|DC AaA|a BbBc|bc CcC|c D S 為二義性文法。 2-5 對(duì)于下列的文法 SAB|c AbA|a BaSb|c的最右推導(dǎo)，并指出各步直接推導(dǎo)所得句型的句柄；指出句子的全試給出句子bbaacb 部短語(yǔ)。 2-6 化簡(jiǎn)下列各個(gè)文法 bAB|cSB CcS|c(1) SaABS|bCACd AbAB|cSA|cCC B BbE|f SaAB(2) |E AdDA|e fA|g CcAB|dSD|a DeA

3、E bC|dS(3) ac|bA AcBC BSA C 產(chǎn)生式2-7 消除下列文法中的- (1) SaAS|b AcS| (2) SaAA AbAc|dAe| 2-8 消除下列文法中的無(wú)用產(chǎn)生式和單產(chǎn)生式 BCb DC (1) SaB|BC AaA|c|aDb BDB| B|(S)|( ) BS| |SB|A (2) SSAA (E)|iE+T|T T(3) ET*F|F FPF|P P 習(xí)題答案第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+2

4、6*36+26*36*36=34658個(gè) 解：2-2 對(duì)應(yīng)文法為G(S)=| aSb ,S) (1) XbX|Y,YcY|(2) 對(duì)應(yīng)文法為G(S)= ,S)u2192aS|X, SY,XaXb|#, G(S法應(yīng)(3)對(duì)文為b,c,d,#, SX, YcYd|# ,S) 1,#, SW#, W0W0|1W1|# ,S)(4) G(S)= , B0B|IB|u2192J|IBJ,(5) IJ|2|4|6|8, J1|3|5|7|9,S) B0C|1S，C1A|0B(6)對(duì)應(yīng)文法為 S0A|1B|，A0S|1C ， 2-3 解：nnm (1) abL(G)=(10)|n,m0。a0本文法構(gòu)成的語(yǔ)言

5、集為：+nn個(gè)數(shù)相同，并且若 |n0，該語(yǔ)言特點(diǎn)是：產(chǎn)生的句子中，(2) L(G)=100、1 干相接的1后必然緊接數(shù)量相同的連續(xù)的。0qnpnnn|q1,n0，特點(diǎn)|p1,n0本文法構(gòu)成的語(yǔ)言集為：(3) L(G)=110100mnnpnnnq 是具有1101|n,m0,且n+m0。0或0 10形式，進(jìn)一步，可知其具有形式2n-1 。|n1可知，該語(yǔ)言特點(diǎn)是：產(chǎn)生的句子是奇數(shù)個(gè)(4)由L(G)=aa 2-4 證明： ，它對(duì)應(yīng)兩個(gè)最右推導(dǎo)：因?yàn)榇嬖诰渥樱篴bc Abc S abc AB Dc S abc DC 所以，本文法具有二義性。 2-5 解： 的最右推導(dǎo)為：句子bbaacb bbAacb

6、 Aacb bbaacbS AB bAacb AaSb 上面推導(dǎo)中，下劃線部分為當(dāng)前句型的句柄。 與句子bbaacb相應(yīng)的語(yǔ)法樹為： 全部的短語(yǔ)為： (1)(1) (產(chǎn)生式Aa）的短語(yǔ)（直A a（a）是句子bbaacb相對(duì)于非終結(jié)符(A第一個(gè)接短語(yǔ)）； (1)(1)(2) 的短語(yǔ)；A相對(duì)于非終結(jié)符bbaacb是句子ab(2)(1)(1)(3)的短語(yǔ)；A b是句子bbbaacba相對(duì)于非終結(jié)符(1)（產(chǎn)生式Sc）的短語(yǔ)（直接短語(yǔ)）；相對(duì)于非終結(jié)符S c是句子bbaacb(2)(3)是句子bbaacb相對(duì)于非終結(jié)符B的短語(yǔ)；a cb(2)(1)(1)(2)(3)(2)的短語(yǔ)； bbaacba相對(duì)于

7、非終結(jié)符cbbSb是句子a注：符號(hào)的上標(biāo)是為了描述方便加上去的。 2-6 解： (1) 因?yàn)橛煞墙K結(jié)符號(hào)B推導(dǎo)不出終結(jié)符號(hào)串，因此B是無(wú)用符號(hào)，含有B的產(chǎn)生式BBab,BcSB, SaABS和AbAB都是無(wú)用產(chǎn)生式，應(yīng)予以刪除。 因此我們最后得到與原文法等價(jià)且不含無(wú)用符號(hào)及無(wú)用產(chǎn)生式的文法為 SbCACd AcSA|cCC CcS|c (2) 因?yàn)橛晌姆ǖ拈_始符號(hào)推導(dǎo)不出含有非終結(jié)符號(hào)C的句型，因此C是無(wú)用符號(hào)，含有C的產(chǎn)生式CcAB|dSD|a都是無(wú)用產(chǎn)生式，也應(yīng)予以刪除。 因此我們最后得到與原文法等價(jià)且不含無(wú)用符號(hào)及無(wú)用產(chǎn)生式的文法為 SaAB|E AdDA|e Bf DeA EfA|g

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

9、生式后的文法為： AcSb SaAS|aS| (2) 對(duì)于G，我們可得到W=A；再按如下步驟得到產(chǎn)生式集P： 對(duì)于產(chǎn)生式SaAA，將產(chǎn)生式SaAA及SAa和Sa放入P； 對(duì)于產(chǎn)生式AbAc，將產(chǎn)生式AbAc及Abc放入P； 對(duì)于產(chǎn)生式AdAe，將產(chǎn)生式AdAe及Ade放入P。 于是得到消除-產(chǎn)生式后的文法為： SaAA|aA|a AbAc|bc|dAe|de 2-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

10、 Cb 因?yàn)镃W(B)，故將C的所有非單產(chǎn)生式的右部作為B-產(chǎn)生式的右部添加到P中： Bb 因?yàn)锽W(D)，故將B的所有非單產(chǎn)生式的右部作為D-產(chǎn)生式的右部添加到P中： DDB 因?yàn)镃W(D)，故將C的所有非單產(chǎn)生式的右部作為D-產(chǎn)生式的右部添加到P中： Db 由此得到消除單產(chǎn)生式后的文法如下： SaB|BC AaA|c|aDb BDB|b Cb Db|DB 因?yàn)橛晌姆ǖ拈_始符號(hào)推導(dǎo)不出含有非終結(jié)符號(hào)A的句型，因此A是無(wú)用符號(hào)，含有A的產(chǎn)生式AaA|c|aDb都是無(wú)用產(chǎn)生式，應(yīng)予以刪除。 于是得到消除無(wú)用產(chǎn)生式和單產(chǎn)生式后的文法如下： BCSaB|BDB|b Cb Db|DB (2) 首先求出

11、如下集合 W(S)=S,A,B, W(A)=A,B, W(B)=B 然后按如下步驟得到產(chǎn)生式集P： 將P中的所有非單產(chǎn)生式添加到P中： SSA|SB A(S)|( ) BS| 因?yàn)锳W(S)，故將A的所有非單產(chǎn)生式的右部作為S-產(chǎn)生式的右部添加到P中： S(S)|( ) 因?yàn)锽W(S)，故將B的所有非單產(chǎn)生式的右部作為S-產(chǎn)生式的右部添加到P中： SS| 因?yàn)锽W(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 因?yàn)門,F,PW(E)，故將T,F,P的所有非單產(chǎn)生式的右部作為E-產(chǎn)生式的右部添加到P中： ET