編譯原理復習題給學生

1、真誠為您提供優(yōu)質參考資料，若有不當之處，請指正。一、單項選擇題概述部分1構造編譯程序應掌握 。d a. 源程序 b. 目標語言 c. 編譯方法 d. 以上三項都是2編譯程序絕大多數(shù)時間花在 上。da. 出錯處理 b. 詞法分析 c. 目標代碼生成 d. 表格管理3編譯程序是對 。da. 匯編程序的翻譯 b. 高級語言程序的解釋執(zhí)行c. 機器語言的執(zhí)行 d. 高級語言的翻譯4. 將編譯程序分成若干“遍”，是為了 。ba. 提高程序的執(zhí)行效率 b. 使程序的結構更為清晰c 利用有限的機器內存并提高機器的執(zhí)行效率d. 利用有限的機器內存但降低了機器的執(zhí)行效率詞法分析部分1dfa m(見圖1-1)接受

2、的字集為 。d 圖1-1xy0011a. 以0開頭的二進制數(shù)組成的集合 b. 以0結尾的二進制數(shù)組成的集合 c. 含奇數(shù)個0的二進制數(shù)組成的集合 d. 含偶數(shù)個0的二進制數(shù)組成的集合 2詞法分析器的輸出結果是 。ca. 單詞的種別編碼 b. 單詞在符號表中的位置c. 單詞的種別編碼和自身值 d. 單詞自身值3正規(guī)式m1和m2等價是指 。ca. m1和m2的狀態(tài)數(shù)相等 b. m1和m2的有向邊條數(shù)相等c. m1和m2所識別的語言集相等 d. m1和m2狀態(tài)數(shù)和有向邊條數(shù)相等4詞法分析器的加工對象是 。 c a中間代碼 b單詞 c源程序 d元程序5同正規(guī)式（a|b）*等價的正規(guī)式為 。d a(a|

3、b)+ ba*|b* c(ab)* d(a*|b*)+6. 兩個dfa等價是指： 。 da. 這兩個dfa的狀態(tài)數(shù)相同b. 這兩個dfa的狀態(tài)數(shù)和有向弧條數(shù)都相等c. 這兩個dfa的有向弧條數(shù)相等d. 這兩個dfa接受的語言相同7. 下列符號串不可以由符號集sa,b上的正閉包運算產(chǎn)生的是：（a）a. b.a c.aa d.ab8稱有限自動機a1和a2等價是指_。daa1和a2都是定義在一個字母表上的有限自動機ba1和a2狀態(tài)數(shù)和有向邊數(shù)相等ca1和a2狀態(tài)數(shù)或有向邊數(shù)相等da1和a2所能識別的字符串集合相等9同正規(guī)式（a|b）+等價的正規(guī)式是_。ba（a|b）* b（a|b）（a|b）* c（

4、ab）*（ab） d（a|b）|（a|b）*語法分析1在規(guī)范歸約中，用 來刻畫可歸約串。 ba. 直接短語 b. 句柄 c. 最左素短語 d. 素短語2若b為非終結符，則a·b為 項目。da. 歸約 b. 移進 c. 接受 d. 待約3如果文法g是無二義的，則它的任何句子 。 aa. 最左推導和最右推導對應的語法樹必定相同b. 最左推導和最右推導對應的語法樹可能不同c. 最左推導和最右推導必定相同d. 可能存在兩個不同的最左推導，但它們對應的語法樹相同4下列動作中，不是自下而上分析動作的是： 。ba. 移進 b. 展開c. 接受 d. 報錯6若a為終結符，則a·a為 項目。

