蔣立源編譯原理第三版第二章習(xí)題與答案_第1頁(yè)
蔣立源編譯原理第三版第二章習(xí)題與答案_第2頁(yè)
蔣立源編譯原理第三版第二章習(xí)題與答案_第3頁(yè)
蔣立源編譯原理第三版第二章習(xí)題與答案_第4頁(yè)
蔣立源編譯原理第三版第二章習(xí)題與答案_第5頁(yè)
已閱讀5頁(yè),還剩2頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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 消除下列文法中的無用產(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是無用符號(hào),含有B的產(chǎn)生式BBab,BcSB, SaABS和AbAB都是無用產(chǎn)生式,應(yīng)予以刪除。 因此我們最后得到與原文法等價(jià)且不含無用符號(hào)及無用產(chǎn)生式的文法為 SbCACd AcSA|cCC CcS|c (2) 因?yàn)橛晌姆ǖ拈_始符號(hào)推導(dǎo)不出含有非終結(jié)符號(hào)C的句型,因此C是無用符號(hào),含有C的產(chǎn)生式CcAB|dSD|a都是無用產(chǎn)生式,也應(yīng)予以刪除。 因此我們最后得到與原文法等價(jià)且不含無用符號(hào)及無用產(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是無用符號(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是無用符號(hào),含有C的產(chǎn)生式CbC|d都是無用產(chǎn)生式,也應(yīng)予以刪除。 因此我們最后得到與原文法等價(jià)且不含無用符號(hào)及無用產(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是無用符號(hào),含有A的產(chǎn)生式AaA|c|aDb都是無用產(chǎn)生式,應(yīng)予以刪除。 于是得到消除無用產(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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論