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

1、編譯原理一、單選題1、將編譯程序分為若干個(gè)“遍”是為了（）。B A. 提高程序的執(zhí)行效率B. 使程序的結(jié)構(gòu)更加清晰C. 利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率D. 利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2、構(gòu)造編譯程序應(yīng)掌握（）。D A. 源程序 B.目標(biāo)語言C.編譯方法 D.以上三項(xiàng)都是3、變量應(yīng)當(dāng)（）。CA. 持有左值 B. 持有右值C. 既持有左值又持有右值D. 既不持有左值也不持有右值4、編譯程序絕大多數(shù)時(shí)間花在（）上。DA. 出錯(cuò)處理 B.詞法分析C.目標(biāo)代碼生成 D.管理表格5、（）不可能是目標(biāo)代碼。DA. 匯編指令代碼 B.可重定位指令代碼C.絕對指令代碼 D.中間代碼6、 編

2、譯程序是對（）。DA. 匯編程序的翻譯 B.高級語言程序的解釋執(zhí)行C.機(jī)器語言的執(zhí)行 D.高級語言的翻譯7、 正規(guī)式M1和M2等價(jià)是指（）。CA. M1和M2的狀態(tài)數(shù)相等 B.M1和M2的有象弧條數(shù)相等C.M1和M2所識別的語言集相等 D.M1和M2狀態(tài)數(shù)和有象弧條數(shù)相等8、 如果文法G是無二義的，則它的任何句子（）。AA. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同。B. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能相同。C. 最左推導(dǎo)和最右推導(dǎo)必定相同。D. 可能存在兩個(gè)不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同。9、 文法G：SS+T|TTT*P|PP(S)|i句型P+T+i的短語有（）BA. i，P+T

3、 B. P，P+T，i，P+T +i B.P+T + i D. P，P+T，i10、 產(chǎn)生正規(guī)語言的文法為（）。DA.0型B.1型C.2型D.3型11、 文法G：Sb|(T)TTS|S則FIRSTVT(T)=() CA. b，( B.b，)C.b，(， D.b，)，12、 給定文法：AbA | cc，下面的符號串中，為該文法句子的是（）。 Accbcbcbcbccbccbccbbbcc可選項(xiàng)有：A. B.C.D.13、 采用自上而下分析，必須（）。CA. 消除左遞歸B.消除右遞歸C.消除回溯 D.提取公共左因子14、 由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號序列是（）。CA. 短語B.句柄

4、C.句型D.句子15、 后綴式ab+cd+/可用表達(dá)式（）來表示。 BA. a+b/c+d B.(a+b)/(c+d) C.a+b/(c+d) D.a+b+c/d16、 語法分析器則可以發(fā)現(xiàn)源程序中的（）。DA. 語義錯(cuò)誤B.語法和語義錯(cuò)誤C.錯(cuò)誤并矯正D.語法錯(cuò)誤17、 在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是（）。BA. 非終極符集 B.終極符集 D.字母表 D.狀態(tài)集18、四種形式語言文法中，1型文法又稱為（）。CA. 短語結(jié)構(gòu)文法B.前后文無關(guān)文法C.前后文有關(guān)文法D.正規(guī)文法19、 優(yōu)化可生成（）的目標(biāo)代碼。DA. 運(yùn)行時(shí)間較短B.占用存儲空間較小C.

5、運(yùn)行時(shí)間短但占用內(nèi)存空間大D.運(yùn)行時(shí)間短且占用內(nèi)存空間小20、四元式之間的聯(lián)系是通過（）實(shí)現(xiàn)的。BA. 指示器B.臨時(shí)變量C.符號表D.程序變量2、 多選題1、如果在文法G中存在一個(gè)句子，當(dāng)其滿足下列條件（ BCD ）之一時(shí)，則稱該文法是二義文法。A.其最左推導(dǎo)和最右推導(dǎo)相同  B.該句子有兩個(gè)不同的最左推導(dǎo)C.該句子有兩個(gè)不同的最右推導(dǎo) D.該句子有兩棵不同的語法樹E.該句子對應(yīng)的語法樹唯一2、下面（BCD）語法制導(dǎo)翻譯中，采用拉鏈回填技術(shù)。A、賦值語句    B、布爾表達(dá)式的計(jì)算 C、條件語句   D

