哈工大編譯原理習(xí)題及答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 1.1何謂源程序、目標(biāo)程序、翻譯程序、編譯程序和解釋程序?它們之間可能有何種關(guān)系?   1.2一個(gè)典型的編譯系統(tǒng)通常由哪些部分組成?各部分的主要功能是什么?   1.3選擇一種你所熟悉的程序設(shè)計(jì)語言，試列出此語言中的全部關(guān)鍵字，并通過上機(jī)使用該語言以判明這些關(guān)鍵字是否為保留字。   1.4選取一種你所熟悉的語言，試對(duì)它進(jìn)行分析，以找出此語言中的括號(hào)、關(guān)鍵字END以及逗號(hào)有多少種不同的用途。   1.5試用你常用的一種高級(jí)語言編寫一短小的程序，上機(jī)進(jìn)行編譯和運(yùn)行，記錄下操作步驟和

2、輸出信息，如果可能，請(qǐng)卸出中間代碼和目標(biāo)代碼。第一章 習(xí)題解答1. 解：源程序是指以某種程序設(shè)計(jì)語言所編寫的程序。目標(biāo)程序是指編譯程序（或解釋程序）將源程序處理加工而得的另一種語言（目標(biāo)語言）的程序。翻譯程序是將某種語言翻譯成另一種語言的程序的統(tǒng)稱。編譯程序與解釋程序均為翻譯程序，但二者工作方法不同。解釋程序的特點(diǎn)是并不先將高級(jí)語言程序全部翻譯成機(jī)器代碼，而是每讀入一條高級(jí)語言程序語句，就用解釋程序?qū)⑵浞g成一段機(jī)器指令并執(zhí)行之，然后再讀入下一條語句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。即邊解釋邊執(zhí)行，翻譯所得的指令序列并不保存。編譯程序的特點(diǎn)是先將高級(jí)語言程序翻譯成機(jī)器語言程序，將其保存到指定的空間

3、中，在用戶需要時(shí)再執(zhí)行之。即先翻譯、后執(zhí)行。 2. 解：一般說來，編譯程序主要由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、信息表管理程序、錯(cuò)誤檢查處理程序組成。 3. 解：C語言的關(guān)鍵字有：auto  break  case char const   continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch t

4、ypedef union unsigned void volatile while。上述關(guān)鍵字在C語言中均為保留字。 4. 解：C語言中括號(hào)有三種：，（）。其中，用于語句括號(hào)；用于數(shù)組；（）用于函數(shù)（定義與調(diào)用）及表達(dá)式運(yùn)算（改變運(yùn)算順序）。C語言中無END關(guān)鍵字。逗號(hào)在C語言中被視為分隔符和運(yùn)算符，作為優(yōu)先級(jí)最低的運(yùn)算符，運(yùn)算結(jié)果為逗號(hào)表達(dá)式最右側(cè)子表達(dá)式的值（如：(a,b,c,d)的值為d）。 5. 略 第二章 前后文無關(guān)文法和語言 21設(shè)有字母表A1=a,b,z，A2=0,1,9，試回答下列問題： (1) 字母表A1上長度為2的符號(hào)串有多少個(gè)? (2) 集合A1A2含有多少個(gè)元

5、素? (3) 列出集合A1 (A1A2)*中的全部長度不大于3的符號(hào)串。 22試分別構(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中的符號(hào)按逆序排列所得的符號(hào)串； (5) 任何不是以0開始的所有奇整數(shù)所組成的集合； (6) 所有由偶數(shù)個(gè)0和偶數(shù)個(gè)1所組成的符號(hào)串的集合。 23試描述由下列文法所產(chǎn)生的語言的特點(diǎn) (文法的開始符號(hào)均為S)。 (1) S10S0SaAAbAAa (2) SSSS1A0A1A0A (3) S1ASB0A1AAC BB0BCC1C0C (4)

6、 SbAdcAAGSGAa (5) SaSSSa 24設(shè)已給文法G=(VN,VT,P,S)，其中： VN=S VT=a1,a2,an, , , P=Sai|i=1,2,nSS,SSS,SSS， 試指出此文法所產(chǎn)生的語言。 25考察文法G=(VN,VT,P,S)，其中： VN=S,A,B,C,D,E,F,G VT=a, P=SABC,CBC,CA,BAGE,BGGBF,AGAD, DBBD,DEAE,FBBF,FEEa,AA (1) 指出此文法的類型； (2) 證明此文法所產(chǎn)生的語言為 L(G)=at(n)|n1 t(n)=ni=1i 26設(shè)已給文法G程序： 程序分程序|復(fù)合語句 分程序無標(biāo)號(hào)分

7、程序|標(biāo)號(hào)：分程序 復(fù)合語句無標(biāo)號(hào)復(fù)合語句|標(biāo)號(hào)：復(fù)合語句 無標(biāo)號(hào)分程序分程序首部；復(fù)合尾部 無標(biāo)號(hào)復(fù)合語句begin復(fù)合尾部 分程序首部begin說明|分程序首部；說明 復(fù)合尾部語句end|語句；復(fù)合尾部 說明d 語句s 標(biāo)號(hào)L (1) 給出句子 L: L: begin d; d; s; s end 的最左推導(dǎo)和最右推導(dǎo)。 (2) 畫出上述句子的語法樹。 27設(shè)已給文法GS： SaAcBSBdSBaScABcAB ABaBAaBcAaBb 試檢驗(yàn)下列符號(hào)串中哪些是GS中的句子，給出這些句子的最左推導(dǎo)、最右推導(dǎo)和相應(yīng)的語法樹。 (1) aacb (2) aabacbadcd (3) aacbc

8、cb (4) aacabcbcccaacdca (5) aacabcbcccaacbca 28設(shè)G=(VN,VT,P,S)為CFG，1,2,n為V上的符號(hào)串，試證明： 若 12n* 則存在V上的符號(hào)串1,2，,n，使=12n，且有 ai*i(i=1,2,n) 29設(shè)G=(VN,VT,P,S)為CFG，和都是V上的符號(hào)串，且*，試證明：當(dāng)?shù)氖追?hào)為終結(jié)符號(hào)時(shí)，的首符號(hào)也必為終結(jié)符號(hào)；當(dāng)?shù)氖追?hào)為非終結(jié)符號(hào)時(shí)，則的首符號(hào)也必為非終結(jié)符號(hào)。 210試證明： 文法 SABSDCAaAAa BbBcBbcCcCCc DaDbDab 為二義性文法。 211對(duì)于下列的文法和相應(yīng)的句子，試指出這些句子的全部短

