編譯原理 第章復習期末

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

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

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

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

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

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

7、和i B P和P+T C i和P+T+i DP和T 6、設文法為：SSA|AAa|b則對句子aba，下面 D 是規(guī)范推導。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,S

8、|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 最左推導的逆過程B 最右推導的逆過程C 規(guī)范推導 D 最左歸約的逆過程12、若a為終結符，則A·a為 B 項目 A歸約B移進C接受D待約13、若項目集Ik含有A·，則在狀態(tài)k時，僅當面臨的輸入符號aFOLLOW(A)時，才采取“A&#

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

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

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

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