1、編譯原理復習題一、填空題：1、編譯方式與解釋方式的根本區別在于（ 是否生成目標代碼 ）。2、對編譯程序而言，輸入數據是（ 源程序 ），輸出結果是（ 目標程序 ）。3、如果編譯程序生成的目標程序是機器代碼程序，則源程序的執行分為兩大階段：（編譯階段 ）和（ 運行階段 ）。4、如果編譯程序生成的目標程序是匯編語言程序，則源程序的執行分成三個階段：（ 編譯階段）、（匯編階段）和（運行階段）。5、自頂向下語法分析方法會遇到的主要問題有（ 回溯 ）和（ （左遞歸帶來的）無限循環 ）。6、LL(k)分析法中，第一個L的含義是（ 從左到右進行分析 ），第二個L的含義是（ 每次進行最左推導 ），“k”的含義是

2、（向輸入串中查看K個輸入符號 ）。7、LL(1)分析法中，第一個L的含義是（從左到右進行分析 ），第二個L的含義是（每次進行最左推導 ），“1”的含義是（向輸入串中查看1個輸入符號 ）。8、自頂向下語法分析方法的基本思想是：從（識別符號）出發，不斷建立（ 直接推導 ），試圖構造一個推導序列，最終由它推導出與輸入符號相同的（ 符號串 ）。9、自底向上語法分析方法的基本思想是：從待輸入的符號串開始，利用文法的規則步步向上進行（直接歸約），試圖（歸約）到文法的（ 識別符號|開始符號 ）。10、LR(0)分析法的名字中，“L”的含義是（從左到右進行分析），“R”的含義是（ 采用最右推導的逆過程-最左歸

3、約 ），“0”的含義是（向貌似句柄的符號串后查看0個輸入符號）。11、LR(1)分析法的名字中，“L”的含義是（從左到右進行分析），“R”的含義是（采用最右推導的逆過程-最左歸約），“1”的含義是（向貌似句柄的符號串后查看1個輸入符號）。12、SLR(1)分析法的名字中，“S”的含義是（簡單的 ），“L”的含義是（從左到右進行分析），“R”的含義是（采用最右推導的逆過程-最左歸約），“1”的含義是（向貌似句柄的符號串后查看1個輸入符號）。13、在編譯過程中，常見的中間語言形式有（逆波蘭表示 ）、（三元式 ）、（四元式）和（樹形表示）。14、在編譯程序中安排中間代碼生成的目的是（便于代碼優化）和