9、語；分別給出句子的最右推導(dǎo)，并指出各步直接推導(dǎo)所得句型的句柄。 (1) SABScAbAAaBaSbBc bbaacb (2) S(AS)S(b)A(SaA)A(a) (b) a (a) (b) (3) EET+ETTTF*TFFFPFPPEPi iii*i+ 212在自底向上的分析中，用來歸約句型句柄的產(chǎn)生式稱為句柄產(chǎn)生式。試證明： 一個(gè)文法是無二義性的，當(dāng)且僅當(dāng)此文法的每一句型至多只有一個(gè)句柄和一個(gè)句柄產(chǎn)生式。 213化簡下列各個(gè)文法。 (1) SaABSSbCACdAbABAcSA AcCCBbABBcSBCcS Cc (2) SaABSEAdDAAe BbEBfCcABCdSD CaD

10、eAEfAEg (3) SacSbAAcBCBSA CbCCd 214消去下列文法中的產(chǎn)生式。 (1) SaASSbAcSA (2) SaAAAbAcAdAeA 215消去下列文法中的無用產(chǎn)生式和單產(chǎn)生式。 (1) SaBSBCAaAAc AaDbBDBBCDB Cb (2) SSASSBABBS A(S)SAB A( ) (3) EE+TETTT*FTF FPFFPP(E)Pi第二章 習(xí)題解答 1.（1）答：26*26=676 （2）答：26*10=260 （3）答：a,b,c,.,z,a0,a1,.,a9,aa,.,az,.,zz,a00,a01,.,zzz,

11、共26+26*36+26*36*36=34658個(gè)2.構(gòu)造產(chǎn)生下列語言的文法 （1）anbn|n0  解：對(duì)應(yīng)文法為G(S) = (S,a,b, S| aSb ,S)  （2）anbmcp|n,m,p0  解：對(duì)應(yīng)文法為G(S) = (S,X,Y,a,b,c,SaS|X,XbX|Y,YcY|,S) （3）an # bn|n0cn # dn|n0  解：對(duì)應(yīng)文法為G(S) = (S,X,Y,a,b,c,d,#, SX, SY,XaXb|#,YcYd|# ,S) （4）w#wr# | w?0,1*,

