編譯原理第1.2.3.4章復(fù)習(xí)期末

1、 .編譯原理 第1、2章復(fù)習(xí)一、選擇題1、詞法分析所依據(jù)的是 B 。A. 語義規(guī)則B. 構(gòu)詞規(guī)則C. 語法規(guī)則D. 等價(jià)變換規(guī)則2、詞法分析器的輸出結(jié)果是C 。A. 單詞的種別編碼B. 單詞在符號表中的位置C. 單詞的種別編碼和自身值D. 單詞自身值3、正規(guī)式M1和M2等價(jià)是指 C 。A. M1和M2的狀態(tài)數(shù)相等B. M1和M2的有向弧條數(shù)相等C. M1和M2所識別的語言集相等 D. M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等4、C語言中表達(dá)式a+=1詞法分析后，能識別的單詞個(gè)數(shù)是 A 個(gè)。A. 5 B. 6 C. 7 D. 85、將識別各類單詞的有限自動(dòng)機(jī)合并后得到的有限自動(dòng)機(jī)是 A 。A. 可能是N

2、FA也可能是DFA B. 一定是DFAC. 一定是NFAD. 是最小的DFA6、中間代碼生成時(shí)所遵循的是 D 。 A語法規(guī)則B詞法規(guī)則 C語義規(guī)則D等價(jià)變換規(guī)則7、語法分析應(yīng)遵循 B 。 A語義規(guī)則B語法規(guī)則 C構(gòu)詞規(guī)則D等價(jià)變換規(guī)則8、編譯程序各階段的工作都涉及到 BC 。 A語法分析B表格管理C出錯(cuò)處理 D語義分析E詞法分析9、編譯過程中掃描器的任務(wù)包括 ABCDE (多選)：A. 按詞法規(guī)則分割單詞，識別出其屬性，并轉(zhuǎn)換成token串輸出；B. 刪除注釋、空格C. 行計(jì)數(shù)、列計(jì)數(shù)D. 發(fā)現(xiàn)并定位詞法錯(cuò)誤E. 建立符號表10、令=a,b，則上所有以b開頭，后跟若干個(gè)ab的字的全體對應(yīng)的正規(guī)

3、式為_ABCD_(多選)。A. b(ab)*B. b(ab)+C. (ba)*bD. (ba)+bE. b(a|b)11、將編譯程序分成若干個(gè)“遍”是為了 B 。 A提高程序的執(zhí)行效率 B使程序的結(jié)構(gòu)更加清晰 C利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率 D利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率12、 D 不可能是目標(biāo)代碼。 A匯編指令代碼B可重定位指令代碼 C絕對指令代碼D中間代碼13、使用 A 可以定義一個(gè)程序的意義。 A語義規(guī)則B詞法規(guī)則 C產(chǎn)生規(guī)則D詞法規(guī)則14、詞法分析器的輸入是 B 。 A單詞符號串B源程序 C語法單位D目標(biāo)程序15、狀態(tài)轉(zhuǎn)換圖（見圖）接受的字集為 D 。 0

4、60;1 0YXA. 以 0開頭的二進(jìn)制數(shù)組成的集合 B. 以0結(jié)尾的二進(jìn)制數(shù)組成的集合C. 含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合 D. 含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合二、填空題1、確定有限自動(dòng)機(jī)DFA是 NFA 的一個(gè)特例。2、若二個(gè)正規(guī)式所表示的 正規(guī)集 相同，則認(rèn)為二者是等價(jià)的。3、一個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可由 FA 所識別。4、編譯過程通?？煞譃?個(gè)階段，分別是 詞法分析 、語法分析 中間代碼生成 、代碼優(yōu)化和目標(biāo)代碼生成。5、確定有窮自動(dòng)機(jī)DFA的化簡，是將多余狀態(tài)消除而形成一個(gè)最小的等價(jià)的DFA?；啺ǎ?消除多余狀態(tài) 、 合并等價(jià)狀態(tài) 。三、判斷題1、一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅

5、有一個(gè)唯一終態(tài)。（ 錯(cuò) ）2、設(shè)r和s分別是正規(guī)式，則有L（r|s）=L(r)|L(s)。（ 對 ）3、自動(dòng)機(jī)M和M的狀態(tài)數(shù)不同，則二者必不等價(jià)。（ 錯(cuò) ）4、確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識別正規(guī)集。（ 對 ）5、對任何正規(guī)表達(dá)式e，都存在一個(gè)NFA M，滿足L(G)=L(e)。（ 對 ）編譯原理 第3、4章復(fù)習(xí)一、選擇題1、文法G：SxSx|y所識別的語言是 C 。A xyxB (xyx)*C xnyxn(n0)D x*yx*2、設(shè)G為算符優(yōu)先文法，G的任意終結(jié)符對a、b有以下關(guān)系成立 C 。A 若f(a)>g(b)，則a>bB若f(a)<g(b)，則a<

6、bC ab都不一定成立D ab一定成立3、如果文法G是無二義的，則它的任何句子 A 。A 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C 最左推導(dǎo)和最右推導(dǎo)必定相同EE + FE + T PT iP #<·+·>+<·i·># 句型P+T+i的語法及優(yōu)先關(guān)系D 可能存在兩個(gè)不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同4、由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號序列是 C 。A 短語B句柄C 句型D 句子5、文法G：EE+T|TTT*P|PP(E)|i則句型P+T+i的句柄和最左素短語為 B 。AP

