編譯原理第1、2、3、4章復(fù)習(xí)(期末)

1、9、編譯過程中掃描器的任務(wù)包括ABCDE (多選):編譯原理第1、2章復(fù)習(xí)2、選擇題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語言中表達(dá)式a+=1詞法分析后，能識別的單詞個數(shù)是A 個。5、 將識別各類單詞的有限自動機(jī)合并后得到的有限自動機(jī)是丄AA. 可能是NFA也可

2、能是DFAB. 定是 DFAC. 定是 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 詞法分析A. 按詞法規(guī)則分割單詞，識別出其屬性，并轉(zhuǎn)換成token串輸出;B. 刪除注釋、空格C. 行計(jì)數(shù)、列計(jì)數(shù)D. 發(fā)現(xiàn)并定位詞法錯誤E. 建立符號表10、令刀=a,b，則刀上所有以b開頭，后跟若干個ab的字的全體對應(yīng)的正規(guī)式為 _ABCD 多選)。C. (ba)*bA. b

3、(ab)*B. b(ab)+D. (ba)+bE. b(a|b)11、將編譯程序分成若干個“遍”是為了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可以定義一個程序的意義。B.詞法規(guī)則D.詞法規(guī)則B。B.源程序D.目標(biāo)程序A .語義規(guī)則C .產(chǎn)生規(guī)則14、詞法分析器的輸入是A .單詞符號串C .語法單位15、狀態(tài)轉(zhuǎn)換圖(見圖)接受的字集為 _D3、如果文法 G是無二義的，則它的任何句子a AC.含奇

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

5、的狀態(tài)數(shù)不同，則二者必不等價。(錯)4、確定的自動機(jī)以及不確定的自動機(jī)都能正確地識別正規(guī)集。(對)5、對任何正規(guī)表達(dá)式 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)，則 ab B.若 f(a)g(b)，則 abC. ab都不一定成立D. ab 一定成立A 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C. 最左推導(dǎo)和

6、最右推導(dǎo)必定相同D. 可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同A 短語B.句柄C.句型D.句子5、文法 G: E- E+T|TTT*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/I、E +|Tp# + 句型P+T+iE1+ FT PIi卜#的語法及優(yōu)先關(guān)系6 、設(shè)文法為：S- SA|AAt a|b則對句子aba,下面D是規(guī)范推導(dǎo)。A. S = SA： SAH AAA： aA ab仁 abaB. SA : SAA : AAA : AAa : A

7、ba : abaC. S 二 S比 SA& SAa : Sba : Aba : abaD. S= SA : Sa : SAa : Sba : Aba : aba7、文法 G: S- b| A (T)T- T,S|S貝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.直接短語B.句柄C.最左素短語D.素短語511

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

9、某時刻所能看到產(chǎn)生式多大一部分。A . n ABVA CDVC. ABVn CDVA21、四元式表示法的優(yōu)點(diǎn)為 C。A.不便于優(yōu)化處理，但便于表的更動B. An BVCDVAD. An BVA CDVB. 不便于優(yōu)化處理，但節(jié)省存儲空間C. 便于優(yōu)化處理，也便于表的更動D. 便于表的更動，也節(jié)省存儲空間A .活前綴B.前綴C.項(xiàng)目D.項(xiàng)目集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.等價變換規(guī)則18、四兀式之間的

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

11、LR、LALR表的構(gòu)造方法。5、 將識別 活前綴 的NFA確定化，使其成為以 項(xiàng)目集 為狀態(tài)的DFA這個DFA就 是建立LR分析表的基礎(chǔ)。6、 At a 稱為歸約項(xiàng)目;對文法開始符St a 為接收項(xiàng)目;若a為終結(jié)符， 則稱At a a 3為 移進(jìn) 項(xiàng)目；若B為非終結(jié)符，則稱 At a B3為 待約 項(xiàng)目。7、 LR (1)分析法的名字中“ L”表示 自左到右掃描輸入串，“ R表示最右推導(dǎo)的逆 過程,“ 1”表示向前展望1個字符。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語法分析時，必須消除文法的左遞歸。15、 Chomsky把文法分為4種類型，編譯器構(gòu)造中采用 2