12、wr是w的逆序排列  解：G(S) = (S,W,R,0,1,#, SW#, W0W0|1W1|# ,S) （5）任何不是以0打頭的所有奇整數(shù)所組成的集合  解：G(S) = (S,A,B,I,J,-,0,1,2,3,4,5,6,7,8,9,SJ|IBJ,B0B|IB|e, IJ|2|4|6|8, Jà1|3|5|7|9,S) （6）所有偶數(shù)個(gè)0和偶數(shù)個(gè)1所組成的符號(hào)串集合  解：對(duì)應(yīng)文法為 S0A|1B|e，A0S|1C B0C|1S C1A|0B3.描述語言特點(diǎn) （1）S10S0SaAAbA

13、Aa  解：本文法構(gòu)成的語言集為：L(G)=(10)nabma0n|n, m0。 （2）SSS S1A0A1A0A  解：L(G)=1n10n11n20n2 1nm0nm |n1,n2,nm0；且n1,n2,nm不全為零該語言特點(diǎn)是：產(chǎn)生的句子中，0、1個(gè)數(shù)相同，并且若干相接的1后必然緊接數(shù)量相同連續(xù)的0。 （3）S1ASB0A1AACBB0BCC1C0C  解：本文法構(gòu)成的語言集為：L(G)=1p1n0n|p1,n01n0n0q|q1,n0，特點(diǎn)是具有1p1n0n 或1n0n0q形式，進(jìn)一步，可知其具有形式1n0

14、mn,m0,且n+m>0。 （4）SbAdcAAGSGAa  解：可知，S=>=>baSndc n0  該語言特點(diǎn)是：產(chǎn)生的句子中，是以ba開頭dc結(jié)尾的串,且ba、dc個(gè)數(shù)相同。 （5）SaSSSa  解：L(G)=a(2n-1)|n1可知：奇數(shù)個(gè)a4.解：此文法產(chǎn)生的語言是：以終結(jié)符a1 、a2 an 為運(yùn)算對(duì)象，以、為運(yùn)算符，以、為分隔符的布爾表達(dá)式串5.   5.1解：由于此文法包含以下規(guī)則：AAe，所以此文法是0型文法。    

15、 5.2證明：略6.解：（1）最左推導(dǎo)：<程序>T<分程序>T<標(biāo)號(hào)>：<分程序>TL：<分程序>TL：<標(biāo)號(hào)>：<分程序>T L：L：<分程序>T L：L：<無標(biāo)號(hào)分程序>T L：L：<分程序首部>；<復(fù)合尾部>T L：L：<分程序首部>；<說明>；<復(fù)合尾部>T L：L：begin<說明>；<說明>；<復(fù)合尾部>T L：L：begin d；<說明>；<復(fù)合尾部&

16、gt;T L：L：begin d；d；<復(fù)合尾部>T L：L：begin d；d；<語句>；<復(fù)合尾部>T L：L：begin d；d；s；<復(fù)合尾部.T L：L：begin d；d；s；<語句> endT L：L：begin d；d；s；s end最右推導(dǎo)：<程序>T<分程序>T<標(biāo)號(hào)>：<分程序>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<無標(biāo)號(hào)分程序>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<

17、分程序首部>；<復(fù)合尾部>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語句>；<復(fù)合尾部>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語句>；<語句>；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語句>；s；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；s；s；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；說明；s；s；endT<標(biāo)號(hào)>：

18、<標(biāo)號(hào)>：<分程序首部>；d；s；s；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：begin 說明；d；s；s；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：begin d；d；s；s；endT<標(biāo)號(hào)>： L：begin d；d；s；s；endTL：L：begin d；d；s；s；end（2）句子L：L：begin d；d；s；s end的相應(yīng)語法樹是：7.解：aacb是文法GS中的句子，相應(yīng)語法樹是：最右推導(dǎo)：S=>aAcB=>aAcb=>aacb最左推導(dǎo)：S=>aAcB=>aacB=>aacb（2）aab

19、acbadcd不是文法GS中的句子因?yàn)槲姆ㄖ械木渥硬豢赡芤苑墙K結(jié)符d結(jié)尾（3）aacbccb不是文法GS中的句子可知，aacbccb僅是文法GS的一個(gè)句型的一部分，而不是一個(gè)句子。（4）aacabcbcccaacdca不是文法GS中的句子因?yàn)榻K結(jié)符d后必然要跟終結(jié)符a，所以不可能出現(xiàn)dc這樣的句子。（5）aacabcbcccaacbca不是文法GS中的句子由（1）可知：aacb可歸約為S，由文法的產(chǎn)生式規(guī)則可知，終結(jié)符c后不可能跟非終結(jié)符S，所以不可能出現(xiàn)caacb這樣的句子。8.證明：用歸納法于n，n=1時(shí)，結(jié)論顯然成立。設(shè)n=k時(shí)，對(duì)于12.kT*b,存在i：i=1,2,.,k，iT*bi

20、成立，現(xiàn)在設(shè)12. kk+1T*b，因文法是前后文無關(guān)的，所以12. k可推導(dǎo)出b的一個(gè)前綴b'，k+1可推導(dǎo)出b的一個(gè)后綴=b"(不妨稱為b k+1)。由歸納假設(shè)，對(duì)于b'，存在i ：i=1,2,.,k，b'=12.k,使得iT*bi成立，另外,我們有k+1T*b"(=b k+1）。即n=k+1時(shí)亦成立。證畢。9.證明：(1)用反證法。假設(shè)首符號(hào)為終結(jié)符時(shí)，的首符號(hào)為非終結(jié)符。即設(shè)：=a；=A且 =>*。由題意可知：=aT T A=，由于文法是CFG，終結(jié)符a不可能被替換空串或非終結(jié)符，因此假設(shè)有誤。得證；（2）同（1），假設(shè)：的首符號(hào)為非終