5、ba. 歸約 b. 移進 c. 接受 d. 待約7語法分析時所依據(jù)的是 。aa. 語法規(guī)則 b. 詞法規(guī)則 c. 語義規(guī)則 d. 等價變換規(guī)則8文法g：sxsx|y所識別的語言是 。c a. xyx b. (xyx)* c. xnyxn (n0) d. x*yx*9下列動作中，不是自上而下分析動作的是： 。ca. 匹配 b. 展開c. 移進 d. 報錯10若a為非終結符，則a· 為 項目。aa. 歸約 b. 移進 c. 接受 d. 待約11文法g：sxsx| xs|y所識別的語言是 。 a a. xmyxn(mn0) b. (xyx)* c. xnyxn(n0) d. x*yx*13

6、由文法的開始符號出發(fā)經(jīng)過若干步（包括0步）推導產(chǎn)生的文法符號序列稱為_。ba語言 b句型 c句子 d句柄14在自上而下的語法分析中，應從 開始分析。ca句型 b句子 c文法開始符號d句柄15一個文法g，若_，則稱它是ll（1）文法。cag中不含左遞歸 bg無二義性 cg的ll（1）分析表中不含多重定義的條目 dg中產(chǎn)生式不含左公因子16項目ss. 為 。da.歸約項目 b.移進項目c.待約項目 d.接受項目17. 語法分析器的輸入是： 。aa. token序列 b. 源程序c. 目標程序 d. 符號表18. 在lr（0）的action表中，如果某行中存在標記為“rj”的欄，則： 。 aa. 該

7、行必定填滿“rj” b. 該行未必填滿“rj”c. 其他行可能也有“rj” d. goto表中也可能有“rj”19. lr分析過程中棧內存儲的是 。 aa. 活前綴 b. 前綴c. 歸約活前綴 d. 項目20.文法g：s x xs | y 所識別的語言是 。 daxxyn b(xxy) n cxxnyx d(xx)ny21.若狀態(tài)k含有項目“a.”，對任意非終結符a，都用規(guī)則“a ”歸約的語法分析方法是 。balalr分析法 blr(0)分析法 clr(1)分析法 dslr(1)分析法22. 在slr（1）的action表中，如果某行中存在標記為“rj”的欄，則： 。ba. 該行必定填滿“rj

8、” b. 該行未必填滿“rj”c. 其他行可能也有“rj” d. goto表中也可能有“rj”23. 一個 指明了在lr分析過程中的某個時刻所能看到產(chǎn)生式多大一部分。da. 活前綴 b. 前綴c. 歸約活前綴 d. 項目24.若狀態(tài)k含有項目“a.”，且僅當輸入符號afollow(a)時，才用規(guī)則“a ”歸約的語法分析方法是 。dalalr分析法 blr(0)分析法 clr(1)分析法 dslr(1)分析法25設有文法gt:tt*f|fffp|pp(t)|a該文法句型t*p(t*f)的句柄是下列符號串 。c a.（t*f） b. t*f c. p d. p(t*f)26lr分析表中的轉移表（g

9、oto）是以 作為列標題的。ba終結符 b非終結符 c終結符或非終結符 d表示狀態(tài)的整形數(shù)27編譯程序的語法分析器必須輸出的信息是 。 a a語法錯誤信息 b語法規(guī)則信息c語法分析過程 d語句序列28下列項目中為可移進項目的是 。c aee . bl. cl.-l dfl*f.29lr分析表中的動作表（action）是以 作為列標題的。da終結符 b非終結符c終結符或非終結符 d終結符和結束符#30下列項目中為可歸約項目的是 。bae.e bl. cl-.l dfl*.f33lr分析器的核心部分是一張分析表，該表由_組成。daaction表 bgoto表c預測分析表 daction表和goto

10、表 34在遞歸下降子程序方法中，若文法存在左遞歸，則會使分析過程產(chǎn)生_ _。da回溯 b非法調用 c有限次調用 d無限循環(huán) 35最左簡單子樹的葉結點，自左至右排列組成句型的_。ca短語 b句型 c句柄 d間接短語36由文法的開始符號出發(fā)經(jīng)過若干步（包括0步）推導產(chǎn)生的文法符號序列中，如果只含有終結符，則文法符號序列稱為_。ca語言 b句型 c句子 d句柄37ll（1）分析法中“1”的含義是在輸入串中查看一個輸入符號，其目的是_。ca確定最左推導 b確定句柄 c確定使用哪一個產(chǎn)生式進行展開 d確定是否推導語義分析1.表達式（ab）（ef）的逆波蘭表示為 。baabef babefcabef da