7、+T和i B P和P+T C i和P+T+i DP和T 6、設(shè)文法為：SSA|AAa|b則對句子aba，下面 D 是規(guī)范推導(dǎo)。A SÞSAÞSAAÞAAAÞaAAÞabAÞabaB SÞSAÞSAAÞAAAÞAAaÞAbaÞabaC SÞSAÞSAAÞSAaÞSbaÞAbaÞabaD SÞSAÞSaÞSAaÞSbaÞAbaÞaba7、文法G：Sb|(T)TT

8、,S|S則FIRSTVT(T) C 。A b,(B b,)Cb,(,，Db,),，8、產(chǎn)生正規(guī)語言的文法為 D 。A 0型B 1型C 2型D 3型9、采用自上而下分析，必須 A 。A 消除左遞歸、消除回溯B 消除右遞歸C提取公共左因子10、在規(guī)范歸約中，用 B 來刻畫可歸約串。A 直接短語B 句柄C 最左素短語D 素短語11、規(guī)范歸約指 B 。A 最左推導(dǎo)的逆過程B 最右推導(dǎo)的逆過程C 規(guī)范推導(dǎo) D 最左歸約的逆過程12、若a為終結(jié)符，則A·a為 B 項(xiàng)目 A歸約B移進(jìn)C接受D待約13、若項(xiàng)目集Ik含有A·，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號aFOLLOW(A)時(shí)，才采取“A

9、·”動(dòng)作的一定是 D 。 ALALR文法BLR（0）文法CLR（1）文法DSLR（1）文法14、在LR（0）的ACTION子表中，如果某一行中存在標(biāo)記“rj”的欄，則 A 。 A該行必定填滿rjB該行未填滿rjC其他行也有rjDgoto子表中也有rj15、一個(gè) A 指明了在分析過程中的某時(shí)刻所能看到產(chǎn)生式多大一部分。 A活前綴B前綴C項(xiàng)目D項(xiàng)目集16、自上而下的語法分析方法是 B 。 A算符優(yōu)先分析法BLL（1）分析法CSLR（1）分析法DLR（0）分析法E. LALR（1）分析法17、中間代碼生成所依據(jù)的是 D 。A語法規(guī)則B詞法規(guī)則C語義規(guī)則D等價(jià)變換規(guī)則18、四元式之間的聯(lián)系是

10、通過 B 實(shí)現(xiàn)的。 A指示器B臨時(shí)變量C符號表D程序變量19、后綴式ab+cd+/可用表達(dá)式 B 來表示。Aa+b/c+dB(a+b)/(c+d)Ca+b/(c+d)Da+b+c/d20、表達(dá)式（AB）（CD）的逆波蘭表示為 B 。 A ABCDB ABCDC ABCDD ABCD21、四元式表示法的優(yōu)點(diǎn)為 C 。A不便于優(yōu)化處理，但便于表的更動(dòng)B不便于優(yōu)化處理，但節(jié)省存儲空間C便于優(yōu)化處理，也便于表的更動(dòng)D便于表的更動(dòng)，也節(jié)省存儲空間22、終結(jié)符具有 D 屬性。A傳遞B繼承C抽象D綜合 二、填空題1、對于一個(gè)文法，如果能夠構(gòu)造 LR分析表 。使得它的 每個(gè)入口 均是唯一確定的，則稱該文法為L

11、R文法。2、字的前綴是指該字的 任意首部 。3、每一項(xiàng)ACTIONS，a所規(guī)定的動(dòng)作包括 移進(jìn) 、歸約 、 接收 、出錯(cuò) 。4、對LR分析器來說，存在 LR(0)、 SLR(1) 、LR(1)、LALR(1)表的構(gòu)造方法。5、將識別 活前綴 的NFA確定化，使其成為以 項(xiàng)目集 為狀態(tài)的DFA，這個(gè)DFA就是建立 LR分析表 的基礎(chǔ)。6、A·稱為 歸約 項(xiàng)目；對文法開始符S·為 接收 項(xiàng)目；若a為終結(jié)符，則稱A·a為 移進(jìn) 項(xiàng)目；若B為非終結(jié)符，則稱A·B為 待約 項(xiàng)目。7、LR（1）分析法的名字中“L”表示 自左到右掃描輸入串 ，“R”表示最右推導(dǎo)的逆過

12、程，“1”表示 向前展望1個(gè)字符 。8、在條件、循環(huán) 結(jié)構(gòu)的語法制導(dǎo)翻譯中，采用拉鏈-回填技術(shù)。9、中間代碼有逆波蘭記號、樹形表示、三元式、四元式等形式，生成中間代碼主要是為了使 目標(biāo)代碼的優(yōu)化容易實(shí)現(xiàn) 。10、語法制導(dǎo)翻譯既可以用來產(chǎn)生 中間代碼 代碼，也可以用來產(chǎn)生 機(jī)器 指令，甚至可用來對輸入串進(jìn)行解釋執(zhí)行 。11、文法符號的屬性有兩種，一種稱為 綜合 ，另一種稱為 繼承 。12、后綴式abc-/所代表的表達(dá)式是 a/(b-c) ，表達(dá)式(a-b)*c可用后綴式 ab-c* 表示。13、在語法分析中，最常見的兩種方法是 top-down 分析法，另一是 bottom-up 分析法。14、采用 top-down 語法分析時(shí)，必須消除文法的左遞歸。15、Chomsky把文法分為 4 種類型，編譯器構(gòu)造中采用 2型 和 3型 文法，它