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

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

3、中，在用戶需要時再執行之。即先翻譯、后執行。 2. 解：一般說來，編譯程序主要由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、代碼優化程序、目標代碼生成程序、信息表管理程序、錯誤檢查處理程序組成。 3. 解：C語言的關鍵字有：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。上述關鍵字在C語言中均為保留字。 4. 解：C語言中括號有三種：，（）。其中，用于語句括號；用于數組；（）用于函數（定義與調用）及表達式運算（改變運算順序）。C語言中無END關鍵字。逗號在C語言中被視為分隔符和運算符，作為優先級最低的運算符，運算結果為逗號表達式最右側子表達式的值（如：(a,b,c,d)的值為d）。 5. 略 第二章 前后文無關文法和語言 21設有字母表A1=a,b,z，A2=0,1,9，試回答下列問題： (1) 字母表A1上長度為2的符號串有多少個? (2) 集合A1A2含有多少個元

5、素? (3) 列出集合A1 (A1A2)*中的全部長度不大于3的符號串。 22試分別構造產生下列語言的文法。 (1) anbn|n0； (2) anbmcp|n,m,p0； (3) an#bn|n0cn#dn|n0； (4) w#wr#|w0,1*，wr是將w中的符號按逆序排列所得的符號串； (5) 任何不是以0開始的所有奇整數所組成的集合； (6) 所有由偶數個0和偶數個1所組成的符號串的集合。 23試描述由下列文法所產生的語言的特點 (文法的開始符號均為S)。 (1) S10S0SaAAbAAa (2) SSSS1A0A1A0A (3) S1ASB0A1AAC BB0BCC1C0C (4)

6、 SbAdcAAGSGAa (5) SaSSSa 24設已給文法G=(VN,VT,P,S)，其中： VN=S VT=a1,a2,an, , , P=Sai|i=1,2,nSS,SSS,SSS， 試指出此文法所產生的語言。 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) 證明此文法所產生的語言為 L(G)=at(n)|n1 t(n)=ni=1i 26設已給文法G程序： 程序分程序|復合語句 分程序無標號分

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

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

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

10、eAEfAEg (3) SacSbAAcBCBSA CbCCd 214消去下列文法中的產生式。 (1) SaASSbAcSA (2) SaAAAbAcAdAeA 215消去下列文法中的無用產生式和單產生式。 (1) SaBSBCAaAAc AaDbBDBBCDB Cb (2) SSASSBABBS A(S)SAB A( ) (3) EE+TETTT*FTF FPFFPP(E)Pi第二章 習題解答 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個2.構造產生下列語言的文法 （1）anbn|n0  解：對應文法為G(S) = (S,a,b, S| aSb ,S)  （2）anbmcp|n,m,p0  解：對應文法為G(S) = (S,X,Y,a,b,c,SaS|X,XbX|Y,YcY|,S) （3）an # bn|n0cn # dn|n0  解：對應文法為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打頭的所有奇整數所組成的集合  解：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）所有偶數個0和偶數個1所組成的符號串集合  解：對應文法為 S0A|1B|e，A0S|1C B0C|1S C1A|0B3.描述語言特點 （1）S10S0SaAAbA

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

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

15、 5.2證明：略6.解：（1）最左推導：<程序>T<分程序>T<標號>：<分程序>TL：<分程序>TL：<標號>：<分程序>T L：L：<分程序>T L：L：<無標號分程序>T L：L：<分程序首部>；<復合尾部>T L：L：<分程序首部>；<說明>；<復合尾部>T L：L：begin<說明>；<說明>；<復合尾部>T L：L：begin d；<說明>；<復合尾部&

16、gt;T L：L：begin d；d；<復合尾部>T L：L：begin d；d；<語句>；<復合尾部>T L：L：begin d；d；s；<復合尾部.T L：L：begin d；d；s；<語句> endT L：L：begin d；d；s；s end最右推導：<程序>T<分程序>T<標號>：<分程序>T<標號>：<標號>：<分程序>T<標號>：<標號>：<無標號分程序>T<標號>：<標號>：<

17、分程序首部>；<復合尾部>T<標號>：<標號>：<分程序首部>；<語句>；<復合尾部>T<標號>：<標號>：<分程序首部>；<語句>；<語句>；endT<標號>：<標號>：<分程序首部>；<語句>；s；endT<標號>：<標號>：<分程序首部>；s；s；endT<標號>：<標號>：<分程序首部>；說明；s；s；endT<標號>：

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

19、acbadcd不是文法GS中的句子因為文法中的句子不可能以非終結符d結尾（3）aacbccb不是文法GS中的句子可知，aacbccb僅是文法GS的一個句型的一部分，而不是一個句子。（4）aacabcbcccaacdca不是文法GS中的句子因為終結符d后必然要跟終結符a，所以不可能出現dc這樣的句子。（5）aacabcbcccaacbca不是文法GS中的句子由（1）可知：aacb可歸約為S，由文法的產生式規則可知，終結符c后不可能跟非終結符S，所以不可能出現caacb這樣的句子。8.證明：用歸納法于n，n=1時，結論顯然成立。設n=k時，對于12.kT*b,存在i：i=1,2,.,k，iT*bi

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