11、bef2中間代碼生成時所依據(jù)的是 。ca詞法規(guī)則 b語法規(guī)則 c語義規(guī)則 d等價變換規(guī)則3 -a-(b*c/(c-d)+(-b)*a)的逆波蘭表示是 。(代表后綴式中的求負運算符) ca. abc*cd-ba*+/- b. abc*cd-ba*+/-c. abc*cd-/ba*+- d. abc*/cd-ba*+-4有文法g及其語法制導翻譯如下所示（語義規(guī)則中的*和+分別是常規(guī)意義下的算術運算符）： ee(1) t e.val = e(1).val * t.val et e.val = t.val tt(1)# n t.val = t(1).val + n.val t n t.val = n.

12、val則分析句子1 2 3 # 4其值為 。 c a. 10 b. 34 c. 14 d.545有文法g及其語法制導翻譯如下所示（語義規(guī)則中的*和+分別是常規(guī)意義下的算術運算符）： ee(1) t e.val = e(1).val * t.val et e.val = t.val tt(1)# n t.val = t(1).val + n.val t n t.val = n.val 則分析句子2 3 # 4其值為 。 c a. 10 b. 21 c. 14 d. 246間接三元式表示法的優(yōu)點為 。 aa. 采用間接碼表，便于優(yōu)化處理 b. 節(jié)省存儲空間，不便于表的修改c. 便于優(yōu)化處理，節(jié)省存

13、儲空間 d. 節(jié)省存儲空間，不便于優(yōu)化處理7文法gs及其語法制導翻譯定義如下： 產(chǎn)生式語義動作 s sprint(s.num) s (l)s.num = l.num +1s as.num = 0 l l(1), sl.num = l(1).num + s.numl s l.num = s.num若輸入為(a,(a)，且采用自底向上的分析方法，則輸出為 。ca0b1c2d48四元式之間的聯(lián)系是通過 _實現(xiàn)的。ba指示器 b臨時變量 c符號表 d程序變量9表達式（ab）（cd）的逆波蘭表示為 。baabcd babcdcabcd dabcd10表達式a+b+c+d的逆波蘭表示為 。baa+bc+d

14、+ bab+c+d+cab+cd+ dabc+d+11.有文法g及其語法制導翻譯如下所示（語義規(guī)則中的*和+分別是常規(guī)意義下的算術運算符）： ee(1) t e.val = e(1).val * t.val et e.val = t.val tt(1)# n t.val = t(1).val + n.val t n t.val = n.val則分析句子3 3 # 4其值為 。b a. 10 b. 21 c. 14 d. 2412表達式a+b+c的逆波蘭表示為 。baa+bc+ bab+c+c+abc+ dabc+13. 文法gs及其語法制導翻譯定義如下： 產(chǎn)生式語義動作 s sprint(s.

15、num) s (l)s.num = l.num +1s a s.num = 0 l l(1), sl.num = l(1).num + s.numl s l.num = s.num若輸入為(a, a)，且采用自底向上的分析方法，則輸出為 。ba0 b1c2 d414有一語法制導翻譯定義如下：sbab print “1”a（b print “2”aa print “3”baa) print “4”若輸入序列為b（a（a（aa）b，且采用自底向上的分析方法，則輸出序列為 。ba32224441 b34242421c12424243 d3444221215賦值語句x:=-(a+b)/(c-d)-(a

16、+b*c)的逆波蘭表示是 。ca. xab+cd-/-bc*a+-:=b. xab+/cd-bc*a+-:=c. xab+-cd-/ a bc* +-:=d. xab+cd-/abc* +-:=16有一語法制導翻譯定義如下，其中+表示符號連接運算：sb print b.versba b.vers=abb b.vers=bbba b.vers=a+b.versbbb b.vers=b+b.vers若輸入序列為abab，且采用自底向上的分析方法，則輸出序列為 。daaabb babab cbbaa dbaba17編譯程序不能檢查、處理的錯誤是程序中的_。ba靜態(tài)語義檢查 b動態(tài)語義檢查 c語法錯誤

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

