《編譯原理》模擬試題六[001]

1、個人資料整理，僅供個人學習使用1 / 5編譯原理模擬試題六一、是非題(請在括號內(nèi)，正確的劃W錯誤的劃X)(每個 2 分，共 20 分)1 設 r 和 s 分別是正規(guī)式，則有 L(r|s)=L(r)L(s)。(X2.確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。(V)3詞法分析作為單獨的一遍來處理較好。(X)4.構造 LR 分析器的任務就是產(chǎn)生 LR 分析表。 (V)5.規(guī)范歸約和規(guī)范推導是互逆的兩個過程。(X)6.同心集的合并有可能產(chǎn)生新的 “移進” /歸“約”沖突。 (X)7.LR 分析技術無法適用二義文法。 (X)8.樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。(X)

2、9.程序中的表達式語句在語義翻譯時不需要回填技術。(V)10.對中間代碼的優(yōu)化依賴于具體的計算機。(X)二、選擇題 (請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論 )(每個 4 分，共40 分)1. 編譯程序絕大多數(shù)時間花在A.( ) 出錯處理C.( ) 目標代碼生成2._ 編譯程序是對 _ 。A.( ) 匯編程序的翻譯C.( ) 機器語言的執(zhí)行3.采用自上而下分析，必須A.( ) 消除左遞歸C.( ) 消除回溯4. 在規(guī)范歸約中，用 _A.( )直接短語C.( )最左素短語5.若 a 為終結(jié)符，則 A-a_ 上。B.( ) 詞法分析D.( ) 表格管理B.D.高級語言程序的解釋A

3、.( )歸約B.( ) 移進顧葒。OB.D.( ) 提取公共左因子聞創(chuàng)溝燴鐺險愛氌譴凈禍測。來刻畫可歸約串。B.( )句柄D.( )素短語殘騖樓諍錈瀨濟溆塹籟婭騍。-為 _項目。( )消除右遞歸C.接受D.( ) 待約釅錒極額閉鎮(zhèn)檜豬訣錐6.間接三元式表示法的優(yōu)點為 _A.( ) 采用間接碼表，便于優(yōu)化處理C.( ) 便于優(yōu)化處理，節(jié)省存儲空間貿(mào)攝爾霽斃攬磚鹵廡詒爾。B.( ) 節(jié)省存儲空間，不便于表的修改D.( ) 節(jié)省存儲空間，不便于優(yōu)化處理彈7._ 基本塊內(nèi)的優(yōu)化為 _ 。A. ( ) 代碼外提，刪除歸納變量C.( ) 強度削弱，代碼外提8. 在目標代碼生成階段，符號表用A.( ) 目標

4、代碼生成C.( ) 語法檢查9. 若項目集 Ik 含有 A-a采取“A-a動作的一定是A. ( ) LALR 文法C.( ) LR(1) 文法D.B.( ) 刪除多余運算，刪除無用賦值 循環(huán)展開，循環(huán)合并謀蕎摶篋飆鐸懟類蔣薔點鉍。OB.( ) 語義檢查D.( ) 地址分配廈礴懇蹣駢時盡繼價騷巹癩。，則在狀態(tài) k 時，僅當面臨的輸入符號 a FOLLOW(A)時，才_ 。煢楨廣鰳鯡選塊網(wǎng)羈淚鍍齊。B.( ) LR(0) 文法D. ( ) SLR(1)文法鵝婭盡損鶴慘歷蘢鴛賴縈詰。個人資料整理，僅供個人學習使用2 / 510.堆式動態(tài)分配申請和釋放存儲空間遵守 _原則。個人資料整理，僅供個人學習使

5、用3 / 5A.()先請先放B.()先請后放C .()后請先放D.()任意籟叢媽羥為贍債蟶練淨櫧撻。三、 填空題(每空 1 分，共 10 分)1詞法分析基于 正則文法進行，即識別的單詞是該類文法的句子。2.語法分析基于 上下文無關文法進行，即識別的是該類文法的句子。語法分析的有效工具是語法樹。預頌圣鉉儐歲齦訝驊糴買闥。3分析句型時，應用算符優(yōu)先分析技術時，每步被直接歸約的是最左素短語，而應用LR 分析技術時，每步被直接歸約的是句柄_。滲釤嗆儼勻諤鱉調(diào)硯錦鋇絨。4語義分析階段所生成的與源程序等價的中間表示形式可以有 逆波蘭、四無式表示_與_三元式表示_等。鐃誅臥瀉噦圣騁貺頂廡縫勵。5按 Chom

6、sky 分類法，文法按照規(guī)則定義的形式進行分類。6. 一個文法能用有窮多個規(guī)則描述無窮的符號串集合(語言)是因為文法中存在有遞歸定義的規(guī)則。四、 簡答題(20 分)1.文法 GS為：S-Ac|aBA-abB-bc寫出 L(GS)的全部元素。解: S=Ac=abc或 S=aB=abc所以 L(GS)=abc2.構造正規(guī)式 1(0|1)*101 相應的 DFA。01XAAAABABACABACAABYABYACAB重新命名，令 AB 為 B、AC 為 C、ABY 為 D 得:01 .XAAABBCBCAD確定化:個人資料整理，僅供個人學習使用4 / 5DCB所以，可得 DFA 為:薔報贏。3. 文

7、法S-aF|(T)T-T,S|S對(a,(a,a)和(a,a),A,(a),a)的最左推導。解：對(a,(a,a )的最左推導為：S=(T) =(T,S) =(S,S) =(a,S)=(a,(T) =(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)對(a,a),A,(a),a)的最左推導為：S=(T) =(T,S) =(S,S) =(T),S)=(T,S),S) =(T,S,S),S) =(S,S,S),S)=(T),S,S),S) =(T,S),S,S),S) =(S,S),S,S),S) =(a,S),S,S),S) =(a,a),S,S),S)=(a,a),A,S

8、),S) =(a,a),A,(T),S) =(a,a),A,(S),S) =(a,a),A,(a),S) =(a,a),A,(a),a)贓熱俁閫歲匱閶鄴鎵騷鯛漢。4. 文法：S-MH|aH-LSo| &K-dML|L-eHfM-K|bLM判斷 G 是否為 LL(1)文法，如果是，構造 LL(1)分析表。 解：各符號的 FIRST 集和 FOLLOW 集為：FIRSTFOLLOWSa,d,b, c,eMH3#3L何g 期心的KHOeAo預測分析表為:個人資料整理，僅供個人學習使用5 / 5a0dcbS-MHM-K-bLM-KHr - EL-eHfK- -dML- 8E由于預測分析表中無多重入口，所以可判定文法是LL(1)的。壇搏鄉(xiāng)囂懺蔞鍥鈴氈淚躋馱。五.計算題(10 分)已知文法 GS為：S-aF|(T)T- T,S|S(1) 計算 GS的 FIRSTVT 和 LASTVT 。(2) 構造 GS的算符優(yōu)先關系表并說明GS是否未算符優(yōu)先文法。計算 GS的優(yōu)先函數(shù)。(4)給出輸入串(a,a)#的算符優(yōu)先分析過程。解：(