4、（便于目標程序的移植）。15、表達式-a+b*(-c+d)的逆波蘭表示為（ a-bc-d+*+ ）。16、表達式a+b*(c+d/e)的逆波蘭表示為（abcde/+*+ ）。17、表達式a:=a+b*c(d/e)/f的逆波蘭表示為（ aabcde/*f/+:= ）。18、文法符號的屬性有（ 繼承屬性 ）和（ 綜合屬性 ）兩種。19、一個文法符號的繼承屬性是通過語法樹中它的（兄弟結點與父 ）結點的相應文法符號的屬性來計算的。20、一個文法符號的綜合屬性是通過語法樹中它的（子 ）結點的屬性來計算的。21、語法制導的編譯程序能同時進行（ 語法 ）分析和（ 語義 ）分析。22、編譯過程中掃描器所完成的

5、任務是從（ 源程序 ）中識別出一個個具有（ 獨立語法意義的單詞 ）。23、確定的有窮自動機是一個（ 五元組 ），通常表示為（ DFA=（K，M，S，Z）。24、已知文法G(E): E->T|E+T|E-T T->F|T*F|T/F F->(E)|i 該文法的開始符號是（ E ），終結符號集合VT是（ +,-,*./,(,),i ），非終結符號集合VN是（ E,T,F ），句型T+T*F+i的短語有（ T+T*F+I ，T*F第一個T，i）。25、已知文法G(E): E->T|E+T|E-T T->F|T*F|T/F F->(E)|i 改寫該文法以消除直接左遞

6、歸，改寫后的文法為：E->（+TE|-TE| ），T->（ FT ），（T-> *FT|），F->（ （E）| i ）。26、已知文法G(Z): Z->U0|V1 U->Z1|1 V->Z0|0 請寫出全部由此文法描述的只含四個符號的句子：（ 0101，1010，1001，0110 ）。 該文法是Chomsky（ 3 ）型文法。27、Chomsky定義的四種形式語言文法分別為：（ 0型）文法-又稱（短語文法 ）文法，（1型）文法-又稱（上下文有關）文法，（2型 ）文法-又稱（上下文無關 ）文法，（3型）文法-又稱（正則）文法。28、文法G(S): S-

7、>AB A->aAb|ab B->Bc|其描述的語言L(GS)=（ anbncm,n1，m0 ）。29、文法G(S): S->SAS|b|c A->aaA|a 其描述的語言L(GS)=（b,C,或者是以b開頭、以c結尾的、中間是任意個由b或c間隔開的奇數個a組成的符號串）。30、過程與過程引用中信息交換的方法是（全局變量的使用）和（參數傳遞 ）。31、形式參數和實在參數之間的對應關系通常按（它們在源程序中的位置）來確定。32、按傳結果的方式進行形實參數結合，是一種把（傳地址 ）和（傳值）的特點相結合的參數傳遞方式。33、在PASCAL中，由于允許用戶動態申請與釋放

8、內存空間，所以必須采用（ 堆 ）存儲分配方式。34、編譯程序進行數據流分析的目的是（ 為了進行全局優化 ）。35、根據所涉及程序的范圍，優化可分為（ 局部優化 ）、（ 循環優化 ）和（ 全局優化 ）三種。36、局部優化是局限于一個（ 基本塊 ）范圍內的一種優化。37、詞法分析階段的錯誤主要是（ 拼寫錯誤 ），可通過（ 最小距離匹配 ）的辦法去糾正錯誤。38、對錯誤的處理方法一般有（ 校正法 ）和（ 局部優化法 ）。39、源程序中的錯誤一般有（ 詞法錯誤 ）、（ 語法錯誤 ）、（ 語義錯誤 ）和（ 違反環境限制的錯誤 ）四種。40、翻譯程序是這樣一種程序，它能夠將（ 用甲語言書寫的程序 ）轉換成

9、與其等價的（ 用乙語言書寫的程序 ）。41、編譯程序的工作過程一般可以劃分成（ 詞法分析、語法分析、語義分析、中間代碼生成、代碼優化 ）等五個基本階段。42、編譯程序的工作過程還會伴有（ 表格處理 ）和（ 出錯處理 ）。二、選擇題：1、在使用高級語言編程時，首先可通過編譯程序發現源程序的全部（ A ）錯誤和部分（ B ）錯誤。 A、語法 B、語義 C、語用 D、運行2、程序語言的處理程序是一種（ A ）。 A、系統軟件 B、應用軟件 C、實時系統 D、分布式系統3、（ B ）是兩類程序語言處理程序，它們的主要區別在于是否生成目標代碼。 A、高級語言和低級語言 B、解釋程序和編譯程序 C、編譯程

10、序和操作系統 D、系統程序和應用程序4、匯編語言是將（ A ）翻譯成（ B ）；編譯程序是將（ C ）翻譯成（ D ）。 A、匯編語言程序 B、機器語言程序 C、高級語言程序 D、匯編或機器語言程序 e、匯編或高級語言程序 F、機器或高級語言程序5、編譯程序與具體的機器（ A ），與具體的語言（ B ）。 A、有關 B、無關6、編譯程序生成的目標程序（ B ）是可執行的程序。 A、一定 B、不一定7、編譯程序生成的目標程序（ B ）是機器語言程序。 A、一定 B、不一定8、把匯編語言程序翻譯成機器可執行的目標程序的工作是由（ B ）完成的。 A、編譯器 B、匯編器 C、解釋器 D、預處理器9、

11、編譯過程中，語法分析器的任務是（ B ）。 (1)分析單詞是怎樣構成的；(2)分析單詞串是如何構成語句和說明的；(3)分析語句和說明是如何構成程序的；(4)分析程序的結構 A、(2)(3) B、(2)(3)(4) C、(1)(2)(3) D、(1)(2)(3)(4) 10、文法G所描述的語言是（ D ）的集合 A、文法G的字母表V中所有符號組成的符號串； B、文法G的字母表V的閉包V*中的所有符號串； C、由文法的識別符號推出的所有符號串； D、由文法的識別符號推出的所有終結符符號串；11、描述語言L=ambn|n>m>1的文法為（D ）。 A、Z->Abb, A->a

12、A|a, B->bB|b B、Z->ABb, A->Aa|a,B->aBb|b C、Z->Ab, A->aAb|a D、Z->aAb, A->Ab|aAb|12、一個句型中的最左（B ）稱為該句型的句柄。 A、短語 B、簡單短語 C、素短語 D、終結符號13、文法的二義性和語言的二義性是兩個（A）的概念。 A、不同 B、相同 C、無法判斷14、上下文無關文法（ A）產生語言L=ambnci|i>1,n>1 A、可以 B、不可以15、（B）正規文法能產生下面的語言：L=ambn|n>1 A、存在一個 B、不存在任何c、無法判斷16

13、、編譯程序中的語法分析器接受以（C）為單位的輸入，并產生有關信息供以后各階段使用。 A、表達式 B、產生式C、單詞D、語句17、高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（ B ）分析方法。 A、自左至右 B、自頂向下 C、自底向上 D、自右至左18、算符優先分析法每次都是對（ E ）進行歸約，簡單優先分析法每次都是對（ C ）進行歸約。 A、最左短語 B、簡單短語 C、句柄 D、素短語 E、最左素短語19、文法G(S)：S>aTb|,，T->R，R>R/S|S的句型aR/aSb/aTb,b的最左素短語為（ B ）。 A、aTb B、aSb C、S D、R/ E

14、、,20、LR語法分析棧中存放的狀態是識別（ B ）的DFA狀態。 A、前綴 B、可歸前綴 C、項目 D、句柄21、已知文法GS：s->LaR|R，L->bR|c，R->L 該文法是（ B ）。 (1)LR(0)文法；(2)SLR(1)文法；(3)LR(1)文法；(4)LALR(1)文法；(5)都不是 A、(1)(2) B、(3)(4) C、(1)(2)(3)(4) D、(5) E、(6)22、若一個句型中出現了某一產生式的右部，則此右部（ B ）是該句型的句柄。 A、一定 B、不一定 23、LR(K)方法是（ D ）。 A、從左到右分析，每次走K步的一種編譯方法 B、從左到

15、右分析，共經過K步的一種編譯方法 C、從左到右分析，每次向前預測K步的一種編譯方法 D、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法24、文法GS：S->AA，A->Aa|a 不是LR(1)文法的理由是（ D ） A、FIRST(S)NFIRST(A) B、FIRST(A)NFOLLLOW(A) C、FIRST(Aa)NFIRST(a) D、都不是25、下列關于標識符和名字的敘述中，正確的是（ C ）。 A、標識符有一定的含義 B、名字是一個沒有意義的字符序列 C、名字有確切的屬性 D、都不對26、編譯程序在其工作過程中使用最多的數據結構是（ C ）。它記錄著

16、源程序中的各種信息，以便查詢或修改。 A、線性表 B、鏈表 C、表 D、符號表 27、在編譯程序在其工作過程中使用的各種表中，以（ D ）最重要，其生存期最長，使用也最頻繁。 A、線性表 B、鏈表 C、表 D、符號表28、編譯程序使用（ B ）區別標識符的作用域。 A、說明標識符的過程或函數名 B、說明標識符的過程或函數的靜態層次 C、說明標識符的過程或函數的動態層次 D、標識符的行號29、動態存儲分配時，可以采用的分配方法有（ C ）。 (1)以過程為單位的棧式動態存儲分配；(2)堆存儲分配；(3)最佳分配方法 A、(1) B、(2) C、(1)(2) D、(1)(2)(3)30、過程調用時

17、，參數的傳遞方法通常有（ D ）。 (1)傳值；(2)傳地址；(3)傳結果；(4)傳名 A、(1)(2) B、(1)(2)(3) C、(1)(2)(4) D、(1)(2)(3)(4)31、在編譯方法中，動態存儲分配的含義是（ A ）。 A、在運行階段對源程序中的量進行分配 B、在編譯階段對源程序中的量進行分配 C、在編譯階段對源程序中的量進行分配，在運行時這些量的地址可以根據需要改變 D、以上都不對32、PASCAL中過程說明的局部量地址分配在（ B ）。 A、調用者的數據區中 B、被調用者的數據區 C、主程序的數據區 D、公共數據區33、表達式-a+b*c+d+(e*f)/d*e，如果優先級

18、由高到低依次為-、+、*、/，且均為左結合，則其后綴式為（ D ）。 A、abc*+d+ef*d/e*+- B、a-bc*def*d/e*+ C、a-bc*+def*d/e*+ D、a-b+cd+ef*+*de*/34、表達式a*b-c-d$e$f-g-h*i中，運算符的優先級由高到低依次為-、*、$，且均為右結合，則其后綴式為（ D ）。 A、ab*c-d-e$fg-h-i*$ B、$*a-b-cd$e*-f-ghi C、bcd-a*efgh-i*$ D、abcd-*efgh-i*$ E、ab*c-d-e$fg-h-i*$35、a:= a+b*c(d/e)/f的逆波蘭記號表示是（ C ）。A

