完整版編譯原理復習題考試

1、編譯原理復習題一、是非題I 計算機高級語言翻譯成低級語言只有解釋一種方式。(X )3 每個文法都能改寫為 LL(1) 文法。(X )4 算符優(yōu)先關系表不一定存在對應的優(yōu)先函數。(V)5 LR分析方法是自頂向下語法分析方法。(X )6 “用高級語言書寫的源程序都必須通過編譯，產生目標代碼后才能投入運行”這種說法。(X7 .一個句型的句柄一定是文法某產生式的右部。(V)8.僅考慮一個基本塊，不能確定一個賦值是否真是無用的。(V )9 .在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達式外提和削減運算強度。(X10. 對于數據空間的存貯分配，F(xiàn)ORTRAN采用動態(tài)貯存分配策略。(XII 甲機上的某編譯程序

2、在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。(X12遞歸下降分析法是自頂向下分析方法。(V )13產生式是用于定義詞法成分的一種書寫規(guī)則。(X14.在SLR(1)分析法的名稱中，S的含義是簡單的。(V)15 綜合屬性是用于“自上而下”傳遞信息。(X16符號表中的信息欄中登記了每個名字的屬性和特征等有關信息，如類型、種屬、所占單元大小、地址等等。( X)17. 程序語言的語言處理程序是一種應用軟件。(X18. 解釋程序適用于 COBOL和FORTRAN 語言。(X19. 一個 LL(l)文法一定是無二義的。(V)20. 正規(guī)文法產生的語言都可以用上下文無關文法來描述。(V)2

3、1 . 一張轉換圖只包含有限個狀態(tài)，其中有一個被認為是初態(tài)，最多只有一個終態(tài)。(X )22 目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。(V)22. 逆波蘭法表示的表達式亦稱后綴式。(V )23. 如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。(V )24. 數組元素的地址計算與數組的存儲方式有關。(V)25. 算符優(yōu)先關系表不一定存在對應的優(yōu)先函數。(X)26. 編譯程序是對高級語言程序的解釋執(zhí)行。(X)27. 一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。(X)28. 一個算符優(yōu)先文法可能不存在算符優(yōu)先函數與之對應。( V )29. 語法分析時必須先消除文

4、法中的左遞歸。 (X)30. LR 分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。( V)31. 逆波蘭表示法表示表達式時無須使用括號。(V )32. 靜態(tài)數組的存儲空間可以在編譯時確定。(V)33. 進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。(V)34. 兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。(V)35. 一個語義子程序描述了一個文法所對應的翻譯工作。(X)36 .設r和s分別是正規(guī)式，則有 L(r|s)=L(r)L(s)。( X37. 確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。(V)38. 詞法分析作為單獨的一遍來

5、處理較好。(X)39. 構造 LR 分析器的任務就是產生 LR 分析表。 (V)40. 規(guī)范歸約和規(guī)范推導是互逆的兩個過程。(V)41. 同心集的合并有可能產生新的“移進” /歸“約”沖突。 (X)42. LR 分析技術無法適用二義文法。( X)43. 樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。(X)44 程序中的表達式語句在語義翻譯時不需要回填技術。(V)45.對中間代碼的優(yōu)化依賴于具體的計算機。(X)46若一個句型中出現(xiàn)了某產生式的右部，則此右部一定是該句型的句柄。(X47. 在程序中標識符的出現(xiàn)僅為使用性的。(X48. 削減運算強度破壞了臨時變量在一基本塊內僅被定義一次

6、的特性。(X49. 編譯程序與具體的機器有關，與具體的語言無關。(X二、選擇題 (請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論)1. 一個編譯程序中，不僅包含詞法分析， ( A ) ，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分。A. 語法分析B.文法分析C.語言分析 D.解釋分析2. 語法分析器則可以發(fā)現(xiàn)源程序中的 ( D ) 。A.語義錯誤B .語法和語義錯誤C.錯誤并校正D.語法錯誤3. 解釋程序處理語言時 , 大多數采用的是 ( B ) 方法。A. 源程序命令被逐個直接解釋執(zhí)行B. 先將源程序轉化為中間代碼，再解釋執(zhí)行C. 先將源程序解釋轉化為目標程序，再執(zhí)行D. 以上方

7、法都可以4. 編譯程序是一種 ( B ) 。A.匯編程序B.翻譯程序C.解釋程序D .目標程序5. 文法分為四種類型，即 0型、1型、2型、3型。其中 3型文法是 ( B ) 。A.短語文法B .正則文法C.上下文有關文法D .上下文無關文法6. 通常一個編譯程序中， 不僅包含詞法分析， 語法分析， 中間代碼生成， 代碼優(yōu)化， 目標代碼生成等五個部分， 還應包括 ( C )。A .模擬執(zhí)行器B .解釋器C.表格處理和出錯處理D.符號執(zhí)行器7. 一個句型中的最左 ( B )稱為該句型的句柄。A .短語B .簡單短語C.素短語D .終結符號8. 文法 GE ：EF I E + TF IT * FF

8、f I ( E )該文法句型 E F * (E T) 的簡單短語是下列符號串中的 ( B )。 （ E T ） E TF F * （E T）A .和B .和C .和D .9. 詞法分析器用于識別 ( C )。A .句子B .句型C.單詞D .產生式10. 在自底向上的語法分析方法中，分析的關鍵是 ( A )。A .尋找句柄B.尋找句型 C.消除遞歸 D .選擇候選式11. 文法 G 產生的 ( D )的全體是該文法描述的語言。A .句型B .終結符集C.非終結符集D .句子12. 若文法 G 定義的語言是無限集，則文法必然是( A ) 。A .遞歸的B .前后文無關的C .二義性的D .無二義

9、性的13. 四種形式語言文法中， 1 型文法又稱為 ( C ) 文法。A .短語結構文法B .前后文無關文法C .前后文有關文法D .正規(guī)文法14. 一個文法所描述的語言是 ( A )。A .唯一的B .不唯一的C .可能唯一，好可能不唯一D .都不對15. ( B )和代碼優(yōu)化部分不是每個編譯程序都必需的。A .語法分析B .中間代碼生成C .詞法分析D .目標代碼生成16. ( B ) 是兩類程序語言處理程序。A .高級語言程序和低級語言程序B .解釋程序和編譯程序C .編譯程序和操作系統(tǒng)D .系統(tǒng)程序和應用程序17 數組的內情向量中肯定不含有數組的 ( D ) 的信息。A 維數B.類型C

10、.維上下界D 各維的界差18. 一個上下文無關文法 G 包括四個組成部分，它們是：一組非終結符號，一組終結符號，一個開始符號，以 及一組 ( D ) 。A .句子B .句型C .單詞D .產生式19. 文法分為四種類型，即 0 型、1型、2 型、3 型。其中 2 型文法是 ( D )。A .短語文法B .正則文法C.上下文有關文法D .上下文無關文法20. 文法 G 所描述的語言是 ( C )的集合。A .文法G的字母表 V中所有符號組成的符號串 B .文法G的字母表 V的閉包 V*中的所有符號串C .由文法的開始符號推出的所有終極符串D .由文法的開始符號推出的所有符號串21. 詞法分析器用

11、于識別 ( C )。A .字符串B .語句C .單詞D .標識符22. 文法分為四種類型，即 0型、1 型、2 型、 3型。其中 0 型文法是 ( A )。A .短語文法B .正則文法C .上下文有關文法D.上下文無關文法24( A ) 是一種典型的解釋型語言。A BASICB CC FORTRAN25與編譯系統(tǒng)相比，解釋系統(tǒng) ( D )。A 比較簡單 , 可移植性好 , 執(zhí)行速度快C 比較簡單 , 可移植性差 , 執(zhí)行速度慢26用高級語言編寫的程序經編譯后產生的程序叫A 源程序B 目標程序C 連接程序27詞法分析器用于識別 ( A )。A 字符串 B 語句C 單詞D PASCALB 比較復雜

12、 , 可移植性好 , 執(zhí)行速度快 D 比較簡單 , 可移植性好 , 執(zhí)行速度慢 ( B )。D 解釋程序D 標識符28編寫一個計算機高級語言的源程序后, 到正式上機運行之前，一般要經過 ( B )這幾步 :(1) 編輯 (2) 編譯 (3) 連接 (4) 運行A (1)(2)(3)(4)B (1)(2)(3) C (1)(3) D (1)(4)29把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由( B )完成的。A 編譯器B 匯編器C 解釋器D 預處理器31詞法分析器的輸出結果是 ( C )。A .單詞的種別編碼B .單詞在符號表中的位置C .單詞的種別編碼和自身值D .單詞自身值32 正規(guī)

13、式 M 1 和 M 2 等價是指 ( C ) 。AM1 和 M2 的狀態(tài)數相等BM1 和 M2 的有向邊條數相等CM1 和 M2 所識別的語言集相等DM1 和 M2 狀態(tài)數和有向邊條數相等33. 文法G: St xSx|y所識別的語言是(C )。AxyxB(xyx)* C xn yxn(n 0) Dx*yx*34. 如果文法 G是無二義的，則它的任何句子a ( A )。A .最左推導和最右推導對應的語法樹必定相同B .最左推導和最右推導對應的語法樹可能不同C .最左推導和最右推導必定相同D .可能存在兩個不同的最左推導，但它們對應的語法樹相同35. 構造編譯程序應掌握 ( D ) 。A .源程

14、序B .目標語言C .編譯方法D.以上三項都是36. 四元式之間的聯(lián)系是通過 ( B )實現(xiàn)的。A .指示器B .臨時變量C .符號表D .程序變量37. 表達式(AV B) A (C V D)的逆波蘭表示為(B )。A . n ABVA CD VB . AqB V CD VA C. AB Vn CDVAD . AqB VA CD V38. 優(yōu)化可生成 ( D )的目標代碼。A 運行時間較短B 占用存儲空間較小20C .運行時間短但占用內存空間大D 運行時間短且占用存儲空間小39. 下列 ( C )優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A 強度削弱B 刪除歸納變量40. 編譯程序使用 ( B )區(qū)別

15、標識符的作用域。A .說明標識符的過程或函數名C 說明標識符的過程或函數的動態(tài)層次41. 編譯程序絕大多數時間花在 ( D )上。A.出錯處理B.詞法分析C.C.刪除多余運算D 代碼外提B 說明標識符的過程或函數的靜態(tài)層次D .標識符的行號目標代碼生成D 表格管理42.編譯程序是對 ( D )。A 匯編程序的翻譯B 高級語言程序的解釋執(zhí)行C.機器語言的執(zhí)行D .咼級語言的翻譯43.采用自上而下分析，必須 ( C )。A .消除左遞歸B .消除右遞歸C .消除回溯D .提取公共左因子44.在規(guī)范歸約中，用 ( B )來刻畫可歸約串。A .直接短語B.句柄C.最左素短語D .素短語45.若a為終結

16、符，則 A-a為(B )項目。A .歸約B .移進 C .接受D .待約46.間接三元式表示法的優(yōu)點為 ( A )。A .采用間接碼表，便于優(yōu)化處理C .便于優(yōu)化處理，節(jié)省存儲空間47. 基本塊內的優(yōu)化為 ( B )。A .代碼外提，刪除歸納變量C .強度削弱，代碼外提48. 在目標代碼生成階段，符號表用B .節(jié)省存儲空間，不便于表的修改D.節(jié)省存儲空間，不便于優(yōu)化處理B .刪除多余運算，刪除無用賦值D .循環(huán)展開，循環(huán)合并( D )。49.若項目集Ik含有A-a 則在狀態(tài)k時，僅當面臨的輸入符號 一定是 ( D )。a FOLLOW(A)時，才采取 “A a ”動作的A. LALR 文法B.

17、LR(0)文法C. LR(1)文法D. SLR(1)文法50.堆式動態(tài)分配申請和釋放存儲空間遵守( D )原則。A .先請先放B .先請后放C .后請先放D.任意A .目標代碼生成B.語義檢查C.語法檢查D .地址分配三、填空題1. 編譯程序的工作過程一般可以劃分為詞法分析,語法分析 , 語義分析 ,中間代碼生成 , 代碼優(yōu)化等幾個基本階段 同時還會伴有 _表格處理 _和 _ _出錯處理 _。2. 編譯方式與解釋方式的根本區(qū)別在于_是否生成目標代碼 _。3. 產生式是用于定義 _語法成分 _的一種書寫規(guī)則。4 .設G是一個給定的文法，S是文法的開始符號，如果 S-x(其中x VT*),則稱x是

18、文法的一個句子_5. 自頂向下的語法分析方法的基本思想是：從文法的_開始符號 開始，根據給定的輸入串并按照文法的產生式一步一步的向下進行 _直接推導 ，試圖推導出文法的 _句子，使之與給定的輸入串 _匹配_。6. 常用的參數傳遞方式有 _傳地址 _，傳值和傳名。7. 一個句型中的最左簡單短語稱為該句型的_句柄 _。8. 對于文法的每個產生式都配備了一組屬性的計算規(guī)則，稱為_語義規(guī)則 _ 。9. 一個典型的編譯程序中，不僅包括_詞法分析 _、_語法分析 _、_中間代碼生成 _、代碼優(yōu)化、目標代 碼生成等五個部分，還應包括表格處理和出錯處理。10. 從功能上說，程序語言的語句大體可分為_執(zhí)行性 _

19、語句和 _說明性 _語句兩大類。11. 掃描器的任務是從 _源程序 _中識別出一個個 _單詞符號 _。12. 產生式是用于定義 _語法范疇 _的一種書寫規(guī)則。13. 語法分析是依據語言的 _語法 _規(guī)則進行的，中間代碼產生是依據語言的_語義_規(guī)進行的。14. 語法分析器的輸入是 _單詞符號串 _，其輸出是 _語法單位 _。15. 一個名字的屬性包括 _類型_和_作用域 _。16. 逆波蘭式 ab+c+ d*e-所表達的表達式為 _(a+b+c)*d-e 。17 語法分析最常用的兩類方法是自上而下_和_自下而上分析法。18 計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋_和 _編譯_。19

20、掃描器是詞法分析器，它接受輸入的 源程序，對源程序進行詞法分析并識別出一個個單詞 符號，其輸出結果是單詞符號，供語法分析器使用。20.自上而下分析法采用 移進_、歸約、錯誤處理、接受_等四種操作。21 . 一個LR分析器包括兩部分：一個總控程序和 一張分析表_。22. 后綴式abc-/所代表的表達式是a/(b-c)_。23. 局部優(yōu)化是在_基本塊范圍內進行的一種優(yōu)化。24. 詞法分析基于 正則 文法進行，即識別的單詞是該類文法的句子。25語法分析基于上下文無關文法進行，即識別的是該類文法的句子。語法分析的有效工具是 語法樹 26. 分析句型時，應用算符優(yōu)先分析技術時，每步被直接歸約的是_最左素

21、短語 ，而應用LR分析技術時，每步被直接歸約的是 句柄_。27. 語義分析階段所生成的與源程序等價的中間表示形式可以有逆波蘭、四無式表示與三元式表 示等。28按Chomsky分類法，文法按照規(guī)則定義的形式進行分類。遞歸定義的規(guī)則。29.一個文法能用有窮多個規(guī)則描述無窮的符號串集合(語言)是因為文法中存在有 四、簡答題1. 寫一文法，使其語言是偶正整數的集合，要求：(1)允許0打頭;(2) 不允許0打頭。解：(1)GS=(S,P,D,N,0,1,2,9,P,S)P:S-PD|DP-NP|ND-0|2|4|6|8N-0|1|2|3|4|5|6|7|8|9(2)GS=(S,P,R,D,N,Q ,0,

22、1,2,9,P,S)P:S-PD|P0|DP-NR|NR-QR|QD-2|4|6|8N-1|2|3|4|5|6|7|8|9Q-0|1|2|3|4|5|6|7|8|92. 構造正規(guī)式相應的NFA : 1(0|1)*101解1(0|1)*101對應的NFA為3. 寫出表達式(a+ b*c)/(a + b)- d的逆波蘭表示和三元式序列。逆波蘭表示：abc* + ab+ /d 三元式序列： (* , b, c) (+, a,) (+, a, b) (/,，) (，d)4. 已知文法GS為：St dABAt aA|aBt Bb| GS產生的語言是什么？答：GS產生的語言是 L(GS)= danbm |

23、 n 1,m 0。5. 構造正規(guī)式相應的DFA : 1(1010 * | 1(010) * 1) * 0 。解 ：1(1010*|1(010)*1)*0 對 應 的 NFA 為6.已知文法 G(S)Sta|A |(T)Ttt , S|S寫出句子(a, a), a)的規(guī)范歸約過程及每一步的句柄。解：句型歸約規(guī)則句柄(a, a), a)STaa(S, a), a)TtSS(T , a), a)STaa(T , S), a)Ttt , ST , S(S), a)TtSS(T) , a)St S(T)(T)(S, a)TtSS(T, a)STaa(T, S)Ttt , ST , S(T)St (T)(

24、T)S7. 寫一個文法，使其語言是奇數集，且每個奇數不以0開頭。解：文法G(N):NT AB|BAt AC|DBt 1|3|5|7|9DT B|2|4|6|8Ct 0|D8. 設文法G(S):St (L)|a S|a LF , S|S(1) 消除左遞歸和回溯；(2) 計算每個非終結符的 FIRST 和 FOLLOW 。 解： (1)St (L)|aSS tS| LtSLLtSL| (2)FIRST)S) = (, a FIRST(S) = , a, FIRST(L) = ( , a FIRST(L) = ,門9. 已知文法 G(E)EtT|ETTtF|T *FFOLLOW(S) = # , ,

25、 )FOLLOW(S) = # , )FOLLOW(L) = ) FOLLOW(L = )Ft(E)|i(1)給出句型(T *F + i)的最右推導；給出句型(T *F + i)的短語、素短語。解：(1) 最右推導： E=T-F=(E)-(E T)=(E F)-(E i)=(T i)=(T*F i)(2)短語：(T*F + i) , T*F + i, T*F , i素短語： T*F,i10. Whilea 0 V b v 0 doBeginX：= X1；if a0 then a：= a1else b：= b1解：(1) (j， a，0，5)(2) (j ，3)(3) (jv， b，0，5)(4

26、) (j ，15)(5) (， X，1，T1)(6) (：=， T1，X)(j E0， 9)(8) (j ，12)(9) (， a，1，T2)(10) (：=，T2，a)(11) (j，1)(12) (， b，1，T3)(13) (：=，T3，b)(14) (j，1)(15)End ； 翻譯成四元式序列。11. 寫出下列表達式的三地址形式的中間表示。(1) 5+6 *(a + b);(2) for j:=1 to 10 do aj + j:=0。答：(1)100: t1:=a+b101: t2:=6*t1102: t3:=5+t2(2)100: j:=1101: if j10 goto NEX

27、T102: i:=j+j103: ai:=012. 設基本塊p由如下語句構成:T 0 : =3.14;T 1 :=2*T 0 ;T 2 :=R+r;A:=T l *T 2;B:=A;T 3 :=2*T 0 ;T 4 :=R+r;T 5 :=T 3 *T 4 ;T 6 :=R-r ;B:=T 5 *T 6;試給出基本塊p的DAG。O T03.14解：基本塊p的DAG圖：13. 寫出表達式（a+b）/（a-b-（a+b*c）的三元序列及四元序列。 解：（1 ）三元式： （+, a, b） （，a, b） （/,，）* , b, c） （+, a,） （，）（2 ）四元式： （+, a, b, T1

28、） （，a, b, T2）3（ /, T1 , T2 , T3）* , b, c, T4）（+, a, T4, T5）(，T3, T5, T6)14. 寫一個文法使其語言為偶數集，且每個偶數不以 0開頭。 解：文法 G(S)：St AB|B|AOAt AD|CBt2|4|6|8Ct1|3|5|7|9|BDt0|C15. 設文法 G ( S )：StS aF|aF| aFFt *aF|*a (1)消除左遞歸和回溯；(2)構造相應的 FIRST 和 Follow 集合。 解：(1)S-aFS|aFSS-+ aFS| &F-*aFF-F|&(2)FIRST(S) = a, +FOLLOW(S) =

29、#FIRST(S)= +, FOLLOW (S) = #FIRST(F ) = *FOLLoW (F) = ( +, #FIRST(F) =*，F(xiàn)OLLOW (+，16. 簡要說明語義分析的基本功能。 答：語義分析的基本功能包括 : 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。17. 考慮文法 GS:St (T) | a+S | aT t T,S | S 消除文法的左遞歸及提取公共左因子。解：消除文法 GS 的左遞歸：St(T) | a+S | aTt STTt ,ST |提取公共左因子：St(T) | aSSt +S |&TtSTTt ,ST|&18. 試為表達式 w+(a+b)*(c

30、+d/(e-10)+8) 寫出相應的逆波蘭表示。 解： w a b + c d e 10 - / + 8 + * +19. 按照三種基本控制結構文法將下面的語句翻譯成四元式序列：while (AC A B 1) C=C+1;else while (A D)A=A+2;。解：該語句的四元式序列如下(其中E1、E2和E3分別對應AV CA BV D、A1和AD ,并且關系運算符優(yōu)先級高)：100 (j,A,C,102)101 (j,亠113)102 (jAc|aBA-abB-bc寫出L(GS)的全部元素。解: S=Ac=abc或 S=aB=abc所以 L(GS)=abc22. 構造正規(guī)式 1(0|

31、1)*101相應的DFA。確定化:01XAAAABABACABACAABYABYACAB重新命名，令 AB為B、AC為C、ABY為D得:01XAAA0BCBCADrfcBS-aF|(T)T-T,S|S對(a,(a,a)和(a,a),A,(a),a)的最左推導。解：對(a,(a,a )的最左推導為：S=(T) =(T,S) =(S,S) =(a,S)=(a,(T) =(a,(T,S) =(a,(S,S)=(a,(a,S) =(a,(a,a)對(a,a),A,(a),a)的最左推導為：S=(T) =(T,S) =(S,S) =(T),S)=(T,S),S) =(T,S,S),S) =(S,S,S)

32、,S)=(T),S,S),S) =(T,S),S,S),S) =(S,S),S,S),S)=(a,S),S,S),S) =(a,a),S,S),S) =(a,a),A,S),S)=(a,a),A,(T),S) =(a,a),A,(S),S) =(a,a),A,(a),S) =(a,a),A ,(a) ),a)24. 文法：S-MH|aH-LSo| &K-dML| L-eHfM-K|bLM判斷G是否為LL(1)文法，如果是，構造 LL(1)分析表。 解：各符號的 FIRST集和FOLLOW集為：FIRSfFOLLOWSH 2L何迅歸0訓K輒鶴0預測分析表為:SLdcfbS-M-K-K-K亠L甌4

