編譯原理-期末復習

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

ABC）3個方面。語法B、語義C、D、4、程序語言一般分為（

A

）和（

B

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

C、分析語句和說明是如何構成程序的7、語法分析的常用方法有。A、自頂向下

B、自底向上

C、自左向右D、自右向左8、程序設計語言常見的數(shù)據(jù)類型有：（ABCD）

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

B、一組產生式

C、一個開始符號文法12、描述一個語言的文法是（C、D）。A、唯一的B、不唯一的

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

B、a0c01

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

E’→+TE’∣ε

T→FT’

T’→*FT’∣ε

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

B、單詞在符號表中的位置C、單詞的長度

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

AD

）的目標代碼。A、運行時間較短B、占用存儲空間較大

C、運行時間短且占用內存空間大

D、占用存儲空間小22BC）A、語法分析BD、語義分析F、詞法分析填空題2．若源程序是用高級語言編寫的,___目標程序__是機器語言程序或匯編程序,

則其翻譯程序稱為

___編譯程序__

。

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

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

輸出結果是__目標程序___。

5．產生式是用于定義___語法成分__的一種書寫規(guī)則。

6．語法分析最常用的兩類方法是___自上而下__和___自下而上__分析法

7．設

G

是一個給定的文法，S

是文法的開始符號，如果

S->x(

其中

x∈VT*),

則稱

x

是文

法的一個__句子___。

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

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

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

11．一個句型中的最左簡單短語稱為該句型的___句柄_。

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

代碼優(yōu)化、目標代碼生成等五個部分，還應包括表格處理和出錯處理。

13．

從功能上說，程序語言的語句大體可分為__執(zhí)行性___語句和__說明性___語句兩大類。

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

進行的。

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

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

應著重考慮的問題：

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

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

(3)如何充分利用指令系統(tǒng)的特點。6.基本的優(yōu)化方法有哪幾種？刪除多余運算，代碼外提，強度削弱，變換循環(huán)控制條件，合并已知量，復寫傳播和刪除無用賦值。7.構造下列正規(guī)式相應的DFA（用狀態(tài)轉換圖表示）（1）1（0|1）*1（2）0*10*10*10*1（3）letter(letter|digit)*8.給出下述文法所對應的正規(guī)式。對應的正規(guī)式為：R=a(b|aa)*b解析：9.給出文法G[S],構造相應最小的DFAS—>aS|bA|bA—>aS10.給出下述文法所對應的正規(guī)式：S—>0A|1BA—>1S|