21、結(jié)符時(shí)，首符號(hào)為終結(jié)符。即設(shè)：=a；=A且=aT T A=，與（1）同理，得證。10.證明：因?yàn)榇嬖诰渥樱篴bc，它對(duì)應(yīng)有兩個(gè)語法樹（或最右推導(dǎo)）：STABTAbcTabcSTDCTDcTabc所以，本文法具有二義性。11.解：(1) STABTAaSbTAacbTbAacbTbbAacbTbbaacb上面推導(dǎo)中，下劃線部分為當(dāng)前句型的句柄。對(duì)應(yīng)的語法樹為：全部的短語：第一個(gè)a (a1)是句子bbaacb相對(duì)于非終結(jié)符A (A1) (產(chǎn)生式A?a）的短語（直接短語）；b1a1是句子bbaacb相對(duì)于非終結(jié)符A2的短語；b2b1a1是句子bbaacb相對(duì)于非終結(jié)符A3的短語；c是句子bbaacb

22、相對(duì)于非終結(jié)符S1（產(chǎn)生式S?c）的短語（直接短語）；a2cb3是句子bbaacb相對(duì)于非終結(jié)符B的短語；b2b1a1a2cb3是句子bbaacb相對(duì)于非終結(jié)符S2的短語；注：符號(hào)的下標(biāo)是為了描述方便加上去的。（2）句子（b）a（a）（b）的最右推導(dǎo)：ST（AS）T（A（b）T（SaA）（b）T（Sa（a）（b）T（b）a（a）（b）相應(yīng)的語法樹是：（3）解：iii*i+對(duì)應(yīng)的語法樹略。最右推導(dǎo)：E TT=>F=>FPT FET FET+T FEF+T FEP+T FEi+TFTi+T FTF*i+TFTP*i+T FTi*i+TFFi*i+T FPi*i+TFii*i+T Pii

23、*i+Tiii*i+12.證明：充分性：當(dāng)前文法下的每一符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式T對(duì)當(dāng)前符號(hào)串有唯一的最左歸約T對(duì)每一步推導(dǎo)都有唯一的最右推導(dǎo)T有唯一的語法樹。必要性：有唯一的語法樹T對(duì)每一步推導(dǎo)都有唯一的最右推導(dǎo)T對(duì)當(dāng)前符號(hào)串有唯一的最左歸約T當(dāng)前文法下的每一符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式13.化簡下列各個(gè)文法（1）解：SbCACdAcSA| cCCCcS | c（2）解：SaAB | fA | gAe | dDADeABf（3）解：Sac14.消除下列文法中的產(chǎn)生式（1）解：SaAS | aS | bAcS（2）解：SaAA | aA | aAbAc| bc | dAe| d

24、e15.消除下列文法中的無用產(chǎn)生式和單產(chǎn)生式（1）消除后的產(chǎn)生式如下：SaB | BCBDB | bCbDb | DB（2）消除后的產(chǎn)生式如下：SSA | SB |（）|（S）| |SA() |（S）|SBà |S（3）消除后的產(chǎn)生式如下：EE+T | T*F | (E) | PF | iTT*F | (E) | PF | i FPF | (E) | i P(E) | i 第三章 詞法分析及詞法分析程序  3.1試用某種高級(jí)語言編寫一個(gè)FORTRAN源程序的預(yù)處理子程序，其功能是： 每調(diào)用它一次，即把源程序中的一個(gè)完整語句送入掃描緩沖區(qū)。要求刪去語句中的

25、注釋行；刪去續(xù)行標(biāo)記字符，把語句中的各行連接起來，并在語句的末端加上語句結(jié)束符。此外，還要求此程序具有組織源程序列表輸出的功能。    3.2畫出用來識(shí)別如下三個(gè)關(guān)鍵字的狀態(tài)轉(zhuǎn)移圖。 STEP STRING SWITCH    3.3假定有一個(gè)獵人帶著一只狼、一頭山羊和一棵白菜來到一條河的左岸，擬擺渡過河，而岸邊只有一條小船，其 大小僅能裝載人和其余三件東西中的一件，也就是說，每一次獵人只能將隨行者中的一件帶到彼岸。若獵人將狼和山羊留在同一岸上而無人照管，那么，狼就會(huì)將羊吃掉；如果獵人把山羊和白菜留在同一岸，山羊也

26、會(huì)把白菜吃掉。現(xiàn)在，請(qǐng)你用狀態(tài)轉(zhuǎn)換圖作為工具，描述獵人可能采取的種種擺渡方案，并從中找出可將上述三件東西安全地帶到右岸的方案來。    3.4設(shè)已給文法G=(VN,VT,P,S)，其中，P僅含形如 ABAV*T，BVN 的產(chǎn)生式，試證明： 由此種文法所產(chǎn)生的語言是一正規(guī)語言。     3.5試證明： 任何有限個(gè)符號(hào)串所組成的集合 L=x1,x3,xnxi+ 都是3型語言。    3.6試構(gòu)造一右線性文法，使得它與如下的文法等價(jià) SABAUTUa|aU Tb|bTBc|cB 并

27、根據(jù)所得的右線性文法，構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。     3.7對(duì)于如題圖37所示的狀態(tài)轉(zhuǎn)換圖 (1) 寫出相應(yīng)的右線性文法； (2) 指出它接受的最短輸入串； (3) 任意列出它接受的另外四個(gè)輸入串； (4) 任意列出它拒絕接受的四個(gè)輸入串。 題圖37    3.8對(duì)于有限自動(dòng)機(jī) M=(K,f,S0,Z) 其中，K=S0,S1,S2,S3,S4,S5,=a,b,Z=S1,S4,S5。 f由如下的狀態(tài)轉(zhuǎn)移矩陣給出： abS0S2S1S1S3S1S2S0S4S3S0S0S4S5S4S5S4S0 試找出一個(gè)長度最小的輸入

28、串，使得： (1) 在識(shí)別此輸入串的過程中，每一狀態(tài)至少經(jīng)歷一次； (2) 每一狀態(tài)轉(zhuǎn)換至少經(jīng)歷一次。     3.9對(duì)于下列的狀態(tài)轉(zhuǎn)換矩陣： abSASAABBBB(i) 初態(tài)：S 終態(tài)：BabSABABABBB(ii) 初態(tài)：S 終態(tài)：AabSABACABBCCCC(iii) 初態(tài)：S 終態(tài)：A,CabSASACBBBCCCC(iv) 初態(tài)：S 終態(tài)：C (1) 分別畫出相應(yīng)的狀態(tài)轉(zhuǎn)換圖； (2) 寫出相應(yīng)的3型文法； (3) 用自然語言分別描述它們所識(shí)別的輸入串的特征。     3.10對(duì)于下面所給的文法：

29、G1=(S,A,B,C,D, a,b,c,d,P1,S) P1由如下產(chǎn)生式組成： SaASBAabS AbBBbBcC CDDdDbB 以及G2=(S,A,B,C,D,a,b,c,d,P2,S) P2由如下產(chǎn)生式組成： SAaSBACc ABbBBbBa CDCBabDd (1) 試分別對(duì)G1和G2構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)換圖 (提示：對(duì)于右線性文法，可將形如CD的產(chǎn)生式視為CD；而對(duì)左線性文法，則可將它視為CD)。 (2) 對(duì)于G1，構(gòu)造一等價(jià)的左線性文法G1；對(duì)于G2構(gòu)造一等價(jià)的右線性文法G2。 (3) 對(duì)于G1和G1，分別給出如下符號(hào)串的推導(dǎo)序列： abbaababbbcdcbb 對(duì)于G2和G2