33、 L-eHfK- -dML一二 由于預測分析表中無多重入口，所以可判定文法是LL(1)的。25. 敘述由下列正規(guī)式描述的語言(a) 0(0|1)*0(b) ( & |0)1*)*(c) (0|1)*0 1)(0|1)(d) 0*10*10*10*(e) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*解：(a)以0開頭、以0結尾的所有0和1的串。(b) 由0和1組成的串，包括空串。(c) 倒數第3個字符為0,由0和1組成的串。(d) 含有3個1的所有0和1的串。(e) 由偶數個0和偶數個1構成的所有0和1的串。26. 已知文法GS:S- (L)|aL L,S|S

34、為句子(a,(a,a)構造最左推導和最右推導。解：句子(a,(a,a)的最左推導為：S=(L)=(L ,S) =(S,S)=(a,S) =(a,(L)=(a,(L,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)句子(a,(a,a)的最右推導為：S=(L)=(L ,S) =(l,(L)=(L,(L,S)=(L,(L,a)=(L,(S,a)=(L,(a,a)=(S,(a,a)=(a,(a,a)五.計算題1.構造下述文法 GS的自動機：S-A0A-A0|S1|0該自動機是確定的嗎？若不確定，則對它確定化。解：由于該文法的產生式S-A0 , A-A0|S1中沒有字符集 VT的輸入，所以不

35、是確定的自動機。要將其他確定化，必須先用代入法得到它對應的正規(guī)式。把S?A0代入產生式 A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入 S-A0 有該文法的正規(guī)式：0(0|01)*0 ,所以，改寫該文法為確定的自動機為：由于狀態(tài)A有3次輸入0的重復輸入，所以上圖只是NFA，下面將它確定化：下表由子集法將NFADFA:rId - e-cbsurelb -1)AV1smBXC 站 Y, zC 民 ZBI轉換由上表可知 DFA為：1*2 .對下面的文法 G :E-TEE-+E| T-FTT -T| F- PFF- *F|P-(E)|a|bF(1) 計算這個文法的每個非

36、終結符的FIRST集和FOLLOW 集。(2) 證明這個方法是LL(1)的。(3) 構造它的預測分析表。解：(1)計算這個文法的每個非終結符的FIRST集和FOLLOW 集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b;FIRST(E)=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,A;FIRST(T)=FIRST(T) U =(,a,b,A, ;FIRST(F)=FIRST(P)=(,a,b,A;FIRST(F)=FIRST(P)=*, ;FIRST(P)=(,a,b,A;FOLLOW集合有：FOLLOW(E)

37、=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E) U FOLLOW(E)=+,),#; 不包含 FOLLOW(T)=FOLLOW(T)=FIRST(E) U FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T) U FOLLOW(T)=(,a,b,A,+,),#; 不包含 FOLLOW(F)=FOLLOW(F)=FIRST(T) U FOLLOW(T)=(,a,b,A,+,),#;FOLLOW(P)=FIRST(F) U FOLLOW(F)=*,(,a,b,A,+,),#;不包含 (2)證明這個方法是 LL(1)的。各產生式的SEL

38、ECT集合有：SELECT(E-TE)=FIRST(T)=(,a,b,人;SELECT(E-+E)=+;SELECT(E- )=FOLLOW(E/)=),#SELECT(T-FT)=FIRST(F)=(,a,b,A;SELECT(T-T)=FIRST(T)=(,a,b,A;SELECT(T- )=FOLLOW(T/)=+,),#;SELECT(F-PF)=FIRST(P)=(,a,b,A;SELECT(F-*F)=*;SELECT(F- )=FOLLOW(F)=(,a,b,A,+,),#;SELECT(P-(E)=(SELECT(P-a)=aSELECT(P-b)=bSELECT(P-a)=a

39、可見，相同左部產生式的SELECT集的交集均為空，所以文法GE是LL(1)文法。(3) 構造它的預測分析表。3 已知 NFA= ( x,y,z,0,1,M,x,z)，其中:M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)=文法GE的預測分析表如下：NFA 圖：集IIq - f-cJcwyre fMovg 1q(1 G”Il = -點W TqCjI)Az山SzC 熱 zDyClxj zC x,E【並yDy冋禺yE 旳 yF“z】AxF 並 y, aFl% aEa,y解：根據題意有下 表 由 子法 將NFA轉 換 為DFA*()atta#E-4TEZTTEF-TET兮fFT今T弓T今TF4PF