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

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

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

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

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

5、L(r)|L(s)。(對)3、 自動機M和M'的狀態(tài)數(shù)不同，則二者必不等價。(錯)4、確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。(對)5、對任何正規(guī)表達式 e,都存在一個 NFA M滿足L(G)=L(e)。(對)編譯原理第3、 4章復(fù)習(xí)一、選擇題1文法G:A xyxStxSx|y所識別的語言是 C。B. (xyx)*C. x nyxn(n > 0)D. x*yx2、設(shè)G為算符優(yōu)先文法，G的任意終結(jié)符對a、b有以下關(guān)系成立CA 若 f(a)>g(b)，則 a>b B.若 f(a)<g(b)，則 a<bC. ab都不一定成立D. ab 一定成立3、如

6、果文法 G是無二義的，則它的任何句子aAA 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C. 最左推導(dǎo)和最右推導(dǎo)必定相同D. 可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同A 短語B.句柄C.句型D.句子5、文法 G: E- E+T|TT- T*P|PP- (E)|i貝恂型P+T+i的句柄和最左素短語為B。4、由文法的開始符經(jīng) 0步或多步推導(dǎo)產(chǎn)生的文法符號序列是CA P+T 和 i B . P 和 P+TC. i 和 P+T+iE/IE +TIP#< + 句型P+T+iEI + FiT PIi卜< >#的語法及優(yōu)先關(guān)系6 、設(shè)文法為：

7、S- SA|AAt a|bASSASAAAAAaAAabAabaB.SSASAAAAAAAaAbaabaC.SSASAASAaSbaAbaabaD.SSASaSAaSbaAbaaba7、文法G:S b| A (T)TT,S|S則對句子aba,下面D 是規(guī)范推導(dǎo)。貝U FIRSTVT(T) _C。A b, A ,(B. b, A ,)C. b, A ,(, , D .b,A ,), , 8、產(chǎn)生正規(guī)語言的文法為_D_。A.0型B.1型C. 2型D. 3型9、米用自上而下分析，必須 _A。A.消除左遞歸、消除回溯B.消除右遞歸C.提取公共左因子10、 在規(guī)范歸約中，用 _B來刻畫可歸約串。A.直接

8、短語B.句柄C.最左素短語D.素短語11、規(guī)范歸約指巴_A.最左推導(dǎo)的逆過程B.最右推導(dǎo)的逆過程C.規(guī)范推導(dǎo)D.最左歸約的逆過程12、若a為終結(jié)符，則Aaa B為B項目A.歸約B.移進C.接受D.待約13、 若項目集Ik含有Aa，則在狀態(tài)k時，僅當(dāng)面臨的輸入符號 a FOLLOW(A寸，才采 取“ Aa ”動作的一定是衛(wèi)_。A . LALR文法B. LR ( 0)文法 C. LR (1)文法 D. SLR (1)文法14、 在LR( 0)的ACTION子表中，如果某一行中存在標(biāo)記“j 的欄，貝U上_。A .該行必定填滿rjB.該行未填滿rjC.其他行也有rjD. goto子表中也有門15、 一

9、個 A指明了在分析過程中的某時刻所能看到產(chǎn)生式多大一部分。A . n ABVA CDVC. ABVn CDVA21、四元式表示法的優(yōu)點為 C。A.不便于優(yōu)化處理，但便于表的更動C.便于優(yōu)化處理，也便于表的更動B. An BVCDVAD. An BVA CDVB.不便于優(yōu)化處理，但節(jié)省存儲空間D. 便于表的更動，也節(jié)省存儲空間A .活前綴B.前綴C.項目D.項目集16、自上而下的語法分析方法是B。A .算符優(yōu)先分析法B.LL (1)分析法C. SLR( 1)分析法D. LR ( 0)分析法E.LALR (1)分析法17、中間代碼生成所依據(jù)的是D。)A.語法規(guī)則B.詞法規(guī)則C.語義規(guī)則D.等價變換

10、規(guī)則18、四兀式之間的聯(lián)系是通過B實現(xiàn)的。A .指示器B.臨時變量C.符號表D.程序變量19、后綴式ab+cd+/可用表達式B來表示。A.a+b/c+dB. (a+b)/(c+d)C. a+b/(c+d)D. a+b+c/d20、表達式鬥 AV B)A( CVD)的逆波蘭表示為B。22、終結(jié)符具有_D_屬性。A.傳遞B.繼承C.抽象D.綜合二、填空題1 對于一個文法，如果能夠構(gòu)造LR分析表。使得它的 每個入口均是唯一確定的，則稱該文法為 LR文法。2、字的前綴是指該字的 任意首部 。3、 每一項 ACTIONS, a所規(guī)定的動作包括 移進 、歸約 、接收 、出錯 。4、 對LR分析器來說，存在

11、 LR(O)、SLR、LR、LALR表的構(gòu)造方法。5、 將識別 活前綴 的NFA確定化，使其成為以項目集 為狀態(tài)的DFA這個DFA就 是建立LR分析表 的基礎(chǔ)。6、Aa稱為歸約項目;對文法開始符S'fa為 接收 項目;若a為終結(jié)符， 則稱Aaa B為 移進 項目；若B為非終結(jié)符，則稱 AaB B為待約 項目。7、 LR (1)分析法的名字中“ L”表示 自左到右掃描輸入串，“ R'表示最右推導(dǎo)的逆 過程,“ 1”表示向前展望1個字符。8、 在條件、 循環(huán) 結(jié)構(gòu)的語法制導(dǎo)翻譯中，采用拉鏈-回填技術(shù)。9、中間代碼有逆波蘭記號、樹形表示、三元式、四元式等形式，生成中間代碼主要是為了使 目標(biāo)代碼的優(yōu)化容易實現(xiàn)。10、 語法制導(dǎo)翻譯既可以用來產(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種類型，編譯器構(gòu)造中采用 2