30、分別給出如下符號(hào)串的推導(dǎo)序列： aabaaabcadca (4) 試給出若干個(gè)不能由G1或G2產(chǎn)生的符號(hào)串，并驗(yàn)證它們同樣不能用G1和G2產(chǎn)生。     3.11分別構(gòu)造將左線性文法轉(zhuǎn)換為右線性文法以及將右線性文法轉(zhuǎn)換為左線性文法的算法。     3.12將如題圖312所示的NFA確定化和最小化。 題圖312     3.13將如題圖313所示的具有動(dòng)作的NFA確定化。 題圖313     3.14將如題圖314所示的有限自動(dòng)機(jī)最小化。

31、     3.15試用一種高級(jí)語言分別寫出將NFA確定化以及將DFA最小化的算法。     3.16構(gòu)造一產(chǎn)生FORTRAN語言COMMON語句的3型文法 (假定分別用和代表標(biāo)識(shí)符和整常數(shù)，它們都是終結(jié)符號(hào)，且假定數(shù)組的維數(shù)不加限定)，構(gòu)造相應(yīng)的DFA，并寫出描述COMMON語句的正規(guī)式。     3.17設(shè)r,s等為任意的正規(guī)式，試證明下列的關(guān)系式成立： (1) r*=(|r)*=|rr*=(r*)* (2) (rs)*r=r(sr)* (3) (r|s)*=(r*s*)*

32、=(r*|s*)*     3.18對(duì)于解習(xí)題36所得的文法，試用正規(guī)式描述它所產(chǎn)生的語言。 abS0S1S5S1S2S7S2S3S5S3S5S7S4S5S5S5S3S1S6S3S0S7S0S1S8S3S8(1) 初態(tài)：S0 終態(tài)：S1，S2，S6，S7abS0S5S2S1S6S2S2S0S4S3S3S5S4S6S2S5S3S0S6S3S1(2) 初態(tài)：S0 終態(tài)：S4,S5,S6題圖314     3.19對(duì)于習(xí)題310所給的文法G1和G2，試分別用正規(guī)式描述它們所產(chǎn)生的語言。    

33、; 3.20設(shè)有如下的文法G標(biāo)號(hào)說明： 標(biāo)號(hào)說明LABEL標(biāo)號(hào)表 標(biāo)號(hào)表d標(biāo)號(hào)段 標(biāo)號(hào)段d標(biāo)號(hào)段|,標(biāo)號(hào)|； 標(biāo)號(hào)d標(biāo)號(hào)段 其中LABEL,d,;等為終結(jié)符號(hào)。 (1) 試求出描述此文法所產(chǎn)生語言的正規(guī)式； (2) 構(gòu)造識(shí)別此語言的具有最少狀態(tài)的DFA。     3.21求出描述習(xí)題37所給有限自動(dòng)機(jī)所識(shí)別語言的正規(guī)式。     3.22分別構(gòu)造識(shí)別如下正規(guī)語言的DFA： (1) (0*|1)(1*0)* (2) (b|a(aa*b)*b)* (3) a(abab*|a(bab)*a)*b (4) (b|

34、aa|ac|aaa|aac)* (5) a(a|b)*b(a|b)*a(a|b)*b(a|b)*     3.23試設(shè)計(jì)一個(gè)識(shí)別器，它識(shí)別由下列英語單詞： ONE, TWO, THREE, ， NINE， TEN， ELEVEN， TWELVE， THIRTEEN， ， NINETEEN， TWENTY， THIRTY， FORTY， ， NINETY， HUNDRED 所表示的從1到999間的任何整數(shù) (各單詞間用空格分隔，如THREE HUNDRED FIFTY SIX)，并將它們翻譯為相應(yīng)的阿拉伯?dāng)?shù)字 (如356)作為輸出。   

35、;  3.24設(shè)有輔助定義式 D0=a|b D1=D0D0 D2=D1D1 Dn=Dn-1Dn-1 試回答如下問題： (1) 由Dn所表述的正規(guī)集是什么? (2) 如果將Dn中所出現(xiàn)的Dn-1用前面已定義的輔助定義式反復(fù)進(jìn)行替換，則可最終將Dn化為=a,b上的正規(guī)式，此正規(guī)式有多長? (3) 用來識(shí)別Dn的DFA至多需要幾個(gè)狀態(tài)?     3.25試將LEX中的“動(dòng)作子程序”Ai的功能加以擴(kuò)充，使之可用來生成文本編輯程序。     3.26指出下列LEX正規(guī)式所匹配的字符串： (1) "

