編譯原理第1234章復習期末知識分享

1、編譯原理第1、2章復習、選擇題1、詞法分析所依據(jù)的是 B 。A.語義規(guī)則B.構詞規(guī)則2、詞法分析器的輸出結果是 C。A.單詞的種別編碼B.C.單詞的種別編碼和自身值D.3、正規(guī)式M1和M2等價是指 C。A.M1和M2的狀態(tài)數(shù)相等B.C.語法規(guī)則D.等價變換規(guī)單詞在符號表中的位置單詞自身值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、將識別各類單詞的有限自動機合并后得到的有限自動機是AA. 可能是NFA也可能是DFAB. 一"定是

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

3、)。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)轉(zhuǎn)換圖(見圖)接受的字集為D 。A.以0開頭的二進

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

5、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: SH>xSx|y所識別的語言是 C。A xyx B. (xyx)*C. x nyxn(n > 0) D. x*yx*2、設G為算符優(yōu)先文法，G的任意終結符對a、b有以下關系成立 CA 若 f(a)>g(b),則 a>b B.若 f(a)<g(b),則 a<bC. a-b都不一定成

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

7、句子aba,下面D 是規(guī)范推導。B.C.D.7、文法G:SASASASASAASAASAAAAA aAAAAA AAaSAa SbaabAAbaAbaSa SAa Sba AbaSf b| A (T)abaabaabaabaT-T,S|S貝U FIRSTVT(T) C。A b, A ,(B. b, A ,)C. b, A ,(, , b,A,), , 8、產(chǎn)生正規(guī)語言的文法為A. 0型B. 1型C.D. 3型9、采用自上而下分析,必須 A 。A.消除左遞歸、消除回溯B.消除右遞歸C.提取公共左因子10、在規(guī)范歸約中，用B 來刻畫可歸約串。11、規(guī)范歸約指BA.最左推導的逆過程B.最右推導的逆過

8、程C.規(guī)范推導D.最左歸約的逆過程12、若a為終結符，則A-” a3為 B 項目A .歸約B.移進C.接受D.待約13、若項目集Ik含有Af” ，則在狀態(tài)k時，僅當面臨的輸入符號 aCFOLLOW(A)才采 取“A一” ”動作的一定是 D。A . LALR文法B. LR (0)文法 C. LR (1)文法 D. SLR (1)文法14、在LR (0)的ACTION?表中，如果某一彳T中存在標記“ rj的欄，則 /。A .該行必定填滿rjB.該行未填滿rjC.其他彳T也有rjD. goto子表中也有門15、一個 A指明了在分析過程中的某時刻所能看到產(chǎn)生式多大一部分。A .活前綴16、自上而下的語

9、法分析方法是A .算符優(yōu)先分析法D. LR (0)分析法17、中間代碼生成所依據(jù)的是A.語法規(guī)則B,前綴C.項目B 。B. LL (1)分析法E. LALR (1)分析法D。B.詞法規(guī)則C.語義規(guī)則D.項目集C. SLR (1)分析法D.等價變換規(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、表達式 3 AV B) A ( CV D)的逆波蘭表示為 BA . r ABV A CDVC. AB Vn CDV A2

10、1、四元式表示法的優(yōu)點為 C。A.不便于優(yōu)化處理，但便于表的更動B. A r BVCDV AD. Ar BV A CDVB.不便于優(yōu)化處理，但節(jié)省存儲空間C.便于優(yōu)化處理，也便于表的更動D.便于表的更動，也節(jié)省存儲空間22、終結符具有_D_屬性。A.傳遞B.繼承C.抽象D.綜合二、填空題1、對于一個文法，如果能夠構造LR分析表 。使得它的 每個入口均是唯一確定的，則稱該文法為LR文法。2、字的前綴是指該字的任意首部。3、每一項 ACTIONS, a所規(guī)定的動作包括移進 、歸約 、接收 、出錯 。4、對LR分析器來說，存在 LR(0)、SLR(1)、LR(1)、LALR(1)表的構造方法。5、將

11、識別 活前綴 的NFA確定化，使其成為以 項目集 為狀態(tài)的DFA這個DFA就 是建立LR分析表的基礎。6、A-” 稱為歸約項目;對文法開始符S' 一” 為 接收 項目;若a為終結符， 則稱A> a a 3為 移進 項目;若B為非終結符，則稱 A> a B 3為待約 項目。7、LR (1)分析法的名字中“ L”表示 自左到右掃描輸入串，"R'表示最右推導的逆過程,“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 種類型，編譯器構造中采用