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

一、單選題1、將編譯程序分為若干個(gè)“遍”是為了（）。B提高程序的執(zhí)行效率使程序的結(jié)構(gòu)更加清晰利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2、構(gòu)造編譯程序應(yīng)掌握（）。D源程序B.目標(biāo)語(yǔ)言C.編譯方法D.以上三項(xiàng)都是3、變量應(yīng)當(dāng)（）。C持有左值持有右值既持有左值又持有右值既不持有左值也不持有右值4、編譯程序絕大多數(shù)時(shí)間花在（）上。D出錯(cuò)處理B.詞法分析C.目標(biāo)代碼生成D.管理表格5、（）不可能是目標(biāo)代碼。D匯編指令代碼B.可重定位指令代碼C.絕對(duì)指令代碼D.中間代碼編譯程序是對(duì)（）。D匯編程序的翻譯B.高級(jí)語(yǔ)言程序的解釋執(zhí)行如果文法G是無(wú)二義的，則它的任何句子（）。A最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同。最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能相同。最左推導(dǎo)和最右推導(dǎo)必定相同。可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同。文法G：S→S+T|TT→T*P|PP→(S)|i句型P+T+i的短語(yǔ)有（）Bi，P+TB.P，P+T，i，P+T+iB.P+T+iD.P，P+T，i產(chǎn)生正規(guī)語(yǔ)言的文法為（）。DA.0型B.1型C.2型D.3型文法G：S→b|?|(T)T→T?S|S則FIRSTVT(T)=()C{b，?，(}B.{b，?，)}C.{b，?，(，?}D.{b，?，)，?}給定文法：A→bA|cc，下面的符號(hào)串中，為該文法句子的是（）。A采用自上而下分析，必須（）。C消除左遞歸B.消除右遞歸C.消除回溯D.提取公共左因子由文法的開(kāi)始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是（）。C短語(yǔ)B.句柄C.句型D.句子后綴式ab+cd+/可用表達(dá)式（）來(lái)表示。Ba+b/c+dB.(a+b)/(c+d)C.a+b/(c+d)D.a+b+c/d語(yǔ)法分析器則可以發(fā)現(xiàn)源程序中的（）。D語(yǔ)義錯(cuò)誤B.語(yǔ)法和語(yǔ)義錯(cuò)誤C.錯(cuò)誤并矯正D.語(yǔ)法錯(cuò)誤在語(yǔ)法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是（）。B非終極符集B.終極符集D.字母表D.狀態(tài)集18、四種形式語(yǔ)言文法中，1型文法又稱為（）。C短語(yǔ)結(jié)構(gòu)文法B.前后文無(wú)關(guān)文法C.前后文有關(guān)文法D.正規(guī)文法優(yōu)化可生成（）的目標(biāo)代碼。D運(yùn)行時(shí)間較短B.占用存儲(chǔ)空間較小C.運(yùn)行時(shí)間短但占用內(nèi)存空間大D.運(yùn)行時(shí)間短且占用內(nèi)存空間小20、四元式之間的聯(lián)系是通過(guò)（）實(shí)現(xiàn)的。B指示器B.臨時(shí)變量C.符號(hào)表D.程序變量是二義文法。A.其最左推導(dǎo)和最右推導(dǎo)相同該句子有兩個(gè)不同的最左推導(dǎo)C.該句子有兩個(gè)不同的最右推導(dǎo)E.該句子對(duì)應(yīng)的語(yǔ)法樹(shù)唯一2、下面（BCDA、賦值語(yǔ)句布爾表達(dá)式的計(jì)算條件語(yǔ)句循環(huán)語(yǔ)句3、一般程序設(shè)計(jì)語(yǔ)言的定義都涉及到（

ABC）3個(gè)方面。語(yǔ)法B、語(yǔ)義C、D、4、程序語(yǔ)言一般分為（

A

）和（

B