19、、aabc*+de/f/:= B、aabcde/*f/:= C、aabcde/*f/+:= D、以上都不對。三、簡答題：1、什么是語法制導翻譯？答：所謂語法制導翻譯，是指在語法規則的制導下，通過計算語義規則，完成對輸入符號的翻譯。由于使用屬性文法時把語法規則和語義規則分開，但在使用語法規則進行推導或歸約的同時又使用這些語義規則來指導翻譯與最終產生目標代碼，所以稱為語法制導翻譯。2、寫出算術表達式A+B*(C-D)+E/(C-D)*N 的三元式、四元式序列。答：四元式： 三元式：（-，C，D，T1） （1） （-，C，D）（*，B，T1，T2） （2）（*，B，（1）（+，A，T2，T3） （3

20、） （+，A，（2）（-，C，D，T4） （4） （-，C，D）（*，T4，N，T5） （5） （*，（4），N）（/，E，T5，T6） （6）（/，E，（5）（+，T3，T6，T7） （7） （+，（3），（6）3、寫出條件語句 IF a<0 THEN x:=x+1 ELSE x:=4*（x-1）的四元式形式。 答：（1） （>，a，0，T1） （2） （BMZ，T1， ，（6） （3） （+，x，1，T2） （4） （：=，T2， ，x） （5） （BR， ， ，（9） （6） （-，x，1，T3） （7） （*，4，T3，T4） （8） （：=，T4， ，x） （9）4、把語

21、句 IF AB<D then S1 else S2 翻譯成一串四元式。答：（1） （，B，D，T1 （2） （，A，T1 ，T2） （3） （BMZ，T2， ，（6） （4） S1的四元式序列 （5） （JMP， ， ，（7） （6） S2的四元式序列 （7） 5、給出表達式A+B*(C-D)-E/FG 的三元式、逆波蘭和四元式表示。 答： A、三元式 B、四元式 （1）（-，C，D） （1）（-。C。D。T1） （2）（*，B，（1） （2）（*，B，T1，T2） （3）（+，A，（2） （3）（+，A，T2，T3） （4）（，F，G） （4）（，F，G，T4） （5）（/，E，（4）

22、 （5）（/，E，T4，T5） （6）（-，（3），（5） （6）（-，T3，T5，T6） C、逆波蘭： ABCD-*+EFG/-6、給出算術表達式 -(a+b)*(c+d)-(a+b+c)的四元式序列。答：（1） （+，a，b，T1） （2） （neg，T1， ，T2） （3） （+，c，d，T3） （4） （*，T2，T3，T4） （5） （+，a，b，T5） （6） （+，T5，c，T6） （7） （-，T4，T6，T7）7、寫出當型語句 while x+y>3 do begin a:=a+3*b;b:=a+e-f*e; end; 的四元式序列。 答： （1） （+，x，y，T1）

23、 （2） （>，T1，3，T2） （3） （BMZ，T2， ,(12)） （4） （*，3，b，T3） （5） （+，a ，T3，T4） （6） （：=，T4， ，a） （7） （+，a，e，T5） （8） （*，f，e，T6） （9） （-，T5，T6，T7） （10） （：=，T7， ，b） （11） （BR， ， ，（1） （12）8、將語句if A V B>0 then while C>0 do C:=C+D翻譯成四元式。答：100 (jnz， A， -， 104)101 (j， -， -， 102)102 (j>， B， 0， 104)103 (j， -， -

24、， 109)104 (j>， C， 0， 106)105 (j， -， -， 109)106 (+， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)1099、對下列文法G: S'->#S# S->D(R) R->R;P|P P->S|i D->i （1）計算文法G中每個非終結符的FIRSTVT集； （2）計算文法G中每個非終結符的LASTVT集； 答：（1）各非終結符的FIRSTVT集合為：FIRSTVT（S）= # FIRSTVT（P）=（，i）FIRSTVT（S）=（，i） FIRSTVT（D）=i F

25、IRSTVT（R）=；，（，i ） （2）各非終結符的LASTVT集合為：LASTVT（S）=# LASTVT（P）= ，iLASTVT（S）= LASTVT（D）= i LASTVT（R）=；，），i10、對下列文法G: S'->#S# S->fStS S->i=E E->E+T|T T->PT|P P->(E)|i （1）計算文法G中每個非終結符的FIRSTVT集； （2）計算文法G中每個非終結符的LASTVT集；答：（1）各非終結符的FIRSTVT集合為：FIRSTVT（S）= # FIRSTVT（T）= ，（，i）FIRSTVT（S）=f，i

26、 FIRSTVT（E）=+，（，i ）FIRSTVT（P）=（，i ） （2）各非終結符的LASTVT集合為：LASTVT（S）=# LASTVT（T）= ，iLASTVT（S）= t，=，+，)，iLASTVT（E）= +，iLASTVT（P）= ，i11、文法G1：P->PaP|PbP|cP|Pe|f 證明文法G1是二義文法。答：因為文法存在句型：fbfbf ，此句型有兩棵不同的語法樹，所以文法是二義的。 或存在2種最右推導：A、 P=>PbP=>PbPbP=>PbPbf=>Pbfbf=>fbfbfB、 P=>PbP=>Pbf=>PbP

27、bf=>Pbfbf=>fbfbf12、有文法GN：N->SE|ES->SD|DE->0|2|4|6|8|10D->0|1|2|3|4|5|6|7|8|9證明該文法是二義的；此文法描述的語言是什么？并試寫出另一文法，使L（G）=L（G），且G是無二義的。答：對于該文法，存在句型110，有兩棵不同的語法樹或兩種不同的最右推導，因此文法具有二義性。 A、 N=>SE=>S10=>D10=>110 B、 N=>SE=>S0=>SD0=>S10=>D10=>110該文法描述的語言是偶數集合。等價的無二義文法是

28、：GN：N->SE|ES->SD|DE->0|2|4|6|8D->0|1|2|3|4|5|6|7|8|913、寫出不能被5整除的偶整數的文法。答：GZ:Z->(+|-)ABA->0|1|2|3|4|5|6|7|8|9|AAB->1|2|3|4|5|6|7|8|914、對于文法G=（VN，VT，S，P）： VN= S，A，B，；VT=a，b，開始符號為SP：S->aB|bAA->aS|bAA|aB->bS|aBB|b 給出串aaabbabbba的（1） 最左推導；（2）最右推導；（3）推導樹。答：最左推導： S=>aB=>a

29、aBB=>aaaBBB=>aaabSBB=>aaabbABB=>aaabbaBB=>aaabbabB=>aaabbabbS=>aaabbabbbA=>aaabbabbba最右推導：S=>aB=>aaBB=>aaBbS=>aaBbbA=>aaBbba=>aaaBBbba=>aaaBbbba=>aaabSbbba=>aaabbAbbba=>aaabbabbba15、什么是句柄？答：一個句型德最左直接短語稱為句柄。16、什么是最左素短語？17、上下文無關文法答：若一個形式文法 G = (N,

30、, P, S) 的產生式規則都取如下的形式：V -> w，則稱之為上下文無關的，其中 VN ，w(N)* 。上下文無關文法取名為“上下文無關”的原因就是因為字符 V 總可以被字串 w 自由替換，而無需考慮字符 V 出現的上下文。上下文無關文法重要的原因在于它們擁有足夠強的表達力來表示大多數程序設計語言的語法； 四、問答題：1、給出將賦值語句翻譯成四元式的語法制導定義，允許右部表達式含有加法、乘法、取負、括號運算。生成賦值語句x:=b*(c+d)+a的四元式。2、出條件賦值語句 i:=if b then e1 else e2 的語義子程序。其中b是布爾表達式，e1和e2 是算術表達式，I代

31、表與e1和e2類型相同的左部變量。按寫出的語義子程序生成條件賦值語句 z:=if a>c then x+y else x-y+0.5 的四元式序列。3、試寫出PASCAL循環語句 for I:=1 to n do s的語義子程序，假定該語句的文法為： F1:=for i:=1 to n S:= F1 do S1 4、給出做為條件控制的布爾表達式翻譯為四元式的語法制導定義，允許布爾表達式中有與、或、非及括弧運算。（如在翻譯過程中使用了自定義的函數，可以不寫函數過程，但請注明函數的功能和出入口的參數）。5、按語法制導的定義將下面的后綴表達式翻譯成中綴表達式。注意：不允許出現冗余括號。E-&g

32、t;E1E2+E->E1E2*E->id6、某程序設計語言說明部分的語法制導定義如下所示：D->TLT->int|realL->L1,id|id給出其語法制導定義及自底向上的翻譯方案，并比較兩者的不同。7、設有文法GS：S->E(1)E->Aa(2)|Bb(3)A->cA(4)|d(5)B->cB(6)|d(7) 構造其LR（0）分析表并利用此分析表判斷符號串acccd是否是該文法的句子。8、對下列文法：S->SS->bRSTS->bR R->dSaR->eT->fRaT->f(1)出非終結符的FI

33、RST和FOLLOW的集合。（2）構造該文法的SLR（1）分析表。9、給定文法 GS ：S SaA | aA AbS | b 請構造該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 。 請構造該文法的 LR(0) 分析表。 什么是 LR(0) 文法？該文法是 LR(0) 文法嗎？為什么？ 什么是 SLR(1) 文法？該文法是 SLR(1) 文法嗎？為什么？ 10、構造下列文法的LR（1）分析表，其中S 是文法的開始符號。S->SS->Aa|dAb|Bb|dBaA->cB->c11、對下面的文法G：S->bAAB|bAA->dSa|bB-&g

34、t;cAa|c（1）判斷此文法是下列文法中的哪一種？并說明理由。 LR（0）、SLR（1）、LALR（1）、LR（1） （2）構造相應文法的項目集族和分析表。12、對下面的文法GS：S->aBc|bABA->aAb|bB->b|構造其LL（1）分析表，并利用符號棧分析符號串baabbb是否是該文法的句子。13、對下面的文法G：E->E+T|TT->T*F|FF->(E)|I(1) 構造其消除直接左遞歸后的文法G； （2）構造文法G 的LL（1）分析表，并利用符號棧分析符號串i1*i2+i3是否是該文法的句子。14、對下面的文法G：P->begind;X

35、endX->d;X|sYY->sY|構造文法G 的LL（1）分析表15、對下面的文法G：E->TEE->+E|T->FTT->T|F->PFF->*F|P->(E)|a|b| (1)計算這個文法的每個非終結符的FIRST和FOLLOW集合； （2）證明這個文法是LL（1）的； （3）構造它的預測分析表； （4）構造它的遞歸下降分析程序。16、對文法G(S)：S ® S Ú a T | a T | Ú a TT ® Ù a T | Ù a(1) 消除該文法的左遞歸和提取左公因子；(2

36、) 構造各非終結符的FIRST和FOLLOW集合；(3) 構造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。 17、設字母表= a，b，給出上的一個正則式b*abb*(abb*)。（1）構造該正則式所對應的NFA（畫出轉換圖）；（2）將所求的NFA確定化（畫出DFA的轉換圖）；（3）將所求出的DFA最小化（畫出極小化后的轉換圖）；（4）該正則式所表示的正則集是什么？試用自然語言描述之。18、設字母表= a，b，給出上的一個正則式（a *|b*）b(ba)*。（1）構造該正則式所對應的NFA（畫出轉換圖）；（2）將所求的NFA確定化（畫出DFA的轉換圖）；（3）將所求出的DFA最小化

37、（畫出極小化后的轉換圖）；19、設有語言 L= | 0,1 + ，且不以 0 開頭，但以 00 結尾 。 試寫出描述 L 的正規表達式； 構造識別 L 的 DFA （要求給出詳細過程，并畫出構造過程中的 NDFA、DFA 的狀態轉換圖，以及 DFA 的形式化描述 ) 。 20、設字母表= a，b，給出上的一個正則式（a|b）*（aa|bb）（a|b）*。（1）構造該正則式所對應的NFA（畫出轉換圖）；（2）將所求的NFA確定化（畫出DFA的轉換圖）；（3）將所求出的DFA最小化（畫出極小化后的轉換圖）；21、設字母表= a，b，給出上的一個正則式（a|b）*a（a|b）。（1）構造該正則式所對

38、應的NFA（畫出轉換圖）；（2）將所求的NFA確定化（畫出DFA的轉換圖）；（3）將所求出的DFA最小化（畫出極小化后的轉換圖）；22、設有語言 L= | 0,1 + ，且不以 0 開頭，但以 00 結尾 。試寫出描述 L 的正規表達式；構造識別 L 的 DFA （要求給出詳細過程，并畫出構造過程中的 NDFA 、 DFA 的狀態轉換圖，以及 DFA 的形式化描述 ) 。答：（ 1 ）正規表達式： 1(0|1) * 00 （ 2 ）第一步：將正規表達式轉換為 NDFA 第二步：將 NDFA 確定化為 DFA ：造表法確定化（ 3 分） 確定化后 DFA M 的狀態轉換表 狀態 輸入I 0I 1

39、t01SA,D,Bq 0q 1A,D,BD,B,CD,B重新命名q 1q 2q 3D,B,CD,B,C,ZD,Bq 2q 4q 3D,BD,B,CD,Bq 3q 2q 3D,B,C,ZD,B,C,ZD,Bq 4q 4q 3DFA 的狀態轉換圖第三步：給出 DFA 的形式化描述 DFA M = （ q 0 , q 1 , q 2 , q 3 , q 4 , 0,1, t, q 0 , q 4 ）t 的定義見 M 的狀態轉換表。23、給定文法 GS ：S SaA|aA AbS|b請構造該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 。請構造該文法的 LR(0) 分析表。什么是

40、LR(0) 文法？該文法是 LR(0) 文法嗎？為什么？什么是 SLR(1) 文法？該文法是 SLR(1) 文法嗎？為什么？ 答： （1）拓廣文法： GS: S S S SaA S a A AbS A b 該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA ： 該文法的 LR(0) 分析表： 狀態ACTIONGOTOab#SA0S 211S 3acc2r 3r 3r 33S 544r 2r 2 /S 6r 25r 5r 5r 56S 277r 4 /S 3r 4r 4 LR(0) 文法：該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 中沒有沖突狀態。該文法不

41、是 LR(0) 文法，因為存在沖突狀態： I 4 和 I 7。 SLR(1) 文法：該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 中有沖突狀態，沖突可用 FOLLOW 集解決。該文法不是 SLR(1) 文法。因為 FOLLOW(S)=a,b,# ，所以無法解決沖突。24、對下面的文法G：S->aBc|bABA->aAb|bB->b| (1)計算這個文法的每個非終結符的FIRST和FOLLOW集合； （2）證明這個文法是LL（1）的；（3）構造它的預測分析表。答：（1）first(B)=b, ,first(A)=a,b,first(S)=a,bFollow

42、(S)=#,follow(A)=b,#,follow(B)=c,# (2)因為只有FIRST(B)含有e , 所以只考慮： FOLLOW(B)=FIRST(c) ÈFOLLOW(S)=c, # 該文法的LL(1)表 (3)該文法的LL(1)分析表如下： abc#SaBcbABAaAbbBbee25、設字母表= a，b，對于以aa或ab結尾的字的正規集。（1）請寫出描述該語言的正規式。（2）構造該正規式所對應的NFA（畫出轉換圖）；（3）將所求的NFA確定化（畫出DFA的轉換圖）；（4）將所求出的DFA最小化（畫出極小化后的轉換圖）； 答： （1）正則式為：（a|b）*a(a|b）。 （1分）（2）由正則式得到的轉換系統如下圖： （1分） （3）由子集法構造的DFA如下圖： （4）DFA最小化如下圖： 26、設文法G為 S à E Eà TE | T à eT | t (1)證明它是LR(1)文法； (2)構造它的LR(1)分析表； (3)給出輸入符號串etet的分析過程。 答：(1)拓廣文法G：（1分）(0) S' àS (1) S à E (2) Eà TE