21、結符時，首符號為終結符。即設：=a；=A且=aT T A=，與（1）同理，得證。10.證明：因為存在句子：abc，它對應有兩個語法樹（或最右推導）：STABTAbcTabcSTDCTDcTabc所以，本文法具有二義性。11.解：(1) STABTAaSbTAacbTbAacbTbbAacbTbbaacb上面推導中，下劃線部分為當前句型的句柄。對應的語法樹為：全部的短語：第一個a (a1)是句子bbaacb相對于非終結符A (A1) (產生式A?a）的短語（直接短語）；b1a1是句子bbaacb相對于非終結符A2的短語；b2b1a1是句子bbaacb相對于非終結符A3的短語；c是句子bbaacb

22、相對于非終結符S1（產生式S?c）的短語（直接短語）；a2cb3是句子bbaacb相對于非終結符B的短語；b2b1a1a2cb3是句子bbaacb相對于非終結符S2的短語；注：符號的下標是為了描述方便加上去的。（2）句子（b）a（a）（b）的最右推導：ST（AS）T（A（b）T（SaA）（b）T（Sa（a）（b）T（b）a（a）（b）相應的語法樹是：（3）解：iii*i+對應的語法樹略。最右推導：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.證明：充分性：當前文法下的每一符號串僅有一個句柄和一個句柄產生式T對當前符號串有唯一的最左歸約T對每一步推導都有唯一的最右推導T有唯一的語法樹。必要性：有唯一的語法樹T對每一步推導都有唯一的最右推導T對當前符號串有唯一的最左歸約T當前文法下的每一符號串僅有一個句柄和一個句柄產生式13.化簡下列各個文法（1）解：SbCACdAcSA| cCCCcS | c（2）解：SaAB | fA | gAe | dDADeABf（3）解：Sac14.消除下列文法中的產生式（1）解：SaAS | aS | bAcS（2）解：SaAA | aA | aAbAc| bc | dAe| d

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

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

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

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

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

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

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

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

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

33、; 3.20設有如下的文法G標號說明： 標號說明LABEL標號表 標號表d標號段 標號段d標號段|,標號|； 標號d標號段 其中LABEL,d,;等為終結符號。 (1) 試求出描述此文法所產生語言的正規式； (2) 構造識別此語言的具有最少狀態的DFA。     3.21求出描述習題37所給有限自動機所識別語言的正規式。     3.22分別構造識別如下正規語言的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試設計一個識別器，它識別由下列英語單詞： ONE, TWO, THREE, ， NINE， TEN， ELEVEN， TWELVE， THIRTEEN， ， NINETEEN， TWENTY， THIRTY， FORTY， ， NINETY， HUNDRED 所表示的從1到999間的任何整數 (各單詞間用空格分隔，如THREE HUNDRED FIFTY SIX)，并將它們翻譯為相應的阿拉伯數字 (如356)作為輸出。   

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

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

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

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

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

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

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

42、0|0E|1A,D0B|1C,E1C|0B(2) 最短輸入串011(3) 任意接受的四個串011,0110,0011,(4) 任意以1打頭的串.8 從略。9（2）相應的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) 以任意個(包括0)b開頭，中間有任意個（大于1）a，跟一個b,還可以有一個由a,b組成的任意字

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

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

45、于G中每一個形如Aa的產生式,將其變為SAa 12 (1)狀態矩陣是：記S=q0 B=q1 A B=q2 S A=q3 ,最小化和確定化后如圖（2）記 S=q0, A=q1,B S=q2 最小化和確定化后的狀態轉換圖如下13 （1）將具有動作的NFA確定化后，其狀態轉換圖如圖：記 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作為一個狀態，S5和S6作為一個狀態。狀態轉換圖如圖15從略。16從略。· (

46、1) r*表示的正規式集是,r,rr,rrr, (|r)*表示的正規式集是, ,r,rr,rrr,=,r,rr,rrr,|rr*表示的正規式集是,r,rr,rrr,(r*)*=r*=,r,rr,rrr,所以四者是等價的。(2)（rs）*r表示的正規式集是,rs,rsrs,rsrsrs,r =r,rsr,rsrsr,rsrsrsr,r(sr)* 表示的正規式集是r,sr,srsr,srsrsr, = r,rsr,rsrsr,rsrsrsr,所以兩者等價。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· 識別此語言的正規式是S=LABELd(d|,d)*; · 從略。 21 從略。22 構造NFA其余從略。 23 下面舉一個能夠識別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表示的正規集是長度為2n任意a和b組成的字符串。· 此正規式的長度是2n · 用來識別Dn的DFA至多需要2n1個狀態。 25 從略。26（1）由括住的,中間由任意個非組成的字符串, 如,a,defg等等。（2）匹配一行僅由一個大寫字母和一個數字組成的串，如A1,F8,Z2等。（3）識別rn和除數字字符外的任何字符。· 由和括住的，中間由兩個或者非和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設已給文法： SAbBSd ACAbABf BCSdBd CedCa 試寫出對符號串eddfbbd進行帶回溯的自頂向下語法分析的過程。 4.3對于如下的文法，用某種高級語言寫出遞歸下降分析程序。 (1) Pbegin d; X end Xd;X XsY Y;sY Y (2) 程序begin語句end 語句賦值語句|條件語句 賦值語句變量=表達式 條件語句if表達式then語句 表達式變量 表達式表達式+變量 變量i 4.4對于如下的文法，求出各個FIRST集和FOLLOW集。 SaABSbA SAaAb ABbB B 4.

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