）。A高級(jí)語(yǔ)言B低級(jí)語(yǔ)言C專用程序語(yǔ)言D通用程序語(yǔ)言5、編譯程序工作時(shí)，通常有（ABCD）階段。A、詞法分析B、C、中間代碼生成D、語(yǔ)義檢查E、目標(biāo)代碼生成6、。A、分析單詞是怎樣構(gòu)成的

C、分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的7、語(yǔ)法分析的常用方法有。A、自頂向下

B、自底向上

C、自左向右D、自右向左8、程序設(shè)計(jì)語(yǔ)言常見(jiàn)的數(shù)據(jù)類(lèi)型有：（ABCD）

A、數(shù)值型數(shù)據(jù)B、邏輯數(shù)據(jù)C、字符數(shù)據(jù)D、指針類(lèi)型9、（ABC）。A、源程序B、C、編譯方法D以上都不是10、編譯程序前三個(gè)階段完成的工作是（ABC）A、以及（BC）。A、一組字符串

B、一組產(chǎn)生式

C、一個(gè)開(kāi)始符號(hào)文法12、描述一個(gè)語(yǔ)言的文法是（C、D）。A、唯一的B、不唯一的

C、可能唯一D、也可能不唯一13、G[I]：I→I1|I0|Ia|Ic|a|b|c下列符號(hào)串中是該文法句子的有（BCD）。A、ab0

B、a0c01

C、D、14、運(yùn)行階段的存儲(chǔ)組織與管理的目的是（CD）。A、提高編譯程序的運(yùn)行速度B、C、提高目標(biāo)程序的運(yùn)行速度D、為運(yùn)行階段的存儲(chǔ)分配做準(zhǔn)備15、已知文法G[E]：E→TE’

E’→+TE’∣ε

T→FT’

T’→*FT’∣ε

F→（E求：（F）=（D），=（B）A、｛*，+｝B、｛*，ε｝、｛+,#，）｝D、｛*，+，#，）｝E、｛#，）｝、｛*，+，#，id｝16、面向機(jī)器語(yǔ)言的特點(diǎn)是（ABC）。A、程序的執(zhí)行效率高B、編制效率低C、可讀性差D、可讀性強(qiáng)17、編譯程序使用（AB）區(qū)別標(biāo)識(shí)符的作用域。A、說(shuō)明標(biāo)識(shí)符的過(guò)程B、函數(shù)的靜態(tài)層次C、函數(shù)的動(dòng)態(tài)層次D、標(biāo)識(shí)符的行號(hào)18AD）A、單詞的種別編碼

B、單詞在符號(hào)表中的位置C、單詞的長(zhǎng)度

D、單詞自身值19、優(yōu)化可生成（

AD

）的目標(biāo)代碼。A、運(yùn)行時(shí)間較短B、占用存儲(chǔ)空間較大

C、運(yùn)行時(shí)間短且占用內(nèi)存空間大

D、占用存儲(chǔ)空間小22BC）A、語(yǔ)法分析BD、語(yǔ)義分析F、詞法分析填空題2．若源程序是用高級(jí)語(yǔ)言編寫(xiě)的,___目標(biāo)程序__是機(jī)器語(yǔ)言程序或匯編程序,

則其翻譯程序稱為

___編譯程序__

。

3．編譯方式與解釋方式的根本區(qū)別在于__是否生成目標(biāo)代碼___。

4．對(duì)編譯程序而言,輸入數(shù)據(jù)是___源程序__,

輸出結(jié)果是__目標(biāo)程序___。

5．產(chǎn)生式是用于定義___語(yǔ)法成分__的一種書(shū)寫(xiě)規(guī)則。

6．語(yǔ)法分析最常用的兩類(lèi)方法是___自上而下__和___自下而上__分析法

7．設(shè)

G

是一個(gè)給定的文法，S

是文法的開(kāi)始符號(hào)，如果

S->x(

其中

x∈VT*),

則稱

x