18、5編譯過程通?？煞譃?個階段 詞法分析階段 、 語法分析階段 、 語義分析和中間代碼生成階段 、優(yōu)化階段和目標代碼生成階段。6如果編譯階段生成的目標程序是某特定計算機系統(tǒng)的機器代碼程序，則源程序的執(zhí)行分為兩大階段： 編譯階段 和 運行階段 。7對編譯程序而言，輸入數(shù)據(jù)是 源程序 ，輸出結果是 目標程序 。8貫穿于編譯程始終的工作有 符號表處理 和出錯處理。詞法分析部分：1詞法分析的工作是將源程序中的 字符串 變換成 單詞符號流 的過程，所遵循的是語言的 構詞規(guī)則 。2若兩個正規(guī)式所表示的 正規(guī)集 相同，則認為二者是等價的。3若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者是 等價 的。4正規(guī)式r1和

19、r2等價是指_表示相同的正規(guī)集 。5詞法分析器的輸入是源程序字符串，輸出結構是 二元式（單詞種別， 單詞自身的值） 。詞法分析所遵循的是語言的 構詞 規(guī)則。6確定的有限自動機是一個五元組，包含的五個元分別是：狀態(tài)集合、 字母表、初態(tài)、終態(tài)集、狀態(tài)轉換函數(shù)集合 。7有限自動機是更一般化的狀態(tài)轉換圖，它分為 確定的有限自動機dfa 和 非確定的有限自動機nfa 兩種。8nfa和dfa的區(qū)別主要有兩點：其一是 nfa可以有若干個初始狀態(tài)，而dfa僅有一個初始狀態(tài) ；其二是 nfa的狀態(tài)轉換函數(shù)f不是單值函數(shù)，而是一個多值函數(shù) 。語法分析部分：（基本概念、ll（1）、lr（0）、slr（1）、遞歸下降

20、子程序）1 語法分析的方法通常分為兩類： 自上而下分析方法 和 自下而上分析方法 。2文法中的終結符集和非終結符集的交集是 空集 。3一個句型的最左直接短語稱為該句型的_句柄_。4規(guī)范歸約是 最右推導 的逆過程。5自下而上語法分析中分析器的動作有_移進 、_歸約 、_接受_ 、_報錯 _。6自上而下語法分析中分析器的動作有_匹配終結符_、_展開非終結符_、_分析成功、報錯_。7常用的自上而下語法分析方法有遞歸下降子程序方法和預測分析表方法（ll（1）方法）。8常用的自下而上語法分析方法有算符優(yōu)先分析法和lr分析法。9一個ll(1)分析器由 一張ll(1)分析表（預測分析表） 、 一個先進后出分

21、析棧 和一個 控制程序（表驅動程序）組成。10一個lr分析器由 分析棧 、 分析表 和總控程序三個部分組成。11lr(0)分析法的名字中，“l(fā)”表示 自左至右分析輸入串 ，“r”表示 采用最右推導的逆過程即最左歸約 ?！?”表示 向右查看0個字符 。12ll(1)分析法中，第一個l的含義是 從左到右掃描輸入串 ；第二個l的含義是 分析過程中采用最左推導 ；“1”的含義是 只需向右查看一個符號就可以決定如何推導 。13lr(1)文法的含義是：l表明_自左至右掃描輸入串_，r表明_采用最右推導的逆過程（最左歸約）方法進行分析_。14一個上下文無關文法是ll(1)文法的充分必要條件是：對每一個非終結

