編譯原理復(fù)習(xí)題給學(xué)生

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

2、的字集為 。d 圖1-1xy0011a. 以0開頭的二進(jìn)制數(shù)組成的集合 b. 以0結(jié)尾的二進(jìn)制數(shù)組成的集合 c. 含奇數(shù)個0的二進(jìn)制數(shù)組成的集合 d. 含偶數(shù)個0的二進(jìn)制數(shù)組成的集合 2詞法分析器的輸出結(jié)果是 。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上的正閉包運(yùn)算產(chǎn)生的是：（a）a. b.a c.aa d.ab8稱有限自動機(jī)a1和a2等價是指_。daa1和a2都是定義在一個字母表上的有限自動機(jī)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為非終結(jié)符，則a·b為 項目。da. 歸約 b. 移進(jìn) c. 接受 d. 待約3如果文法g是無二義的，則它的任何句子 。 aa. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同b. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同c. 最左推導(dǎo)和最右推導(dǎo)必定相同d. 可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同4下列動作中，不是自下而上分析動作的是： 。ba. 移進(jìn) b. 展開c. 接受 d. 報錯6若a為終結(jié)符，則a·a為 項目。

5、ba. 歸約 b. 移進(jìn) 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. 移進(jìn) d. 報錯10若a為非終結(jié)符，則a· 為 項目。aa. 歸約 b. 移進(jìn) 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步）推導(dǎo)產(chǎn)生的文法符號序列稱為_。ba語言 b句型 c句子 d句柄14在自上而下的語法分析中，應(yīng)從 開始分析。ca句型 b句子 c文法開始符號d句柄15一個文法g，若_，則稱它是ll（1）文法。cag中不含左遞歸 bg無二義性 cg的ll（1）分析表中不含多重定義的條目 dg中產(chǎn)生式不含左公因子16項目ss. 為 。da.歸約項目 b.移進(jìn)項目c.待約項目 d.接受項目17. 語法分析器的輸入是： 。aa. token序列 b. 源程序c. 目標(biāo)程序 d. 符號表18. 在lr（0）的action表中，如果某行中存在標(biāo)記為“rj”的欄，則： 。 aa. 該

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

8、” b. 該行未必填滿“rj”c. 其他行可能也有“rj” d. goto表中也可能有“rj”23. 一個 指明了在lr分析過程中的某個時刻所能看到產(chǎn)生式多大一部分。da. 活前綴 b. 前綴c. 歸約活前綴 d. 項目24.若狀態(tài)k含有項目“a.”，且僅當(dāng)輸入符號afollow(a)時，才用規(guī)則“a ”歸約的語法分析方法是 。dalalr分析法 blr(0)分析法 clr(1)分析法 dslr(1)分析法25設(shè)有文法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分析表中的轉(zhuǎn)移表（g

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

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

11、bef2中間代碼生成時所依據(jù)的是 。ca詞法規(guī)則 b語法規(guī)則 c語義規(guī)則 d等價變換規(guī)則3 -a-(b*c/(c-d)+(-b)*a)的逆波蘭表示是 。(代表后綴式中的求負(fù)運(yùn)算符) ca. abc*cd-ba*+/- b. abc*cd-ba*+/-c. abc*cd-/ba*+- d. abc*/cd-ba*+-4有文法g及其語法制導(dǎo)翻譯如下所示（語義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符）： 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及其語法制導(dǎo)翻譯如下所示（語義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符）： 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)點(diǎn)為 。 aa. 采用間接碼表，便于優(yōu)化處理 b. 節(jié)省存儲空間，不便于表的修改c. 便于優(yōu)化處理，節(jié)省存

13、儲空間 d. 節(jié)省存儲空間，不便于優(yōu)化處理7文法gs及其語法制導(dǎo)翻譯定義如下： 產(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)系是通過 _實(shí)現(xiàn)的。ba指示器 b臨時變量 c符號表 d程序變量9表達(dá)式（ab）（cd）的逆波蘭表示為 。baabcd babcdcabcd dabcd10表達(dá)式a+b+c+d的逆波蘭表示為 。baa+bc+d

