編譯原理復習題-給學生(2014).

1、編譯原理復習題一. 單項選擇題概述部分源程序B.目標語言編譯方法D.以上二項都是編譯程序絕人多數(shù)時間花在o D出錯處理B.詞法分析目標代碼生成D.表格管理編譯程序是對。D匯編程序的翻譯B.高級語言程序的解釋執(zhí)行機器語言的執(zhí)行D.高級語言的翻譯構造編譯程序應掌握o Do B1.A.C.2.A.C.3A.C.4.將編譯程序分成若干“遍”，是為了A.提高程序的執(zhí)行效率B.使程序的結構更為清晰C利用有限的機器內存并提高機器的執(zhí)行效率D. 利用有限的機器內存但降低了機器的執(zhí)行效率詞法分析部分51.A.B.C.D.2.A.C.3.DFA M(見圖1-1)接受的字集為_ 以0開頭的二進制數(shù)組成的集合 以0結

2、尾的二進制數(shù)組成的集合 含奇數(shù)個0的二進制數(shù)組成的集合 含偶數(shù)個0的二進制數(shù)組成的集合 詞法分析器的輸出結果是單詞的種別編碼 單詞的種別編碼和自身值 正規(guī)式Ml和M2等價是指。CB.D.。C單詞在符號表中的位置 單詞自身值C.源程序。DC(ab)*(AD.元程序D.7.A.C.8.AB.A. Ml和M2的狀態(tài)數(shù)相等B. Ml和M2的有向邊條數(shù)相等C. Ml和M2所識別的語言集相等D. Ml和M2狀態(tài)數(shù)和有向邊條數(shù)相等4. 詞法分析器的加工對象是o CA.中間代碼B.單詞5. 同正規(guī)式(a|b) *等價的正規(guī)式為A. (a|b)+B. a*|b*6. 兩個DFA等價是指：o DA. 這兩個DFA

3、的狀態(tài)數(shù)相同B. 這兩個DFA的狀態(tài)數(shù)和有向弧條數(shù)都相等C. 這兩個DFA的有向弧條數(shù)相等這兩個DFA接受的語言相同 卜列符號串不可以由符號集S = a,b上的正閉包運算產生的是: BaaaD. ab稱有限自動機Al和A2等價是指。DA1和A2都是定義在一個字母表上的有限自動機A1和A2狀態(tài)數(shù)和有向邊數(shù)相等C.D.9.C. A1和A2狀態(tài)數(shù)或有向邊數(shù)相等D. A1和A2所能識別的字符串集合相等 9.同正規(guī)式(a|b) +等價的正規(guī)式是B. (a|b) (a|b) *D. (a|b) | (a|b) *A. (a|b) *EC. (ab) * (ab)D語法分析1. 在規(guī)范歸約中，用來刻畫可歸約

4、串。BA.直接短語B.句柄C.最左素短語D.素短語2.若E為非終結符，則A-為項目。D3. 如果文法G是無二義的，則它的任何句子ao AA. 最左推導和最右推導對應的語法樹必定相同B. 最左推導和最右推導對應的語法樹可能不同C. 最左推導和最右推導必定相同D. 可能存在兩個不同的最左推導，但它們對應的語法樹相同4. 下列動作中，不是自下而上分析動作的是：_o BA.移進B.展開C.接受D.報錯6. 若a為終結符，則A-為項目。BA.歸約B.移進C.接受D.待約7. 語法分析時所依據(jù)的是。AA. 語法規(guī)則B.詞法規(guī)則C. 語義規(guī)則D.等價變換規(guī)則8. 文法G： S-xSx|y所識別的語言是o C

5、A. xyxB. (xyx)*C. xnyxn(nO)D. x*yx*9. 下列動作中，不是自上而下分析動作的是：o CA.匹配B.展開C.移進D.報錯10. 若A為非終結符，則A為_項目。AA.歸約B.移進C.接受D.待約11. 文法G： S-xSx|xS|y所識別的語言是o AA.B. (xvx)*C. xnyxqnMO)D. x*yx*13. 由文法的開始符號出發(fā)經(jīng)過若干步(包括0步)推導產生的文法符號序列稱為。BA.語言B.句型C.句子D.句柄14. 在自上而下的語法分析中，應從開始分析。CA.句型B.句子C.文法開始符號 D.句柄15. 一個文法G,若,則稱它是LL (1)文法。CA