22、符a的任何兩個不同產(chǎn)生式a|，有下面的條件成立：（1） first()first() = Ø ；（2）假若，則有 first() follow(a) = Ø 。15對于ll（1）文法中的任何產(chǎn)生式a|，則需要滿足_first(_)first()= 、_若_=>*,則_ first(_) _follow(a)=_ _。16lr分析器的核心部分是一張分析表，該表包括 動作（action）表 和 狀態(tài)轉換（goto）表 等兩個子表。17關于非終結符a的直接左遞歸產(chǎn)生式：aa|，其中、是任意的符號串且不以a開頭，則可以將a的產(chǎn)生式改寫為右遞歸的形式為： aa , aa| 。1

23、8在消除回溯，提取公共左因子時，關于a的產(chǎn)生式a 1 | 2 | | i | i+1 | | j，可以改寫為： a a | i+1 | | j ， a 1 | |i 。19設gs 是一文法，如果符號串x是從識別符號推導出來的，即有x，則稱x是文法gs的_句型_，若x僅由終結符號組成，即，則稱x為文法gs的_句子 。20已知文法gs:set|rt tdr| rdr| da|bd求first(s)=e，d，a，b，_；follow(d)=_d，# 。語義處理部分：1文法符號的屬性有兩種，一種稱為 繼承屬性 ，另一種稱為 綜合屬性 。2編譯過程中，常見的中間語言形式有 逆波蘭表示法 、 抽象語法樹

24、、 三元式 、 四元式 。3語法制導翻譯的方法就是為每個產(chǎn)生式配上一個 翻譯子程序（語義動作或語義子程序） ，并在語法分析的同時執(zhí)行它們。4編譯過程中，常見的中間語言形式有 逆波蘭表示法 、 抽象語法樹 、 三元式 、 四元式 。6文法符號的屬性有兩種，一種稱為 繼承屬性 ，另一種稱為 綜合屬性 。7四元式之間的聯(lián)系是通過 臨時變量 實現(xiàn)的。8在屬性文法中，終結符只有_綜合 屬性。10語法制導翻譯的方法就是為每個產(chǎn)生式配上一個 翻譯子程序（語義動作或語義子程序） ，并在語法分析的同時執(zhí)行它們。11目前較常見的語言語義的描述形式是_屬性文法_，并使用_語法制導翻譯 方法完成對語法成分的翻譯。（優(yōu)

25、化、存儲、錯誤管理）1.代碼優(yōu)化的含義是：對代碼進行 等價變換 ，使得變換后的代碼具有更高的 時間效率 和 空間效率。2.按照優(yōu)化對象所涉及的程序范圍，優(yōu)化分為 局部優(yōu)化 、 循環(huán)優(yōu)化 和 全局優(yōu)化 。3.基本塊，是指程序中 順序執(zhí)行的語句序列 ，其中只有一個 入口 和一個 出口 。4.從編譯角度看，分配目標程序數(shù)據(jù)空間的基本策略有： 靜態(tài)分配策略 、 棧式動態(tài)分配策略 和堆式動態(tài)分配策略 。三、判斷題1設r和s分別為正規(guī)式，則有l(wèi)(r|s) = l(r) | l(s).。( × )2一個文法的所有句型的集合形成該文法所能接受的語言。( × )3語法分析之所以采用上下文無關

26、文法是因為它的描述能力最強。( × )4由于lr(0)分析表構造簡單，所以它的描述能力強，適用面寬；lr(1)分析表因構造復雜而描述能力弱，適用面窄。( × )5逆波蘭表示法表示表達式時無需使用括號。( )6自動機m和m的狀態(tài)個數(shù)不同，則二者必不等價。( × )7ll(1)文法一定不含左遞歸和二義性。( )8所有l(wèi)r分析器的總控程序都是一樣的，只是分析表各有不同。( )9無論是三元式表示還是間接三元式表示的中間代碼，其三元式在三元式表中的位置一旦確定就很難改變。( )10三地址語句類似于匯編語言代碼，可以看成中間代碼的一種抽象形式。( )11最左推導也被稱為規(guī)范推

