編譯原理期末復習

1、編譯原理、單選題1、將編譯程序分為若干個“遍”是為了（） o ba.提高程序的執(zhí)行效率b.使程序的結構更加清晰c.利用有限的機器內(nèi)存并提高機器的執(zhí)行效率d.利用有限的機器內(nèi)存但降低了機器的執(zhí)行效率2、構造編譯程序應掌握（）。 da.源程序 b.目標語言c.編譯方法 d.以上三項都是3、變量應當（）。ca.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值4、編譯程序絕大多數(shù)時間花在（）上。 da.由錯處理 b.詞法分析c.目標代碼生成 d.管理表格d可重定位指令代碼 中間代碼5、（）不可能是目標代碼。a.匯編指令代碼b.c.絕對指令代碼d.高級語言程序的解釋執(zhí)行 高級語言

2、的翻譯6、編譯程序是對（） o da.匯編程序的翻譯b.c.機器語言的執(zhí)行d.7、正規(guī)式m1和m2等價是指（）。ca.m1和m2的狀態(tài)數(shù)相等b.m1和m2的有象弧條數(shù)相等c.m1和m2所識別的語言集相等 d.m1和m2狀態(tài)數(shù)和有象弧條數(shù)相等8、如果文法g是無二義的，則它的任何句子（）o aa.最左推導和最右推導對應的語法樹必定相同。b.最左推導和最右推導對應的語法樹可能相同。c.最左推導和最右推導必定相同。d.可能存在兩個不同的最左推導，但它們對應的語法樹相同叮叮小文庫229、文法 g s- s+t|tt*p|pp- （s）|i 句型p+t+i的短語有（）ba. i , p+t b. pb.p

3、+t + i d. p10、產(chǎn)生正規(guī)語言的文法為（）。da.0型b.1型11、文法 g s- b| ?|（t）t t?s|s則 firstvt（t）=（）a.b, ?, （b.bc.b , ?,（ , ? d.b12、給定文法：cc bcbc可選項有：a. b.c.13、采用自上而下分析，必須（）a.消除左遞歸c.消除回溯14、由文法的開始符經(jīng) 。步或多步推導產(chǎn)生的文法符號序列是（）oa.短語b.句柄 c.句型 d.句子a - ba | cc , bcbcca.a+b/c+dc.a+b/(c+d),p+t, i , p+t +i ,p+t, ic.2型d.3型)?f面的符號串中，為該文法句子的

4、是bbbccd.cb.消除右遞歸d.提取公共左因子c15、后綴式ab+cd+/可用表達式（）來表示b.(a+b)/(c+d)d.a+b+c/d16、語法分析器則可以發(fā)現(xiàn)源程序中的（） a.語義錯誤。db.語法和語義錯誤c.錯誤并矯正d.語法錯誤first 集17、在語法分析處理中，合、a.非終極符集b.d.字母表d.follow 合、select 集合均是（）。 b終極符集狀態(tài)集a. cb.前后文無關文法d.正規(guī)文法b.占用存儲空間較小d.運行時間短且占用內(nèi)存空間b?|缶時變量d.程序變量18、四種形式語言文法中，1型文法又稱為（） 短語結構文法c.前后文有關文法19、優(yōu)化可生成（）的目標代碼

5、。a.運行時間較短c.運行時間短但占用內(nèi)存空間大20、四元式之間的聯(lián)系是通過（）實現(xiàn)的a.指示器c.符號表:、多選題1、 女果在文法g中存在一個句子，當其滿足下列條件（bcd ）之一時，則稱該 文法是二義文法。a.其最左推導和最右推導相同b.該句子有兩個不同的最左推與c.該句子有兩個不同的最右推導d.該句子有兩棵不同的語法樹e.該句子對應的語法樹唯一2、 下面（bcd語法制與翻譯中，采用拉鏈一回填技術。a、賦值語句b 、布爾表達式的計算c條件語句d 、循環(huán)語句3、 一般程序設計語言的定義都涉及到（ abc） 3個方面。a、語法b、語義c、語用d、程序基本符號的確定4、 程序語言一般分為（a ）

6、和（b ）。a高級語言b低級語言c專用程序語言d通用程序語言5、 編譯程序工作時，通常有（abcd ）階段。a、詞法分析b、語法分析c、中間代碼生成 d、語義檢查e、目標代碼生成6編譯過程中，語法分析的任務是（bcd ）。a、分析單詞是怎樣構成的b、分析單詞是如何構成語句和說明的c、分析語句和說明是如何構成程序的d、分析程序的結構7、語法分析的常用方法有（ab ）。a、自頂向下b自底向上c、自左向右d、自右向左8、程序設計語言常見的數(shù)據(jù) 類型有：（abcda、數(shù)值型數(shù)據(jù)b、邏輯數(shù)據(jù)c、字符數(shù)據(jù)d、指針類型9、構造編譯程序應掌握 （abca、源程序b、目標語言c、編譯方法d、以上都不是abc、語