6、、循環(huán)語句3、一般程序設(shè)計(jì)語言的定義都涉及到（ ABC ）3個(gè)方面。A、 語法 B、語義 C、語用 D、程序基本符號的確定4、程序語言一般分為（ A ）和（ B ）。A高級語言 B低級語言 C專用程序語言 D通用程序語言5、編譯程序工作時(shí)，通常有（ABCD ）階段。A、詞法分析 B、語法分析 C、中間代碼生成 D、語義檢查 E、目標(biāo)代碼生成6、編譯過程中，語法分析的任務(wù)是（ BCD ）。A、分析單詞是怎樣構(gòu)成的   B、分析單詞是如何構(gòu)成語句和說明的C、分析語句和說明是如何構(gòu)成程序的 D、分析程序的結(jié)構(gòu)

7、7、語法分析的常用方法有 （ AB ）。A、自頂向下 B、自底向上 C、自左向右 D、自右向左   8、程序設(shè)計(jì)語言常見的數(shù)據(jù)類型有：（ABCD）  A、數(shù)值型數(shù)據(jù) B、邏輯數(shù)據(jù) C、字符數(shù)據(jù) D、指針類型9、構(gòu)造編譯程序應(yīng)掌握（ABC）。A、源程序 B、目標(biāo)語言   C、編譯方法 D、以上都不是10、編譯程序前三個(gè)階段完成的工作是（ABC）A、詞法分析 B、語法分析C、語義分析和中間代碼生成 D、代碼優(yōu)化11、一個(gè)上下文無關(guān)文法G 包括四個(gè)組成部分：一組終結(jié)符，一組非終結(jié)符，以及（B

8、C）。A、一組字符串 B、一組產(chǎn)生式 C、一個(gè)開始符號 D、一個(gè)文法12、描述一個(gè)語言的文法是（C、D）。 A、唯一的 B、不唯一的  C、可能唯一 D、也可能不唯一13、設(shè)有文法GI：II1|I0|Ia|Ic|a|b|c下列符號串中是該文法句子的有（BCD）。 A、ab0  B、a0c01   C、aaa     D、bc10  14、運(yùn)行階段的存儲組織與管理的目的是（CD）。A、提高編譯程序的運(yùn)行速度 B、節(jié)省編譯程序的存儲空間 C

9、、提高目標(biāo)程序的運(yùn)行速度 D、為運(yùn)行階段的存儲分配做準(zhǔn)備 15、已知文法GE：ETE E+TE  TFT  T*FT  F（E）id 求：FOLLOW（F）=（ D ），F(xiàn)IRST（T）=（ B ）A、*，+ B、*， C、+,#，）D、*，+，#，） E、#，） F、*，+，#，id16、面向機(jī)器語言的特點(diǎn)是（ ABC  ）。A、程序的執(zhí)行效率高 B、編制效率低 C、可讀性差 D、可讀性強(qiáng)17、編譯程序使用（ AB ）區(qū)別標(biāo)識符的作用域。A、說明標(biāo)識符的過程 B、函數(shù)的靜態(tài)層次C、函數(shù)的動態(tài)層

10、次 D、標(biāo)識符的行號18、詞法分析器的輸出結(jié)果是（ AD ） A、單詞的種別編碼 B、單詞在符號表中的位置 C、單詞的長度 D、單詞自身值19、優(yōu)化可生成（ AD ）的目標(biāo)代碼。 A、運(yùn)行時(shí)間較短 B、占用存儲空間較大 C、運(yùn)行時(shí)間短且占用內(nèi)存空間大  D、占用存儲空間小22、編譯程序各階段的工作都涉及到（ BC ） A、語法分析 B、表格管理 C、出錯(cuò)處理 D、語義分析 F、詞法分析3、 填空題1編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代

11、碼 生成,代碼優(yōu)化等幾個(gè)基本階段,同時(shí)還會伴有_表格處理_和 _出錯(cuò)處理_。  2若源程序是用高級語言編寫的,_目標(biāo)程序_是機(jī)器語言程序或匯編程序, 則其翻譯程序稱為 _編譯程序_ 。  3編譯方式與解釋方式的根本區(qū)別在于_是否生成目標(biāo)代碼_。  4對編譯程序而言,輸入數(shù)據(jù)是_源程序_, 輸出結(jié)果是_目標(biāo)程序_。 5產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。  6語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法 7設(shè)

