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

1、蔣立源 編譯原理第三版第二章 習(xí)題與答案(修改后)第2章 習(xí)題2-1 設(shè)有字母表A1 =a,b,c,z，A2 =0,1,9，試回答下列問(wèn)題：(1) 字母表A1上長(zhǎng)度為2的符號(hào)串有多少個(gè)？ (2) 集合A1A2含有多少個(gè)元素？(3) 列出集合A1(A1A2)*中的全部長(zhǎng)度不大于3的符號(hào)串。2-2 試分別構(gòu)造產(chǎn)生下列語(yǔ)言的文法：（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ù)個(gè)0和偶數(shù)個(gè)1所組成的符號(hào)串的集合。2-3 試描述由下列文

2、法所產(chǎn)生的語(yǔ)言的特點(diǎn)：（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 對(duì)于下列的文法SAB|c AbA|a BaSb|c試給出句子bbaacb的最右推導(dǎo)，并指出各步直接推導(dǎo)所得句型的句柄；指出句子的全部短語(yǔ)。2-6 化簡(jiǎn)下列各個(gè)文法(1) SaABS|bCACd AbAB|cSA|cCC BbAB|cSB CcS|c(2) SaAB|E AdDA|e BbE|f CcAB|dS

3、D|a DeA EfA|g(3) Sac|bA AcBC BSA CbC|d2-7 消除下列文法中的-產(chǎn)生式(1) SaAS|b AcS|(2) SaAA AbAc|dAe|2-8 消除下列文法中的無(wú)用產(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+

4、26*36+26*36*36=34658個(gè)2-2 解：(1) 對(duì)應(yīng)文法為G(S)=(S,a,b, S| aSb ,S) (2) 對(duì)應(yīng)文法為G(S)=(S,X,Y,a,b,c,SaS|X, XbX|Y, YcY| ,S)(3)對(duì)應(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)對(duì)應(yīng)文法為 S

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

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

7、bbaacb相對(duì)于非終結(jié)符B的短語(yǔ)；b(2)b(1)a(1)a(2)cb(3)是句子bbaacb相對(duì)于非終結(jié)符S(2)的短語(yǔ)；注：符號(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)橛晌姆ǖ拈_(kāi)始符號(hào)推導(dǎo)不出含有非終結(jié)符號(hào)C的句型，因此C是無(wú)用符號(hào)，含有C的產(chǎn)生式CcAB|dSD|a都是無(wú)用產(chǎn)生式，也應(yīng)予以刪除。因此我們最后得到與原文法等價(jià)且

8、不含無(wú)用符號(hào)及無(wú)用產(chǎn)生式的文法為SaAB|E AdDA|e Bf DeA EfA|g(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的開(kāi)始符號(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為 Sac2-7 解：(1) 對(duì)于G，我們可得到W=A；再按如下步驟得到產(chǎn)生式集P：對(duì)于產(chǎn)生式SaAS，將產(chǎn)生式SaAS及SaS放入P；對(duì)于產(chǎn)生式Sb，直接將產(chǎn)生式

9、Sb放入P；對(duì)于產(chǎn)生式AcS，將產(chǎn)生式AcS放入P。于是得到消除-產(chǎn)生式后的文法為：SaAS|aS|b AcS(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|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中

10、：SaB|BC AaA|c|aDb BDB 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|BCAaA|c|aDbBDB|bCbDb|DB因?yàn)橛晌姆ǖ拈_(kāi)始符號(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)生式后的文法如下：SaB|BCBDB|bCbDb|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*F EP