編譯原理第1234章復(fù)習(xí)期末知識(shí)分享

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

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

3、)。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 .絕對(duì)指令代碼D.中間代碼13、使用 A 可以定義一個(gè)程序的意義。A.語義規(guī)則B.詞法規(guī)則C.產(chǎn)生規(guī)則D.詞法規(guī)則14、詞法分析器的輸入是 B。A.單詞符號(hào)串B.源程序C.語法單位D.目標(biāo)程序15、狀態(tài)轉(zhuǎn)換圖(見圖)接受的字集為D 。A.以0開頭的二進(jìn)

4、制數(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 所識(shí)別。4、編譯過程通?？煞譃?個(gè)階段，分別是 詞法分析、語法分析中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成。5、確定有窮自動(dòng)機(jī) DFA的化簡(jiǎn)，是將多余狀態(tài)消除而形成一個(gè)最小的等價(jià)的DFA化簡(jiǎn)包括：消除多余狀態(tài)、合并等價(jià)狀態(tài)。三、判斷題1、一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一終態(tài)。(錯(cuò))2、設(shè)r和s分別是正規(guī)式,則有 L (r|

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

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

7、句子aba,下面D 是規(guī)范推導(dǎo)。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.最左推導(dǎo)的逆過程B.最右推導(dǎo)的逆過

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

9、法分析方法是A .算符優(yōu)先分析法D. LR (0)分析法17、中間代碼生成所依據(jù)的是A.語法規(guī)則B,前綴C.項(xiàng)目B 。B. LL (1)分析法E. LALR (1)分析法D。B.詞法規(guī)則C.語義規(guī)則D.項(xiàng)目集C. SLR (1)分析法D.等價(jià)變換規(guī)則18、四元式之間的聯(lián)系是通過B實(shí)現(xiàn)的。A .指示器B.臨時(shí)變量C.符號(hào)表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á)式 3 AV B) A ( CV D)的逆波蘭表示為 BA . r ABV A CDVC. AB Vn CDV A2

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

11、識(shí)別 活前綴 的NFA確定化，使其成為以 項(xiàng)目集 為狀態(tài)的DFA這個(gè)DFA就 是建立LR分析表的基礎(chǔ)。6、A-” 稱為歸約項(xiàng)目;對(duì)文法開始符S' 一” 為 接收 項(xiàng)目;若a為終結(jié)符， 則稱A> a a 3為 移進(jìn) 項(xiàng)目;若B為非終結(jié)符，則稱 A> a B 3為待約 項(xiàng)目。7、LR (1)分析法的名字中“ L”表示 自左到右掃描輸入串，"R'表示最右推導(dǎo)的逆過程,“1 ”表示向前展望1個(gè)字符。8、在條件、 循環(huán) 結(jié)構(gòu)的語法制導(dǎo)翻譯中，采用拉鏈 -回填技術(shù)。9、中間代碼有逆波蘭記號(hào)、樹形表示、三元式、四元式等形式,生成中間代碼主要是 為了使 目標(biāo)代碼的優(yōu)化容易實(shí)現(xiàn)。10、語法制導(dǎo)翻譯既可以用來產(chǎn)生中間代碼 代碼,也可以用來產(chǎn)生機(jī)器指令，甚至可用來對(duì)輸入串進(jìn)行解釋執(zhí)行。11、文法符號(hào)的屬性有兩種，一種稱為綜合 ，另一種稱為繼承 。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)造中采用