36、;" *"" (2) a-zA-Z0-9$ (3) 0-9|rn (4) (n|)+ (5) "("n|"n)*"     3.27寫出一個(gè)LEX正規(guī)式，它能匹配C語言的所有無符號(hào)整數(shù) (例如：OX89ab，0123，45，Z,t,xab,012,等等)。     3.28寫出一個(gè)LEX正規(guī)式，它能匹配C語言的標(biāo)識(shí)符。     3.29編寫一個(gè)LEX源程序，它將一個(gè)正文文件中的全部小寫字母均換為大寫字母，并

37、將其中的制表字符、空白字符序列均用單個(gè)空格字符進(jìn)行替換 (提示： 在語義動(dòng)作中使用全程變量yytext)。     3.30編寫一個(gè)LEX源程序，它能統(tǒng)計(jì)一個(gè)PASCAL程序中所含用戶定義之標(biāo)識(shí)符個(gè)數(shù)，并能找出最長標(biāo)識(shí)符中的字符個(gè)數(shù) (提示： 使用全程變量yytext及yyleng)。 上 機(jī) 實(shí) 習(xí) 題 對(duì)于如下文法所定義的PASCAL語言子集，試編寫并上機(jī)調(diào)試一個(gè)詞法分析程序： 程序變量說明BEGIN語句表END. 變量說明VAR變量表：類型；|空 變量表變量表，變量|變量 類型INTEGER 語句表語句表；語句|語句 語句賦值語句|條件語句|WHI

38、LE語句|復(fù)合語句|過程定義 賦值語句變量=算術(shù)表達(dá)式 條件語句IF關(guān)系表達(dá)式THEN語句ELSE語句 WHILE語句WHILE關(guān)系表達(dá)式DO語句 復(fù)合語句BEGIN語句表END 過程定義PROCEDURE標(biāo)識(shí)符參數(shù)表； BEGIN語句表END 參數(shù)表(標(biāo)識(shí)符表)|空 標(biāo)識(shí)符表標(biāo)識(shí)符表，標(biāo)識(shí)符|標(biāo)識(shí)符 算術(shù)表達(dá)式算術(shù)表達(dá)式+項(xiàng)|項(xiàng) 項(xiàng)項(xiàng)*初等量|初等量 初等量(算術(shù)表達(dá)式)|變量|無符號(hào)數(shù) 關(guān)系表達(dá)式算術(shù)表達(dá)式關(guān)系符算術(shù)表達(dá)式 變量標(biāo)識(shí)符 標(biāo)識(shí)符標(biāo)識(shí)符字母|標(biāo)識(shí)符數(shù)學(xué)|字母 無符號(hào)數(shù)無符號(hào)數(shù)數(shù)字|數(shù)字 關(guān)系符=|=|=| 字母A|B|C|X|Y|Z 數(shù)字0|1|2|8|9 空 要求和提示： (

39、1) 單詞的分類。 可將所有標(biāo)識(shí)符歸為一類；將常數(shù)歸為另一類；保留字和分隔符則可采取一詞一類。 (2) 符號(hào)表的建立。 可事先建立一保留字表，以備在識(shí)別保留字時(shí)進(jìn)行查詢。變量名表及常數(shù)表則在詞法分析過程中建立。 (3) 單詞串的輸出形式。 所輸出的每一單詞，均按形如 (CLASS，VALUE) 的二元式編碼。對(duì)于變量標(biāo)識(shí)符和常數(shù)，CLASS字段為相應(yīng)的類別碼，VALUE字段則是該標(biāo)識(shí)符、常數(shù)在其符號(hào)表中登記項(xiàng)的序號(hào) (要求在變量名表登記項(xiàng)中存放該標(biāo)識(shí)符的字符串，其最大長度為四個(gè)字符；常數(shù)表登記項(xiàng)中則存放該整數(shù)的二進(jìn)制形式)。對(duì)于保留字和分隔號(hào)，由于采用一詞一類的編碼方式，所以僅需在二元式的CL

40、ASS字段上放置相應(yīng)的單詞的類別碼，VALUE字段則為“空”。不過，為便于查看由詞法分析程序所輸出的單詞串，也可以在CLASS字段上直接放置單詞符號(hào)串本身。 (4) 可以仿照程序34的結(jié)構(gòu)來編寫上述詞法分析程序，但其中的若干語義過程有待于具體編寫。 (5) 寫出它的LEX源程序，并上機(jī)進(jìn)行處理。第三章 習(xí)題解答 1從略23 假設(shè)W:表示載狐貍過河，G:表示載山羊過河，C:表示載白菜過河用到的狀態(tài)1：狐貍和山羊在左岸2：狐貍和白菜載左岸3:羊和白菜在左岸 4:狐貍和山羊在右岸5:狐貍和白菜在右岸 6:山羊和白菜在右岸F:全在右岸4 證明：只須證明文法G:AB 或A （A,BVN, VT