是文

法的一個(gè)__句子___。

8．遞歸下降法不允許任一非終極符是直接__左___遞歸的。

9.常用的參數(shù)傳遞方式有___傳地址__，傳值和傳名。

10．在使用高級(jí)語(yǔ)言編程時(shí),首先可通過(guò)編譯程序發(fā)現(xiàn)源程序的全部__語(yǔ)法___錯(cuò)誤和語(yǔ)義的部分錯(cuò)誤。

11．一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱為該句型的___句柄_。

12．一個(gè)典型的編譯程序中，不僅包括__詞法分析___、__語(yǔ)法分析___、__中間代碼生成___、

代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。

13．

從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為_(kāi)_執(zhí)行性___語(yǔ)句和__說(shuō)明性___語(yǔ)句兩大類(lèi)。

14．語(yǔ)法分析是依據(jù)語(yǔ)言的__語(yǔ)法___規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的__語(yǔ)義___規(guī)

進(jìn)行的。

15．產(chǎn)生式是用于定義___語(yǔ)法成分__的一種書(shū)寫(xiě)規(guī)則。16．計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：___解釋__和__編譯___。

四、名詞解釋（1）2型文法（上下文無(wú)關(guān)文法）若文法G=（VN，VT，P，S）中的每一條規(guī)則的形式為A→β，其中A∈VN，β∈(VN∪VT)*，則稱G是2型文法。二義性文法如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩課不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義性文法。有窮自動(dòng)機(jī)是具有離散輸入與輸出系統(tǒng)的一種抽象數(shù)學(xué)模型。算符文法設(shè)有文法G，若G中沒(méi)有形如U→…VW…的規(guī)則，其中V和W為非終結(jié)符，則稱G為算符文法。素短語(yǔ)素短語(yǔ)是指這樣一種短語(yǔ)，它至少包含一個(gè)終結(jié)符，并且除自身之外，不再包含其他任何更小的素短語(yǔ)。語(yǔ)法制導(dǎo)翻譯法在語(yǔ)法分析過(guò)程中，根據(jù)相應(yīng)文法的每一規(guī)則所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)行翻譯的方法?；緣K指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是局部?jī)?yōu)化局限于基本塊范圍的優(yōu)化稱。應(yīng)用題編譯過(guò)程的5個(gè)階段是什么？第1階段：詞法分析第2階段：語(yǔ)法分析第3階段:詞義分析與中間代碼產(chǎn)生第4階段：代碼優(yōu)化第5階段：目標(biāo)代碼生成請(qǐng)給出編譯程序的結(jié)構(gòu)框圖。設(shè)有文法G[A]:A—>a|b|e|Aa|Ae|A0|A1（1）試問(wèn)VT和VN是由哪些符號(hào)組成的？VN={A}VT={a,b,e,0,1}（2）下列符號(hào)串a(chǎn),ab0,a0e01,0a,11,eee是否為該文法的句子？5.目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問(wèn)題？目標(biāo)代碼通常采用三種形式：機(jī)器語(yǔ)言，匯編語(yǔ)言，待裝配機(jī)器語(yǔ)言模塊。

應(yīng)著重考慮的問(wèn)題：

(1)如何使生成的目標(biāo)代碼較短；

(2)如何充分利用寄存器，以減少訪問(wèn)內(nèi)存次數(shù)；

(3)如何充分利用指令系統(tǒng)的特點(diǎn)。6.基本的優(yōu)化方法有哪幾種？刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫(xiě)傳播和刪除無(wú)用賦值。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.給出下述文法所對(duì)應(yīng)的正規(guī)式。對(duì)應(yīng)的正規(guī)式為：R=a(b|aa)*b解析：9.給出文法G[S],構(gòu)造相應(yīng)最小的DFAS—>aS|bA|bA—>aS10.給出下述文法所對(duì)應(yīng)的正規(guī)式：S—>0A|1BA—>1S|