12、0;G 是一個(gè)給定的文法，S 是文法的開始符號，如果 S->x( 其中 xVT*), 則稱 x 是文 法的一個(gè)_句子_。 8遞歸下降法不允許任一非終極符是直接_左_遞歸的。  9.常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。  10在使用高級語言編程時(shí),首先可通過編譯程序發(fā)現(xiàn)源程序的全部_語法_錯(cuò)誤和語義的部分錯(cuò)誤。 11一個(gè)句型中的最左簡單短語稱為該句型的_句柄_。   12一個(gè)典型的編譯程序中，不僅包括_詞

13、法分析_、_語法分析_、_中間代碼生成_、 代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。 13 從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。   14語法分析是依據(jù)語言的_語法_規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的_語義_規(guī) 進(jìn)行的。  15產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。 16計(jì)算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。 17局部優(yōu)化是在_基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。 18詞法分析基于_正則

14、_文法進(jìn)行，即識別的單詞是該類文法的句子。  19語法分析基于_上下文無關(guān)_文法進(jìn)行，即識別的是該類文法的句子。語法分析的有效 工具是_語法樹_。  20一個(gè)文法能用有窮多個(gè)規(guī)則描述無窮的符號串集合（語言）是因?yàn)槲姆ㄖ写嬖谟衉遞歸 _定義的規(guī)則。 四、名詞解釋（1）2型文法（上下文無關(guān)文法）若文法G=（VN，VT，P，S）中的每一條規(guī)則的形式為A，其中AVN，(VNVT)*，則稱G是2型文法。（2） 二義性文法如果一個(gè)文法存在某個(gè)句子對應(yīng)兩課不同的語法樹，則稱這個(gè)文法是二義性文法。（3） 有窮自動機(jī)是具有離散輸入與輸出系統(tǒng)的

15、一種抽象數(shù)學(xué)模型。（4） 算符文法設(shè)有文法G，若G中沒有形如UVW的規(guī)則，其中V和W為非終結(jié)符，則稱G為算符文法。（5） 素短語素短語是指這樣一種短語，它至少包含一個(gè)終結(jié)符，并且除自身之外，不再包含其他任何更小的素短語。（6） 語法制導(dǎo)翻譯法在語法分析過程中，根據(jù)相應(yīng)文法的每一規(guī)則所對應(yīng)的語義子程序進(jìn)行翻譯的方法。（7） 基本塊指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是其中的第一個(gè)語句，出口就是其中的最后一個(gè)語句。（8） 句柄一個(gè)句型的最左直接短語稱為該句型的句柄。（9） 待用信息如果在一個(gè)基本塊中，四元式i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，

16、則稱j是四元式i的變量A的待用信息。（10） 局部優(yōu)化局限于基本塊范圍的優(yōu)化稱。5、 應(yīng)用題1. 編譯過程的5個(gè)階段是什么？第1階段：詞法分析第2階段：語法分析第3階段: 詞義分析與中間代碼產(chǎn)生第4階段：代碼優(yōu)化第5階段：目標(biāo)代碼生成2. 請給出編譯程序的結(jié)構(gòu)框圖。3. 設(shè)有文法GA:A>a|b|e|Aa|Ae|A0|A1（1）試問VT 和VN是由哪些符號組成的？VN=AVT=a,b,e,0,1（2）下列符號串a(chǎn),ab0,a0e01,0a,11,eee是否為該文法的句子？a,a0e01,eee是該文法句子。4. 證明下面的文法是二義性的。S>iSeS|iS|i5.目標(biāo)代碼有哪幾種形

17、式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問題？ 目標(biāo)代碼通常采用三種形式：機(jī)器語言，匯編語言，待裝配機(jī)器語言模塊。  應(yīng)著重考慮的問題： (1)如何使生成的目標(biāo)代碼較短； (2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；  (3)如何充分利用指令系統(tǒng)的特點(diǎn)。6.基本的優(yōu)化方法有哪幾種？ 刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫傳播和刪除無用賦值。7.構(gòu)造下列正規(guī)式相應(yīng)的DFA（用狀態(tài)轉(zhuǎn)換圖表示）（1）1（0|1）*1（2）0*10*10*10*1（3）letter(letter|digit)*8.給出下述文法所對應(yīng)的正規(guī)式。S>aAA>bA|aB|bB&g