27、導。（× ）12運算對象排列的先后順序在后綴式和中綴式中不同。（ × ）13出現(xiàn)在移進-歸約分析器棧中的內容被稱為文法g的活前綴。（ ）14lr方法可以分析含有左遞歸的文法。（ ）15三元式的編號具有雙重含義，既代表此三元式，又代表三元式存放的結果。（ ）16語義規(guī)則中的屬性有兩種：綜合屬性與繼承屬性。（ ）17移進-歸約分析器的格局中棧的內容一般是文法符號與狀態(tài)。（ ）18由于遞歸下降子程序方法較ll（1）方法簡單，因此它要求文法不必是ll（1）文法。（ × ）19四元式的編號具有雙重含義，既代表此四元式，又代表四元式存放的結果。（ × ）20用高級語

28、言編寫的源程序必須經(jīng)過編譯，產(chǎn)生目標程序后才能運行。（ × ）21源程序到目標程序的變換是等價變換，即兩者結構不同，但語義是一致的。（ ）22對于任何一個正規(guī)式e，都存在一個dfa a，使得l（e）=l（a）。（ ）23最小化的dfa，它的狀態(tài)數(shù)最小。（ ）24nfa的確定化算法具有消除邊的功能。（ ）25每個非終結符產(chǎn)生的終結符號串都是該語言的子集。（ × ）26一個語言的文法是不唯一的。（ ）27語法錯誤校正的目的是為了把錯誤改正過來。（ × ）28源程序和目標程序是等價關系。（ ）29編譯程序中錯誤處理的任務是對檢查出的錯誤進行修改。（ × ）30

29、使用有限自動機可以實現(xiàn)單詞的識別。（ ）31一個非確定的有限自動機nfa可以通過多條路徑識別同一個符號串。（ ）32最小化的dfa所識別接受的正規(guī)集最小。（ × ）33一個語言（如c語言）的句子是有窮的。（ × ）34ll（1）方法又稱為預測分析方法。（ ）35一個ll（1）文法是無二義和無回溯方法。（ ）36語法分析器可以檢查出程序中的所有錯誤。（ × ）37lr分析法是自上而下的語法分析方法。（ × ）三、多項選擇題1. 編譯器的各個階段的工作都涉及到（ae）a. 表格處理 b. 詞法分析c. 語法分析 d. 語義分析 e. 出錯處理2. 令sa,b

30、，則s上的符號串的全體可用下面的正規(guī)式表示。（abe）a. (a|b)* b. (a*|b*)*c. (a|b)+ d. (ab)* e. (a*b*)*3. 自上而下的分析方法有：（ad）a. 遞歸下降分析法 b. lr（0）分析法c. lalr（1）分析法 d. ll（1）分析法e. slr（1）分析法4.文法g：gs：scdabba cacabaab cbcbbbbb adadc bdbdd aabd是（a）。a. 0型文法 b. 1型文法c. 2型文法 d. 3型文法 e. 上下文有關文法5. 對lr分析表的構造，有可能存在的動作沖突有：（ad）a. 移進/歸約沖突 b. 移進/移進沖

31、突c. 歸約沖突 d. 歸約/歸約沖突e. 移進沖突6. 一個編譯器可能有的階段為（abcde）a. 詞法分析 b. 語法分析c. 語義分析 d. 中間代碼生成e. 目標代碼生成7 令sa,b，則s上的所有以b開頭，后跟若干個（可為0個）ab的符號串的全體可用下面的正規(guī)式表示。（ab）a.b (ab)* b. (ba)*b c. b(a|b)+ d. (ba)+b e. b (a|b)*8. 自下而上的分析方法有：（bce）a. 遞歸下降分析法 b. lr（0）分析法c. lalr（1）分析法 d. ll（1）分析法e. slr（1）分析法9. 一般來說，編譯器可分為前端和后端，下列編譯階段可