14、+ bab+c+d+cab+cd+ dabc+d+11.有文法g及其語法制導(dǎo)翻譯如下所示（語義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符）： 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表達(dá)式a+b+c的逆波蘭表示為 。baa+bc+ bab+c+c+abc+ dabc+13. 文法gs及其語法制導(dǎo)翻譯定義如下： 產(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有一語法制導(dǎo)翻譯定義如下：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有一語法制導(dǎo)翻譯定義如下，其中+表示符號連接運(yùn)算：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.在編譯過程中，如果遇到錯誤應(yīng)該 。ca. 把錯誤理解成局部的錯誤 b. 對錯誤在局部范圍內(nèi)進(jìn)行糾正，繼續(xù)向下分析c. 當(dāng)發(fā)現(xiàn)錯誤時，跳過錯誤所在的語法單位繼續(xù)分析下去d. 當(dāng)發(fā)現(xiàn)錯誤時立即停止編譯，待用戶改正錯誤后再繼續(xù)編譯二、填空題概述部分：1編譯程序的開發(fā)常常采用自編譯、 交叉編譯 、 自展 和移植等技術(shù)實(shí)現(xiàn)。2解釋程序和編譯程序的區(qū)別在于 是否生成目標(biāo)程序 。3如果編譯程序生成的目標(biāo)程序是匯編語言程序，則源程序的執(zhí)行分為3個階段： 編譯階段 、 匯編階段 和 運(yùn)行階段 。4編譯程序工作過程中，第一階段輸入是 源程序 ，最后階段的輸出為 目標(biāo)程序 。

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

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

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

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

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)轉(zhuǎn)換（goto）表 等兩個子表。17關(guān)于非終結(jié)符a的直接左遞歸產(chǎn)生式：aa|，其中、是任意的符號串且不以a開頭，則可以將a的產(chǎn)生式改寫為右遞歸的形式為： aa , aa| 。1

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

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

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

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

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

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

29、使用有限自動機(jī)可以實(shí)現(xiàn)單詞的識別。（ ）31一個非確定的有限自動機(jī)nfa可以通過多條路徑識別同一個符號串。（ ）32最小化的dfa所識別接受的正規(guī)集最小。（ × ）33一個語言（如c語言）的句子是有窮的。（ × ）34ll（1）方法又稱為預(yù)測分析方法。（ ）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. 上下文有關(guān)文法5. 對lr分析表的構(gòu)造，有可能存在的動作沖突有：（ad）a. 移進(jìn)/歸約沖突 b. 移進(jìn)/移進(jìn)沖

31、突c. 歸約沖突 d. 歸約/歸約沖突e. 移進(jìn)沖突6. 一個編譯器可能有的階段為（abcde）a. 詞法分析 b. 語法分析c. 語義分析 d. 中間代碼生成e. 目標(biāo)代碼生成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. “或”運(yùn)算服從交換律 b. “或”運(yùn)算服從結(jié)合律c. “連接”運(yùn)算服從交換律 d. “連接”運(yùn)算服從結(jié)合律e. “連接”運(yùn)算可對“或”運(yùn)算進(jìn)行

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. 移進(jìn) b.

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

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

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

37、取，整個編譯過程都在不斷和表格打交道。（7）出錯處理程序?qū)Τ霈F(xiàn)在源程序中的錯誤進(jìn)行處理。如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤，把有關(guān)錯誤信息報告給用戶。編譯程序的各個階段都有可能發(fā)現(xiàn)錯誤，出錯處理程序要對發(fā)現(xiàn)的錯誤進(jìn)行處理、記錄，并反映給用戶。4構(gòu)造一個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 因?yàn)?0 = 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，其對應(yīng)的dfa如下圖所示：001105寫出c語言標(biāo)識符集（字母或下劃線開頭的由字母、數(shù)字、下劃線構(gòu)成的串）的正規(guī)式。解答：用d表示數(shù)字0-9，用l表示字母a-z|a-z，則c語言標(biāo)識符的正規(guī)式為： （l|_）（

39、l|d|_）*語法分析部分：6構(gòu)造一文法，使其描述的語言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、的最左、最右推導(dǎo)。解：最左推導(dǎo)：n nd ndd ddd 5dd 56d 568最右推導(dǎo)：n nd n8 nd8 n68 d68 5688已知文法ga: aaabl|abbb|d試給出與ga等價的ll(1)文法ga；解：ga：aaaaabl | bdbbbb| 9試構(gòu)造下述文法的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. 試構(gòu)造下述文法的ll(1)分析表。gs: s（l）|all，s|s解：消除左遞歸：g(s): s à (l) | al à sll à , sl| 構(gòu)造first集，如下：（1）first(s) = (, a（2）first(l) = (, a（3）first(l) = , 構(gòu)造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有兩種不同的最左推導(dǎo)。 sasbsabsabasbsababsabab sasbsabsasbsabasbsababsabab12已知文法： s ( l | a l s , l | )判斷是不是ll（1）文法，如果是請構(gòu)造文法 的預(yù)測分析表，如果不是請說明理由?！窘狻?1）求各非終結(jié)符的 fisrt 集和 follow 集：first（s）= (, a first(l) = ） È first(s) = (, ), a follow(s) = , # follow(l) = foll