6、. G中不含左遞歸B. G無二義性C. G的LL (1)分析表中不含多重定義的條目D. G中產生式不含左公因子16. 項目 SJS.為。DE 移進項目D.接受項目o AB.源程序D.符號表如果某行中存在標記為“馬”的欄，則:B.該行未必填滿D. goto表中也可能有“習”o AB.前綴D.項目xxS|y所識別的語言是B. (xxy)nD(xxjyA.歸約項目C. 待約項目17. 語法分析器的輸入是： A. Token 序列C.目標程序18. 在 LR (0)的 Action 表中,A.該行必定填滿“rj”C.其他行可能也有“rj”19. LR分析過程中棧內存儲的是A.活前綴C.歸約活前綴20.

7、 文法G： SA. xxynC. xxnyx”歸約的語法分析方法是21. 若狀態(tài)k含有項目“Ara.”，對任意非終結符a,都用規(guī)則“At A. LALR分析法B. LR(0)分析法C. LR(1)分析法D. SLR(l)分析法22. 在SLR (1)的Actum表中，如果某行中存在標記為“勺”的欄，貝山A.該行必定填滿“rj”B.該行未必填滿C.其他行可能也有D. goto表中也可能有“rj”23. 個指明了在LR分析過程中的某個時刻所能看到產生式多大一部分。DA.活前綴B.前綴C.歸約活前綴D項目 ”歸約的語法分24. 若狀態(tài)k含有項目“Atci.”，且僅當輸入符號aWFOLLOW(A)時，

8、才用規(guī)則“AELR(O)分析法 D. SLR分析法析方法是A. LALR分析法C. LR(1)分析法25. 設有文法GT:T-T*F|FF-*F t P|PP-(T)|a該文法句型T*P t (T*F)的句柄是卞列符號串。CA. (T*F)B. T*FC.PD. P t (T*F)26. LR分析表中的轉移表(goto)是以作為列標題的。BA.終結符 B.非終結符C.終結符或非終結符 D.表示狀態(tài)的整形數(shù)語法規(guī)則信息 語句序列o CD. F-L*F.一作為列標題的。D27. 編譯程序的語法分析器必須輸出的信息是 AA.語法錯誤信息B.C.語法分析過程D.28. F列項目中為可移進項目的是_A

9、E E B. Lf. C L-.-L29. LR分析表中的動作表(action)是以_非終結符終結符和結束符#。BA.終結符B.C.終結符或非終結符D.30. F列項目中為可歸約項目的是_A. E -.EB. L-*. C. L-*-.L D. F*L*.F33. LR分析器的核心部分是一張分析表，該表由組成。D編譯原理復習題A. ACTION 表E GOTO 表C.預測分析表DACTION表和GOTO表34. 在遞歸下降子程序方法中，若文法存在左遞歸，則會使分析過程產生。DA.回溯B.非法調用C.有限次調用D.無限循壞35. 最左簡單子樹的葉結點，自左至右排列組成句型的0 CA.短語B.句型

10、C.句柄D.間接短語36. 由文法的開始符號出發(fā)經(jīng)過若干步(包拾0步)推導產生的文法符號序列中，如果只含有終結符，則文法符號序列稱為 CA.語言B.句型C.句子D.句柄37. LL (1)分析法中“1”的含義是在輸入串中查看一個輸入符號，其目的是o CA.確定最左推導E.確定句柄C.確定使用哪一個產生式進行展開D.確定是否推導語義分析1 表達式G aVb) A (eVf)的逆波蘭表示為。BA. n abV AefVB aq bVefV AC abVn efVAD an bVAefV2. 中間代碼生成時所依據(jù)的是。CA 詞法規(guī)則E 語法規(guī)則C.語義規(guī)則D. 等價變換規(guī)則3. -a-(b*c/(c

11、-d)+(.b)*a)的逆波蘭表示是。(代表后綴式中的求負運算符)CA. abc *cd-ba*+/-E abc*cd-ba*+/-C. abc*cd-/ba*+-D abc*/cd-ba*+-4. 有文法G及其語法制導翻譯如下所示(語義規(guī)則中的*和+分別是常規(guī)意義下的算術運算符):E-E A T (E. val = E.val * T. valE-TE. val 二 T. valTT# nT. val = T r，. val + n. val Tf nT val = n. val則分析句子1 / 2 A 3 # 4其值為o CA. 10B34C. 14D. 545.有文法G及其語法制導翻譯如

12、下所示(語義規(guī)則中的*和+分別是常規(guī)意義下的算術運算符):E-e A T E. val = E.val * T. valE-TE val 二 T. valTT# nT. val = T.val + n. val Tf nT val = n. val則分析句子2 A 3 #4其值為. CA. 10B. 21C. 14D. 246 間接三元式表示法的優(yōu)點為_o AA. 采用間接碼表，便于優(yōu)化處理B. 節(jié)省存儲空間，不便于表的修改C. 便于優(yōu)化處理，節(jié)省存儲空間D. 節(jié)省存儲空間，不便于優(yōu)化處理7.文法GS及其語法制導翻譯定義如下：產生式語義動作S JS s T (L)print(S.num)S.n

13、um = L.num+17編譯原理復習題S aS.num = 0L L(1)，SL.num = L(l).num + S.numL SL.num = S.num亠CD. 4若輸入為(a,(a),且采用自底向上的分析方法，則輸出為A0】B1C2BD.程序變量o B8. 四元式之間的聯(lián)系是通過實現(xiàn)的。A.指示器 B.臨時變量C.符號表9. 表達式$ aVb) A (cVd)的逆波蘭表示為_A. -ab/cd/E an bVcdV AC abVn cdV AD an bVAcdV10. 表達式a+b+c+d的逆波蘭表示為。BA a+bc+d+E ab+c+d+C ab+cd+D abc+d+11有文

14、法G及其語法制導翻譯如下所示(語義規(guī)則中的*和+分別是常規(guī)意義下的算術運算符):T E.val = E(l).val * T.valE.val = T.valT.val = T(l).val + n.valT.val = n.valE-E(l) AE-TT-T(l)#nT- n則分析句子3 A 3 #4其值為。BA. 10B.21C.14D.2412. 表達式a+b+c的逆波蘭表示為。BA a+bc+Eab+c+C +abc+Dabc+13. 文法GS及其語法制導翻譯定義如下：產生式語義動作S J Spiint(S.num)S t (L)S.num = L.num +1S aS.num = 0

15、L L(1)，SL.num = L(l).num + S.numL SL.num = S.num若輸入為(a, a),且采用自底向上的分析方法，則輸出為A0E1C2D414有一語法制導翻譯定義如下：S-bAbprmtA- (Bprmt“2”AaprmtB-aA)prmt“4”若輸入序列為b (a (a(aa)b,且采用自底向上的分析方法，則輸出序列為o BA 32224441E 34242421C. 12424243D 3444221215.賦值語句X:=-(a+b)/(c-d)-(a+b*c)的逆波蘭表示是。CA. Xab+cd-/-bc *a+-:=B. Xab+/cd-bc*a+:=C.

16、 Xab+-cd-/ a be* +-：=D. Xab+cd-/abc*16. 有一語法制導翻譯定義如下，其中+表示符號連接運算:S-BB-aB-bB-BaE-Ebprint B.veisB.veis=aB.veis=bB.vers=a+B.versB.vers=b+B.veis若輸入序列為abab,且采用自底向上的分析方法，則輸出序列為。DA. aabbB. ababC. bbaaD. baba17. 編譯程序不能檢查、處理的錯誤是程序中的0 BA.靜態(tài)語義檢查B.動態(tài)語義檢查 C.語法錯誤D.詞法錯誤（優(yōu)化、存儲、錯誤管理）1. 在編譯過程中，如果遇到錯誤應該。CA. 把錯誤理解成局部的錯

17、誤B. 對錯誤在局部范圍內進行糾正，繼續(xù)向下分析C. 當發(fā)現(xiàn)錯誤時，跳過錯誤所在的語法單位繼續(xù)分析下去D. 當發(fā)現(xiàn)錯誤時立即停止編譯，待用戶改正錯誤后再繼續(xù)編譯二、填空題概述部分：1. 編譯程序的開發(fā)常常采用自編譯、 交叉編譯、 自展 和移植等技術實現(xiàn)。2. 解釋程序和編譯程序的區(qū)別在于是否生成目標程序。3. 如果編譯程序生成的目標程序是匯編語言程序，則源程序的執(zhí)行分為3個階段：編譯階段、匯 編階段和運行階段。4. 編譯程序工作過程中，第一階段輸入是一源程序，最后階段的輸出為 目標程序 。5. 編譯過程通?？煞譃?個階段詞法分析階段、語法分析階段、語義分析和中間代碼生成階段、 優(yōu)化階段和目標代

18、碼生成階段。6. 如果編譯階段生成的目標程序是某特定計算機系統(tǒng)的機器代碼程序，則源程序的執(zhí)行分為兩人階段： 編譯階段和運行階段。7. 對編譯程序而言，輸入數(shù)據(jù)是源程序 ，輸出結果是目標程序 &貫穿于編譯程始終的工作有符號表處理和出錯處理。詞法分析部分：1. 詞法分析的工作是將源程序中的字符串變換成單詞符號流的過程,所遵循的是語言的構詞 規(guī)則。2. 若兩個正規(guī)式所表示的正規(guī)集相同,則認為二者是等價的。3. 若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者是等價的。4. 正規(guī)式R1和R2等價是指o5. 詞法分析器的輸入是源程序字符串，輸出結構是 二元式（單詞種別，單詞自身的值）。詞法分析 所遵循的是語言

19、的構詞規(guī)則。6. 確定的有限自動機是一個五元組，包含的五個元分別是：狀態(tài)集合、字母表、初態(tài)、終態(tài)集、狀態(tài)轉 換函數(shù)集合。7. 有限自動機是更一般化的狀態(tài)轉換圖，它分為 確定的有限自動機DFA和 非確定的有限自動機NFA 兩種。8. NFA和DFA的區(qū)別主要有兩點：其一是_ NFA可以有若干個初始狀態(tài)，而DFA僅有一個初始狀態(tài)： 其二是NFA的狀態(tài)轉換函數(shù)f不是單值函數(shù)，而是一個多值函數(shù)。語法分析部分：(基本概念、LL (1)、LR (0)、SLR (1)、遞歸卞降子程序)1. 語法分析的方法通常分為兩類：自上而下分析方法和自卞而上分析方法。2. 文法中的終結符集和非終結符集的交集是空集。3.

20、一個句型的最左直接短語稱為該句型的鮑o4. 規(guī)范歸約是一最右推導的逆過程。5. 自下而上語法分析中分析器的動作有移進、 一歸約、接受 、報錯 。6. 自上而卞語法分析中分析器的動作有匹配終結符、 展開非終結符、分析成功、報錯7. 常用的自上而卞語法分析方法有遞歸卞降子程序方法和預測分析表方法(LL (1)方法)。8. 常用的自下而上語法分析方法有算符優(yōu)先分析法和LR分析法。9. _個LL(1)分析器由一張LL(1)分析表(預測分析表)、一個先進后出分析棧和一個控制程序(表驅動程序)組成。10. 一個LR分析器由 分析棧、 分析表 和總控程序三個部分組成。11. LR(0)分析法的名字中，“L”

21、表示自左至右分析輸入串，“R”表示采用最右推導的逆過程即最左 歸約?！?”表示向右查看0個字符。12. LL(1)分析法中，第一個L的含義是 從左到右掃描輸入串；第二個L的含義是 分析過程中采用 最左推導：1”的含義是只需向右查看一個符號就可以決定如何推導。13. LR(1)文法的含義是：L表明自左至右打描輸入電_，R表明采用最右推導的逆過程(最左歸約)方法進行分析14. 一個上下文無關文法是LL(1)文法的充分必要條件是：對每一個非終結符A的任何兩個不同產生式A-alp,有下面的條件成立：(1)FIRST(a)ClFIRST(B) = O;(2)假若0 = G 則有 FIRST(a)Cl F

22、OLLOW(A) = 0。15. 對于LL (1)文法中的任何產生式A-*a則需要滿足(_ a ) G First ( B )二 、_若_8二* ,則_ First (_ a ) Q_Follow(A)二_16. LR分析器的核心部分是一張分析表，該表包括動作(ACTION)表和 狀態(tài)轉換(GOTO)表 等 兩個子表。17. 關于非終結符A的直接左遞歸產生式：A-Aa|p,其中a、p是任意的符號串且p不以A開頭，則可 以將A的產生式改寫為右遞歸的形式為： ATA ,AfaAb。18. 在消除回溯，提取公共左因子時，關于A的產生式A - 申| 5pz | .| Op|pi+i | .|內，可以改

23、寫為：A 6ATBz丨8， A，-Bi丨耐。19.設GS是一文法，如果符號串x是從識別符號推導出來的，即有S=x,則稱x是文法GS的句型，若x僅由終結符號組成，即*則稱x為文法GS1的 句子。20.已知文法GS:S-*eT|RTT-*DR| RdR| D-*a|bd求 FIRST(S)=e, d, a, b, : FOLLOW(D)=_d,榔 。語義處理部分：1. 文法符號的屬性有兩種，一種稱為 繼承屬性，另一種稱為 綜合屬性2. 編譯過程中，常見的中間語言形式有逆波蘭表示法、抽彖語法樹、三元式、四元式3語法制導翻譯的方法就是為每個產生式配上一個 翻譯子程序(語義動作或語義子程序)，并在語 法

24、分析的同時執(zhí)行它們。4. 編譯過程中，常見的中間語言形式有逆波蘭表示法、抽彖語法樹、三元式、四元式6. 文法符號的屬性有兩種，一種稱為繼承屬性，另一種稱為綜合屬性。7. 四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的。8. 在屬性文法中，終結符只有綜合屬性。10. 語法制導翻譯的方法就是為每個產生式配上一個翻譯子程序（語義動作或語義子程序），并在語 法分析的同時執(zhí)行它們。11. 目前較常見的語言語義的描述形式是_屬性文法，并使用吾法制導翻譯方法完成對語法成分的翻譯。（優(yōu)化、存儲、錯誤管理）1. 代碼優(yōu)化的含義是：對代碼進行等價變換 ，使得變換后的代碼具有更高的 時間效率和 空間效率。2. 按照優(yōu)化對彖所

25、涉及的程序范圍，優(yōu)化分為局部優(yōu)化、循壞優(yōu)化和全局優(yōu)化o3. 基本塊，是指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口 4. 從編譯角度看，分配目標程序數(shù)據(jù)空間的基本策略有：靜態(tài)分配策略 、棧式動態(tài)分配策略和堆式動態(tài)分配策略。三、判斷題1. 設r和s分別為正規(guī)式，則有L（r|s） = L（i） | L.。（X ）2. 一個文法的所有句型的集合形成該文法所能接受的語言。（X ）3. 語法分析之所以采用上下文無關文法是因為它的描述能力最強。（X ）4. 由于LR（0）分析表構造簡單，所以它的描述能力強，適用面寬；LR（1）分析表因構造復雜而描述能力弱， 適用面窄。（X ）5. 逆波蘭表示法

26、表示表達式時無需使用扌舌號。（V ）6. 自動機M和M，的狀態(tài)個數(shù)不同，則二者必不等價。（X ）7. LL（1）文法一定不含左遞歸和二義性。（J ）8. 所有LR分析器的總控程序都是一樣的，只是分析表各有不同。（V ）9. 無論是三元式表示還是間接三元式表示的中間代碼，其三元式在三元式表中的位置一旦確定就很難改 變。（J ）10. 三地址語句類似于匯編語言代碼，可以看成中間代碼的一種抽象形式。（V ）11. 最左推導也被稱為規(guī)范推導。（X ）12. 運算對彖排列的先后順序在后綴式和中綴式中不同。（X ）13. 出現(xiàn)在移進-歸約分析器棧中的內容被稱為文法G的活前綴。（V ）14. LR方法可以分

27、析含有左遞歸的文法。（J ）15. 三元式的編號具有雙重含義，既代表此三元式，又代表三元式存放的結果。（7）16. 語義規(guī)則中的屬性有兩種：綜合屬性與繼承屬性。（V ）17. 移進-歸約分析器的格局中棧的內容一般是文法符號與狀態(tài)。（V ）18. 由于遞歸下降子程序方法較LL （1）方法簡單，因此它要求文法不必是LL （1）文法。（X ）19. 四元式的編號具有雙重含義，既代表此四元式，又代表四元式存放的結果。（X ）20. 用高級語言編寫的源程序必須經(jīng)過編譯，產生目標程序后才能運行。（X ）21. 源程序到目標程序的變換是等價變換，即兩者結構不同，但語義是一致的。（V ）22. 對于任何一個正

28、規(guī)式e,都存在一個DFA A,使得L （e） =L （A）。（ J ）23. 最小化的DFA,它的狀態(tài)數(shù)最小。（ J ）24. NFA的確定化算法具有消除邊的功能。（ J ）25. 每個非終結符產生的終結符號串都是該語言的子集。（X ）26. 一個語言的文法是不唯一的。（V ）27語法錯誤校正的目的是為了把錯誤改正過來。（ X ）28. 源程序和目標程序是等價關系。（ V ）29. 編譯程序中錯誤處理的任務是對檢查出的錯誤進行修改。（X ）30. 使用有限自動機可以實現(xiàn)單詞的識別。（V ）31一個非確定的有限自動機NFA可以通過多條路徑識別同一個符號串。（ 32最小化的DFA所識別接受的正規(guī)集

29、最小。（ X ）33. 個語言（如C語言）的句子是有窮的。（ X ）34. LL （1）方法又稱為預測分析方法。（J ）35. 個LL （1）文法是無二義和無回溯方法。（ J ）36. 語法分析器可以檢查出程序中的所有錯誤。（X ）37LR分析法是自上而下的語法分析方法。（ X ） 三.多項選擇題1.編譯器的各個階段的工作都涉及到（AE ）B.詞法分析A.表格處理C.語法分析D. 語義分析E.出錯處理2.令E = a,b,則工上的符號串的全體可用卞面的正規(guī)式表示。（ABE ）A. (a|b)*C. (a|b)+E. (a*b*)*B. (a*|b*)*D. (ab)*3.自上而下的分析方法有：

30、(AD )A.遞歸下降分析法B.LR (0)分析法C. LALR (1)分析法D. LL (1)分析法E. SLR (1)分析法4.文法 G： GS： S-CDAbbAC aCABa-aBbCEBb-bBAD-aDC BD-bDD eAabD是(A )oA. 0型文法B. 1型文法C.2型文法D.3型文法E.上卞文有關文法5. 對LR分析表的構造，有可能存在的動作沖突有:（AD ）A.移進/歸約沖突B.移進/移進沖突C.歸約沖突D.歸約/歸約沖突E. 移進沖突6. 一個編譯器可能有的階段為（AECDE ）A.詞法分析B.語法分析C.語義分析D.中間代碼生成E. 目標代碼生成7令S = a,b,

31、則工上的所有以b開頭，后跟若干個（可為0個）ab的符號串的全體可用卞面的正規(guī)式表 示。（AB ）B. (ba)*bD. (ba)+bA.b (ab)* C. b(a|b)+15E. b (a|b)*B.LR (0)分析法D. LL (1)分析法&自下而上的分析方法有：(BCE A.遞歸下降分析法C. LALR (1)分析法E. SLR (1)分析法9. 一般來說，編譯器可分為前端和后端，下列編譯階段可被劃分為編譯的前端的有：(ABCDE )A.詞法分析B.語法分析C.語義分析D.中間代碼生成 E.中間代碼優(yōu)化10. 令S = a,b,則工上的符號串的全體可用下面的正規(guī)式表示。(ABE )A.

32、(a|b)* B. (a*|b*)*C. (a|b)+ D. (ab)* E. (a*b*)*11. F列符號串是符號集X = a,b上的正規(guī)式的有：(ABCDE)A. B. a C. ab D. (ab I a) (ab I a)E. ab I ab12. 正規(guī)式服從的代數(shù)規(guī)律有：(ABDE )A. “或”運算服從交換律B. “或”運算服從結合律C. “連接”運算服從交換律D. “連接”運算服從結合律E. “連接”運算可對“或”運算進行分配13. 令= a,b,則工上的所有以b開頭，后跟若干個(可為0個)ab的符號串的全體可用下面的正規(guī) 式表示。(AE )A.b (ab)* B. (ba)*

33、b C. b(a|b)+D. (ba)+b E. b (a|b)*14. 一個LR分析器包拾：(ADE )A. 一個總控程序B. 一個項目集C. 一個活前綴D. 一個分析棧E. 張分析表15. LR分析器的核心部分是一張分析表，該表包括(DE )等子表。A. LL (1)分析表B.LR (1)分析表C. SLR (1)分析表 D. Action 表E. goto 表16. Action表中的每一項ActionS,a所表示的動作可能為：(ABCD )A.移進 B.接受C.歸約D. 出錯 E.待約五.簡答題1.構造正規(guī)表達式(a|b)*|aa)*b的NFA。解：17編譯原理復習題2.設M=(x,y

34、, a,b, f, x, y)為一非確定的有限自動機，其中f定義如下: f(x,a)=x,yfx,b=yf(y,a)=Pfy,b=x,y試構造相應的確定有限自動機M。解：對照自動機的定義M=(S,SoZ)，由f的定義可知f(xe)、f(y,b)均為多值函數(shù)，因此M是一非確定 有限自動機。先畫出NFAM相應的狀態(tài)圖，如下圖所示。用子集法構造狀態(tài)轉換矩陣，如卞表所示。IlahXgyyx,yx,yx,y將轉換矩陣中的所有子集重新命名，形成卜表所示的狀態(tài)轉換矩陣，即得到狀態(tài)ab02112222(注意：本題由于集合的命名和先后順序不同,可能最終結果不同。)3. 畫出編譯程序的總體結構圖，簡述各部分的主要

35、功能。解：編譯程序的總體框圖如下所示:（1）詞法分析器，又稱掃描器，它接受輸入的源程序，對源程序進行詞法分析，識別出一個個單詞符 號，其輸出結果是二元式（單詞種別，單詞自身的值）流。（2）語法分析器，對單詞符號串進行語法分析（根據(jù)語法規(guī)則進行推導或歸約），識別出程序中的各類 語法單位，最終判斷輸入串是否構成語法上正確的句子。（3）語義分析及中間代碼生成器，按照語義規(guī)則對語法分析器歸約出（或推導出）的語法單位進行語 義分析并把它們翻譯成一定形式的中間代碼。編譯程序可以根據(jù)不同的需要選擇不同的中間代碼形式，有 的編譯程序甚至沒有中間代碼形式，而直接生成目標代碼。（4）優(yōu)化器對中間代碼進行優(yōu)化處理。

36、一般最初生成的中間代碼執(zhí)行效率都比較低，因此要做中間代 碼的優(yōu)化，其過程實際上是對中間代碼進行等價替換，使程序在執(zhí)行時能更快，并占用更小的空間。（5）目標代碼生成器，把中間代碼翻譯成目標程序。中間代碼一般是一種與機器無關的表示形式，只 有把它再翻譯成與機器硬件直接相關的機器能識別的語言，即目標程序，才能在機器上運行。 al aSI bBB7對于文法G（S）：S - （L） I aS I aL - L，S I S畫出句型（S, （a）的語法樹。(2)寫出上述句型的所有短語、直接短語和句柄。解:句型(S,(a)的語法樹如下圖所示:(2) 從語法樹中可以找到(3分)短語：a; (a); S; S,(

37、a); (S, (a)直接短語：a; S句柄：s8.令文法 GN為GN: N-D|NDD-0|l|2|3|4|5|6|7|8|9 給出句子568的最左、最右推導。解：最左推導：N = ND 二 NDD = DDD = 5DD = 56D = 568 最右推導：N 二 ND 二 N8 = ND8= N68 = D68 = 5688. 己知文法 GA:A-aABl|aB-*Bb|d試給出與GA等價的LL文法GA；解：GA ： A-aArAz -AB1| Br -bE | e9. 試構造卞述文法的SLR(l)分析表。GA: A-aABl|aE-Eb|d解：拓廣文法(0) S-A(1) AaABl(2

38、) A-a(3) B-Bb(4) B-dFiist (A) =afollow (A) =#, dFiist (B) =dfollow (B) =1SLR (1)分析表如卞：abd1AB0S211ACC2S2R2R233S454R45S7S66R1R17R310.試構造下述文法的LL(1)分析表。GS: S- (L) |aLL, S|S解：消除左遞歸：G(S): S (L) | aLT SI；U T , SU| 構造FIRST集，如卞：(1) FIRST(S) = (, a(2) FIRST(L) = (, a(3) FIRST(LJ = 構造FOLLOW集如下：(1) FOLLOW(S) =

39、#, ,，)(2) FOLLOW(L) = )(3) FOLLOW(U) = )LL(1)分析表()a#sST(L)S T aLLT SULT SI；UI;譏U T ,SI/11己知文法 GS: S-aSbS|bSaS| e試證明GS是二義文法證明：該文法產生的語言是a的個數(shù)和b的個數(shù)相等的串的集合。該文法二義，例如句子abab有兩種不 同的最左推導。S =aSbS =abS =abaSbS =ababS =ababS =aSbS =abSaSbS =abaSbS =ababS =abab12.已知文法G：S f ( L I aL S , L | )判斷是不是LL (1)文法，如果是請構造文法

40、G的預測分析表，如果不是請說明理由?！窘狻?)求各非終結符的FISRT集和FOLLOW集：Fiist (S) = (, a FIRST(L) = ) u FIRST(S) = (,), a FOLLOW(S) = , # FOLLOW(L) = FOLLOW(S) = ,#FIRST( L)na=(PFIRST(S , L)n)=cp所以是LL (1)文法2)預測分析表:(asS- (LS- aLL S,LL S,LL)13 文法SAa|bAc|dc|bda A d23編譯原理復習題編譯原理復習題構造識別活前綴的DFA。請根據(jù)這個DFA來判斷該文法是不是SLR(l)文法并說明理由。Follow

41、(S )=#Follow(A)=a,c14 存在沖突且 Follow(A)A c= c17 存在沖突且 Follow(A)Aa= a 所以不是SLR文法14設有文法GS:SS*S|S+S| (S) |i該文法是否為二義文法,并說明理由？【解】該文法是二義文法，因為該文法存在句子i*i+i,該句子有兩棵不同的語法樹如圖所示。S3515構造卞面文法的LL (1)分析表。GD: D T TLT T int real【解】FIRST= FIRST(L)= FIRST(R)= FIRST(D 尸int idintreal FOLLOW(T)= id FOLLOW(L)= # s FOLLOW(R)= #

42、 real FOLLOW(D)=#因為 FIRST(int) A FIRST(real)=FIRST(, id R)CFOLLOW(R尸 所以是LL (1)文法，LL (1)分析表如下:intrealidDD T TLD - TLTT intT T realLL T id RRR T , id RR 16 給定文法S-aS bS|a/F面是拓廣文法和識別該文法所產生的活前綴的DFA。判斷該文法是否是SLR(l) 文法:如果是構造其SLR(l)分析表，如果不是請說明理由。(1) 將文法G(S)拓廣為G(S)：(O)S s(l) Sf aS S bSS a(2) 識別該文法所產生的活前綴的DFA如

43、圖1所示。L圖1識別活前綴的DFA【解】注意到狀態(tài)A存在移進-歸納”沖突，計算S的FOLLOW集合: FOLLOW(S)二#a n b CFOLLOW(R)=e可以采用SLR沖突消解法，得到如下的SLR分析表。從分析表可以看出，表中沒有沖突項，所以該文法是SLR(l)文法。表1 SLR分析表ACTIONGOTO狀態(tài)ab#S0SIS231SIS2r342SIS253acc4rl5r217.證明下面文法Sf AaAbIBbBa A-8B-8,是LL (1)文法，但不是SLR (1)文法。證明：(1) first (AaAb) =a first (BbBb) =b,有 first (AaAb) 0f

44、irst (BbBb) =+aPI +a(1) 將文法G(S)改寫為LL文法GJ(S)；(2) 寫出文法G，(S)的預測分析表。解：(1)消除左遞歸，文法變?yōu)椋篠-aPST SPSS J FPS，I P+aPI +a提取公共左因子，文法變?yōu)镚，(S)：S-aPS，l FPSS J *aPS? IeP+aPP JPI (2)計算每個非終結符的FIRST集和FOLLOW集:FIRST(S) = a, *FIRSTCSO = *, FIRST(P) = +FIRST(P) = +, FOLLOW(S) = # FOLLOWS) = # FOLLOW(P) =#FOLLOW(P5) = #構造該文法的

45、預測分析表如下:+a#Ss-aPSS-aPS?S5S J *aPS JwPP+aP5p.PJPP19. 己知文法G(S)：SaS I bS I a(I)構造識別該文法所產生的活前綴的DFA； 判斷該文法是LR(O)還是SLR(l),并構造所屬文法的LR分析表。解:(1)將文法G(S)拓廣為G，(S，)：(0) S JS(1) S-aS(2) S-bS(3) S-a識別該文法所產生的活前綴的DFA：(2)在狀態(tài)12存在“移近歸約”沖突，因此該文法不是LR(0)文法。計算S的FOLLOW集合:FOLLOW(S)= #h中的沖突用FOLLOW集合可以解決，所以該文法是SLR(l)文法。構造SLR(l

46、)分析表如下：狀態(tài)ACTIONGOTOabS0s2s311acc2s2s3r343s2s354rl51220. 構造文法S-AaAblBbBa A-s B-*,的預測分析表。答：first (S) =a, b,First (AaAb) =a, First (BbBa ) =b Follow (A) =a, bFollow (B) =a, bab$SS-AaAbSBbBaAAf A-SBB-*B-21.設有如下文法：GE： EEWT|TTT/F|F(E) |a|b|c w-+|-證明符號串a/(b-c)是句子。解答：有推導 E=T=T/F=F/F=a/F=a/(E) =a/(EWT) = a/(TWT)= a/(FWT)= a/(bWT)= a/(b-T)= a/(b-c),即從文法開始符號E能夠推導出a/(b-c),所以a/(b-c)是文法GE的句子。55對于下列文法