32、被劃分為編譯的前端的有：（abcde）a. 詞法分析 b. 語法分析c. 語義分析 d. 中間代碼生成 e. 中間代碼優(yōu)化10令sa,b，則s上的符號串的全體可用下面的正規(guī)式表示。（abe）a. (a|b)* b. (a*|b*)*c. (a|b)+ d. (ab)* e. (a*b*)*11下列符號串是符號集sa,b上的正規(guī)式的有：（abcde）a. b.a c.ab d.(aba) (aba)e.abab12正規(guī)式服從的代數(shù)規(guī)律有：（abde）a. “或”運算服從交換律 b. “或”運算服從結合律c. “連接”運算服從交換律 d. “連接”運算服從結合律e. “連接”運算可對“或”運算進行

33、分配13 令sa,b，則s上的所有以b開頭，后跟若干個（可為0個）ab的符號串的全體可用下面的正規(guī)式表示。（ab）a.b (ab)* b. (ba)*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.

34、接受 c. 歸約d. 出錯 e. 待約五簡答題1構造正規(guī)表達式(a|b)*|aa)*b的nfa。解：2設m=(x,y, a,b, f, x, y)為一非確定的有限自動機，其中f定義如下： f(x,a)=x,y fx,b=y f(y,a)= fy,b=x,y試構造相應的確定有限自動機m。解：對照自動機的定義m=(s,f,so,z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此m是一非確定有限自動機。先畫出nfa m相應的狀態(tài)圖，如下圖所示。用子集法構造狀態(tài)轉換矩陣，如下表所示。 將轉換矩陣中的所有子集重新命名，形成下表所示的狀態(tài)轉換矩陣，即得到m=(0,1,2,a,b,f,0,1,

35、2)，m狀態(tài)轉換圖如下圖所示。（注意：本題由于集合的命名和先后順序不同，可能最終結果不同。）3畫出編譯程序的總體結構圖，簡述各部分的主要功能。解：編譯程序的總體框圖如下所示： （1）詞法分析器，又稱掃描器，它接受輸入的源程序，對源程序進行詞法分析，識別出一個個單詞符號，其輸出結果是二元式(單詞種別，單詞自身的值)流。（2）語法分析器，對單詞符號串進行語法分析（根據(jù)語法規(guī)則進行推導或歸約），識別出程序中的各類語法單位，最終判斷輸入串是否構成語法上正確的句子。（3）語義分析及中間代碼生成器，按照語義規(guī)則對語法分析器歸約出（或推導出）的語法單位進行語義分析并把它們翻譯成一定形式的中間代碼。編譯程序可

36、以根據(jù)不同的需要選擇不同的中間代碼形式，有的編譯程序甚至沒有中間代碼形式，而直接生成目標代碼。（4）優(yōu)化器對中間代碼進行優(yōu)化處理。一般最初生成的中間代碼執(zhí)行效率都比較低，因此要做中間代碼的優(yōu)化，其過程實際上是對中間代碼進行等價替換，使程序在執(zhí)行時能更快，并占用更小的空間。（5）目標代碼生成器，把中間代碼翻譯成目標程序。中間代碼一般是一種與機器無關的表示形式，只有把它再翻譯成與機器硬件直接相關的機器能識別的語言，即目標程序，才能在機器上運行。（6）表格管理模塊保持一系列的表格，登記源程序的各類信息和編譯各階段的進展狀況。編譯程序各個階段所產(chǎn)生的中間結果都記錄在表格中，所需要的信息也大多從表格中獲

37、取，整個編譯過程都在不斷和表格打交道。（7）出錯處理程序對出現(xiàn)在源程序中的錯誤進行處理。如果源程序有錯誤，編譯程序應設法發(fā)現(xiàn)錯誤，把有關錯誤信息報告給用戶。編譯程序的各個階段都有可能發(fā)現(xiàn)錯誤，出錯處理程序要對發(fā)現(xiàn)的錯誤進行處理、記錄，并反映給用戶。4構造一個dfa，它接受 = 0, 1上所有滿足如下條件的字符串：每個1后面都有0直接跟在右邊。解：（1）0*(0|10)*0* 或者 (0|10)* （2）nfa （2分）x0y01020103子集法確定化 ii0i1x, 0, 1, 3, y0, 1, 3, y20, 1, 3, y0, 1, 3, y221, 3, y-1, 3, y1, 3,

38、 y2重新命名狀態(tài)，即得：s0112322334-443 最小化 首先分為終態(tài)集和非終態(tài)集 3 1, 2, 4 因為10 = 2 20 = 2 40 = 4 狀態(tài)均屬于集合1, 2, 4，所以對于輸入符號0不能區(qū)分開1，2，4三個狀態(tài)；11 = 3 21 = 3 41 = 3狀態(tài)均屬于集合3，所以對于輸入符號1也不能區(qū)分開1，2，4三個狀態(tài)；因此最終的狀態(tài)劃分即為: 3 1, 2, 4，其對應的dfa如下圖所示：001105寫出c語言標識符集（字母或下劃線開頭的由字母、數(shù)字、下劃線構成的串）的正規(guī)式。解答：用d表示數(shù)字0-9，用l表示字母a-z|a-z，則c語言標識符的正規(guī)式為： （l|_）（

39、l|d|_）*語法分析部分：6構造一文法，使其描述的語言l = | (a, b)*，且中含有相同個數(shù)的a和b。解：s | aa|bba b| bs| aaab a| as| bbb7對于文法g(s)：s (l) | as | al l, s | s(1) 畫出句型(s, (a)的語法樹。(2) 寫出上述句型的所有短語、直接短語和句柄。解：(1) 句型(s, (a)的語法樹如下圖所示： (2) 從語法樹中可以找到（3分）短語：a; (a); s; s,(a); (s, (a)直接短語： a; s 句柄： s8令文法gn為 gn: nd|nd d0|1|2|3|4|5|6|7|8|9給出句子568

40、的最左、最右推導。解：最左推導：n nd ndd ddd 5dd 56d 568最右推導：n nd n8 nd8 n68 d68 5688已知文法ga: aaabl|abbb|d試給出與ga等價的ll(1)文法ga；解：ga：aaaaabl | bdbbbb| 9試構造下述文法的slr(1)分析表。ga: aaabl|abbb|d解：拓廣文法 （0）sa（1）aaabl（2）aa（3）bbb（4）bdfirst（a）=afollow（a）=#，dfirst（b）=dfollow（b）=lslr（1）分析表如下：abdl#ab0s211acc2s2r2r233s454r45s7s66r1r17r

41、310. 試構造下述文法的ll(1)分析表。gs: s（l）|all，s|s解：消除左遞歸：g(s): s à (l) | al à sll à , sl| 構造first集，如下：（1）first(s) = (, a（2）first(l) = (, a（3）first(l) = , 構造follow集如下：（1）follow(s) = #, , )（2）follow(l) = )（3）follow(l) = )ll(1)分析表()a,#ss à (l)s à all à sll à slll à l à

42、 ,sl11已知文法gs: sasbs|bsas|試證明gs是二義文法證明： 該文法產(chǎn)生的語言是a的個數(shù)和b的個數(shù)相等的串的集合。該文法二義，例如句子abab有兩種不同的最左推導。 sasbsabsabasbsababsabab sasbsabsasbsabasbsababsabab12已知文法： s ( l | a l s , l | )判斷是不是ll（1）文法，如果是請構造文法 的預測分析表，如果不是請說明理由?！窘狻?1）求各非終結符的 fisrt 集和 follow 集：first（s）= (, a first(l) = ） È first(s) = (, ), a follow(s) = , # follow(l) = foll