41、+）等價(jià)于G1:AaB 或Aa (aVT+)· G1的產(chǎn)生式中 AaB, 則B也有BbC ,CcD . 所以有 A abcB,a,b,cVT,BVN所以與G等價(jià)。2）G的產(chǎn)生式AB，VT+，因?yàn)槭亲址?，所以肯定存在著一個(gè)終結(jié)符a， 使AaB可見兩者等價(jià)，所以由此文法產(chǎn)生的語言是正規(guī)語言。5 6 根據(jù)文法知其產(chǎn)生的語言是L=ambnci| m,n,i1可以構(gòu)造如下的文法VN=S,A,B,C, VT=a,b,cP= S aA, AaA, AbB, BbB, BcC, CcC, Cc其狀態(tài)轉(zhuǎn)換圖如下:7 (1) 其對(duì)應(yīng)的右線性文法是:A 0D, B0A,B1C,C1|1F,C1|0A,F

42、0|0E|1A,D0B|1C,E1C|0B(2) 最短輸入串011(3) 任意接受的四個(gè)串011,0110,0011,(4) 任意以1打頭的串.8 從略。9（2）相應(yīng)的3型文法(i) S aASbS AaA AbB Ba|aB Bb|bB(ii) SaA|a SbB BaB | bB AaB Ab|bA(iii) SaA SbB AbA AaC BaB BbC Ca|aC Cb|bC(iv) SbS SaA AaC AbB BaB BbC Ca|aC Cb|bC（3）用自然語言描述輸入串的特征(i) 以任意個(gè)(包括0)b開頭，中間有任意個(gè)（大于1）a，跟一個(gè)b,還可以有一個(gè)由a,b組成的任意字

43、符串(ii) 以a打頭，后跟任意個(gè)（包括0）b(iii)以a打頭，中間有任意個(gè)（包括0）b,再跟a,最后由一個(gè)a,b所組成的任意串結(jié)尾或者以b打頭，中間有任意個(gè)（包括0）a,再跟b,最后由一個(gè)a,b所組成的任意串結(jié)尾(iv)以任意個(gè)（包括0）b開頭,中間跟aa最后由一個(gè)a,b所組成的任意串結(jié)尾或者以任意個(gè)（包括0）b開頭，中間跟ab后再接任意（包括0）a再接b，最后由一個(gè)a,b所組成的任意串結(jié)尾10 （1）G1的狀態(tài)轉(zhuǎn)換圖：G2的狀態(tài)轉(zhuǎn)換圖：(2) G1等價(jià)的左線性文法：SBb,SDd,DC,BDb,CBc,BAb,B,AaG2等價(jià)的右線性文法：SdD,SaB,DC,BabC,BbB,BbA,

44、B,CcA,Aa（3）對(duì)G1文法,abb的推導(dǎo)序列是：S=>aA=>abB=>abb對(duì)G1文法，abb的推導(dǎo)序列是：S=>Bb=>Abb=>abb對(duì)G2文法，aabca的推導(dǎo)序列是：S=>Aa=>Cca=>Babca=>aabca對(duì)G2文法，aabca的推導(dǎo)序列是：S=>aB=>aabC=>aabcA=>aabca（4）對(duì)串a(chǎn)cbd來說，G1,G1文法都不能產(chǎn)生。11將右線性文法化為左線性文法的算法：o （1）對(duì)于G中每一個(gè)形如AaB的產(chǎn)生式且A是開始符，將其變?yōu)锽a,否則若A不是開始符，BAa; o （2）對(duì)

45、于G中每一個(gè)形如Aa的產(chǎn)生式,將其變?yōu)镾Aa 12 (1)狀態(tài)矩陣是：記S=q0 B=q1 A B=q2 S A=q3 ,最小化和確定化后如圖（2）記 S=q0, A=q1,B S=q2 最小化和確定化后的狀態(tài)轉(zhuǎn)換圖如下13 （1）將具有動(dòng)作的NFA確定化后，其狀態(tài)轉(zhuǎn)換圖如圖：記 S0,S1,S3=q0 S1=q1 S2 S3=q2 S3=q3 (2) 記S=q0 Z=q1 U R=q2 S X=q3 Y U R=q4 X S U=q5 Y U R Z=q6 Z S=q714（1）從略(2)化簡后S0和S1作為一個(gè)狀態(tài)，S5和S6作為一個(gè)狀態(tài)。狀態(tài)轉(zhuǎn)換圖如圖15從略。16從略。· (

46、1) r*表示的正規(guī)式集是,r,rr,rrr, (|r)*表示的正規(guī)式集是, ,r,rr,rrr,=,r,rr,rrr,|rr*表示的正規(guī)式集是,r,rr,rrr,(r*)*=r*=,r,rr,rrr,所以四者是等價(jià)的。(2)（rs）*r表示的正規(guī)式集是,rs,rsrs,rsrsrs,r =r,rsr,rsrsr,rsrsrsr,r(sr)* 表示的正規(guī)式集是r,sr,srsr,srsrsr, = r,rsr,rsrsr,rsrsrsr,所以兩者等價(jià)。18 寫成方程組S=aT+aS(1)B=cB+c(2)T=bT+bB(3)所以B=c*cT=b*bc*cS=a*ab*bc*c· G1