7、法分析d 、代碼優(yōu)化i &編書tt率ftt,firstt 駐(bc 、 +,# , )f 、*,+,#,一*fti & f)id 17、編譯程序使用（ab ）區(qū)別標識符的作用域。10、編譯程序前三個階段完成的工作是a、詞法分析bc語義分析和中間代碼生成 11、一個上下文無關文法 g包括四個組成部分：一組終結符，一組非終結符以及（bc）a、一組字符串b、一組產(chǎn)生式c、一個開始符號d 一個文法12、描述一個語言的文法是（c doa、唯一的b 、不唯一的可能唯一 d、也可能不唯一下列13、設有文法gl:c符號串中是該文法句子的有、（bcd。a、ab0b a0c01cc aaad bc1014、運行階

8、段的存儲組織與管理的目的是（cda、提高編譯程序的運行速度b、節(jié)省編譯程序的存儲空間c、提高目標程序的運行速度d、為運行階段的存儲分配做準備15、已知文法 ge : e te e一 +t(e)i id 求：followf )= (d )a、 *, +b 、 * ,& d * , +, #,) e、 #,) 16、面向機器語言的特點是（abc ） oa、程序的執(zhí)行效率同c、可讀性差a、說明標識符的過程b、函數(shù)的靜態(tài)層次c、函數(shù)的動態(tài)層次d 、標識符的行號18、詞法分析器的輸出結果是（ad ）a單詞的種別編碼b單詞在符號表中的位置 單詞的長度c單詞自身值d19、優(yōu)化可生成（ad ）的目標代碼。、占

9、用存儲空間較大a、運行時間較短c運行時間短且占用內(nèi)存空間大d、占用存儲空間小22、編譯程序各階段的工作都涉及到（ bc ）a、語法分析b、表格管理c、出錯處理d、語義分析f、詞法分析三、填空題1 ?編譯程序的工作過程一般可以劃分為詞法分析，語法分析，語義分析，中間代 碼生成，代碼優(yōu)化等幾個基本階段，會時還會伴有一表格處理 和一出錯處理o2-若源程序是用高級語言編寫的，一目標程序一是機器語言程序或匯編程序，則 其翻譯 程序稱為編譯程序。3 ?編譯方式與解釋方式的根本區(qū)別在于一是否生成目標代碼一。4 ?對編譯程序而言，輸入數(shù)據(jù)是一源程序,輸出結果是一目標程序 一5?產(chǎn)生式是用于定義語法成分一的一種

10、書寫規(guī)則。6 ?語法分析最常用的兩類方法是 自上而下一和一自下而上一 分析法7?設g是一個給定的文法，s是文法的開始符號，如果 s-x （其中x? vt*）,則 稱x是文法的一個句子。8 ?遞歸下降法不允許任一非終極符是直接左遞歸的9?常用的參數(shù)傳遞方式有一傳地址_,傳值和傳名10 .在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部一語法錯誤和語義的部分錯誤。11 . 一個句型中的最左簡單短語稱為該句型的句柄12 . 一個典型的編譯程序中，不僅包括一詞法分析一、一語法分析一、一中間 代碼生成一、代碼優(yōu)化、目標代碼生成等五個部分，還應包括表格處理和出錯處理。13 .從功能上說，程序語言的

11、語句大體可分為一執(zhí)行性一語句和一說明性 語句兩大類。14?語法分析是依據(jù)語言的 一語法一規(guī)則進行的，中間代碼產(chǎn)生是依據(jù)語言的一語義規(guī)進行的。15?產(chǎn)生式是用于定義語法成分 的一種書寫規(guī)則。16 ?計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑 ：解釋和編譯17 ?局部優(yōu)化是在 基本塊 一范圍內(nèi)進行的一種優(yōu)化o18 ?分法分析基于一正則一文法進行，即識別的單詞是該類文法的句子。19?語法分析基于一上下文無關一文法進行，即識別的是該類文法的句子。語 法分析 的有效工具是一語法樹一o20. 一個文法能用有窮多個規(guī)則描述無窮的符號串集合(語言)是因為文法中存在有遞歸定義的規(guī)則。四、名詞解釋(1) 2型文

12、法(上下文無關文法)若文法g=(vn, vt, p, s)中的每一條規(guī)則的形式為 a b,其中a? vn,英(vnuvt)*,則稱g是2型文法。(2)二義性文法如果一個文法存在某個句子對應兩課不同的語法樹，則稱這個文法是二義性文法。(3)有窮自動機是具有離散輸入與輸出系統(tǒng)的一種抽象數(shù)學模型。(4)算符文法設有文法g,若g中沒有形如u-,vw的規(guī)則，其中v和w為非終結符，則稱 g為算符文法。(5)素短語素短語是指這樣一種短語，它至少包含一個終結符，并且除自身之外，不再 包 含其他任何更小的素短語。(6)語法制導翻譯法在語法分析過程中，根據(jù)相應文法的每一規(guī)則所對應的語義子程序進行翻譯的方法。(7)

13、基本塊指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是 其 中的第一個語句，出口就是其中的最后一個語句。(8)句柄一個句型的最左直接短語稱為該句型的句柄(9)待用信息如果在一個基本塊中，四元式i對a定值，四元式j要引用a值，而從i到j之間 沒有a的其它定值，則稱j是四元式i的變量a的待用信息。(10)局部優(yōu)化局限于基本塊范圍的優(yōu)化稱五、應用題1.編譯過程的5個階段是什么？第1階段：詞法分析第2階段：語法分析第3階段：詞義分析與中間代碼產(chǎn)生第4階段：代碼優(yōu)化第5階段：目標代碼生成2?青給出編譯程序的結構框圖3.源程序目標程序設有文法ga:a a|b|e|aa|ae|a0|a1(

14、1 ) 試問vt和vn是由哪些符號組成的？vn=av 二a,b,e,0,1(2)下列符號串a(chǎn),abo,aoeo1,oa,11,eee 是否為該文法的句子？a,a0e01,eee是該文法句子。4.證明下面的文法是二義性的。s- ises|is|i耐句子對應下面兩棵不同的語芯樹如圖d. 1所示。圖d 1對應句于用應的贏棵語袪樽5.目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？目標代碼通常采用三種形式：機器語言，匯編語言，待裝配機器 語言模塊。應著重考慮的問題：(1)如何使生成的目標代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(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)*0 0idtcr8.給出下述文法所對應的正規(guī)式s aaa ba|ab|bb aa對應的正規(guī)式為：r