47、: S=aA+B(1) B=cC+b(2)A=abS+bB (3)C=D(4)D=bB+d(5)把（4）（5）代入（2），得Bc(bB+d)+b=cbB+cd+b 得B=(cb)*(cd|b),代入（3）得A=abS+b(cb)*(cd|b)把它打入（1）得S=a(abS+b(cb)*(cd|b)+ (cb)*(cd|b)=aabS+ab(cb)*(cd|b) + (cb)*(cd|b)=(aab)*( ab(cb)*(cd|b)| (cb)*(cd|b)G2:S=Aa+B (1)A=Cc+Bb (2)B=Bb+a(3)C=D+Bab(4)D=d(5)可得 D=dB=ab*C=ab*ab|bA

48、=(ab*ab|b)c + ab*bS=(ab*ab|b)ca+ab*ba +ab*=(ab*ab|b)ca| ab*ba| ab*20· 識(shí)別此語言的正規(guī)式是S=LABELd(d|,d)*; · 從略。 21 從略。22 構(gòu)造NFA其余從略。 23 下面舉一個(gè)能夠識(shí)別1,2,3,10,20,100的例子，讀者可以推而廣之。%#include <stdio.h>#include <string.h>#include <ctype.h>#define ON1#define TW 2#define THRE 3#define TE 10#de

49、fine TWENT 20#define HUNDRE 100#define WHITE9999%upperA-Z%ONEreturn ON;TWOreturn TW;THREEreturn THRE;TENreturn TE;TWENTYreturn TWENT;HUNDREDreturn HUNDRE;" "+|treturn WHITE;nreturn0;%main(int argc,char *argv)int c,i=0;char tmp30;if (argc=2)if (yyin=fopen(argv1,"r")=NULL)printf(&q

50、uot;can't open %sn",argv1);exit(0);while (c=yylex()!=0)switch(c)case ON:c=yylex();if (c=0) goto i+=1;label;c=yylex();if (c=HUNDRE)i+=100;else i+=1;break;case TW:c=yylex();c=yylex();if (c=HUNDRE)i+=200;else i+=2;break;case TWENT: i+=20;break;case TE:i+=10;break;default:break;/*while*/label:

51、printf("%dn",i);return;24 （1）Dn表示的正規(guī)集是長度為2n任意a和b組成的字符串。· 此正規(guī)式的長度是2n · 用來識(shí)別Dn的DFA至多需要2n1個(gè)狀態(tài)。 25 從略。26（1）由括住的,中間由任意個(gè)非組成的字符串, 如,a,defg等等。（2）匹配一行僅由一個(gè)大寫字母和一個(gè)數(shù)字組成的串，如A1,F8,Z2等。（3）識(shí)別rn和除數(shù)字字符外的任何字符。· 由和括住的，中間由兩個(gè)或者非和n組成的任意次的字符串。如, a,bb,def，等等 27OXx0-9*a-fA-F*|0-9+|(a-zA-Z|Xx0-70-7a-f

52、A-F|0010-70-7|a-z)28a-zA-Z_+0-9*a-zA-Z_*29 參考程序如下：%#include <stdio.h>#include <string.h>#include <ctype.h>#define UPPER2#define WHITE3%upperA-Z%upper+returnUPPER;t|" "+returnWHITE;%main(int argc,char *argv)int c,i;if (argc=2)if (yyin=fopen(argv1,"r")=NULL)printf

53、("can't open %sn",argv1);exit(0); while (c=yylex()!=EOF)if (c=2)for (i=0;yytexti;i+)printf("%c",tolower(yytexti);yytext0='000'if (c=3)printf(" ");else printf("%s",yytext);return;yywrap()return ;30 從略。4.1消除下列文法的左遞歸性。 (1) SSASA ASBAB A(S)A( ) BSB (2)

54、 SASSb ASAAa (3) S(T)Sa STS TT,S 4.2設(shè)已給文法： SAbBSd ACAbABf BCSdBd CedCa 試寫出對(duì)符號(hào)串eddfbbd進(jìn)行帶回溯的自頂向下語法分析的過程。 4.3對(duì)于如下的文法，用某種高級(jí)語言寫出遞歸下降分析程序。 (1) Pbegin d; X end Xd;X XsY Y;sY Y (2) 程序begin語句end 語句賦值語句|條件語句 賦值語句變量=表達(dá)式 條件語句if表達(dá)式then語句 表達(dá)式變量 表達(dá)式表達(dá)式+變量 變量i 4.4對(duì)于如下的文法，求出各個(gè)FIRST集和FOLLOW集。 SaABSbA SAaAb ABbB B 4.

55、5試證明： 任何具有左遞歸性的前后文無關(guān)文法均非LL(1)文法。 4.6試證明： 任何LL(1)文法均為無二義性文法。 4.7驗(yàn)證下列文法是否為LL(1)文法。 (1)SABSCDa AabAc BdECeC CDfD DfEdE E (2) SaABbCDS AASdA BSAcBeC BCSf CCgC DaBDD 4.8對(duì)于如下的文法GS： SSbSAb SbAAa Aa (1) 構(gòu)造一個(gè)與G等價(jià)的LL(1)文法G； (2) 對(duì)于G，構(gòu)造相應(yīng)的LL(1)分析表。 49設(shè)已給文法 SSaBSbB ASAa BAc (1) 求出各個(gè)FIRST集和FOLLOW集； (2) 將它改寫為LL(1)文法。 410將下面的文法改寫為LL(1)文法。 (1) 布爾表達(dá)式布爾表達(dá)式布爾因子 布爾表達(dá)式布爾因子 布爾因子布爾因子布爾二次量 布爾因子布爾二次量 布爾二次量布爾初等量 布爾二次量布爾初等量 布爾初等量(布爾表達(dá)式) 布爾初等量true | false (2) 習(xí)題26中所給的文法。 411設(shè)GS為LL(1)文法，A為G的非終