編譯原理模擬試題六

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

2、序中的表達式語句在語義翻譯時不需要回填技術。 ()10對中間代碼的優(yōu)化依賴于具體的計算機。 (× )二、選擇題(請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1編譯程序絕大多數(shù)時間花在_ 上。A( ) 出錯處理 B( ) 詞法分析 C( ) 目標代碼生成 D( ) 表格管理2 編譯程序是對_。  A( ) 匯編程序的翻譯   B( ) 高級語言程序的解釋執(zhí)行  C( ) 機器語言的執(zhí)行 D( ) 高級語言的翻譯 3 采用自上而下分析，必須_。A( ) 消除左遞歸  B( ) 消除右遞歸 &#

3、160;C( ) 消除回溯   D( ) 提取公共左因子 4在規(guī)范歸約中，用_來刻畫可歸約串。A( )直接短語 B( )句柄   C( )最左素短語   D( )素短語 5 若a為終結符，則A-> · a為_項目。A( )歸約   B( ) 移進     C( ) 接受      D( ) 待約 6間接三元式表示法的優(yōu)點為_。 A( ) 采用間接碼表，便于優(yōu)化處理      

4、60;  B( ) 節(jié)省存儲空間，不便于表的修改 C( ) 便于優(yōu)化處理，節(jié)省存儲空間             D( ) 節(jié)省存儲空間，不便于優(yōu)化處理 7基本塊內的優(yōu)化為_。A. ( ) 代碼外提，刪除歸納變量 B( ) 刪除多余運算，刪除無用賦值        C( ) 強度削弱，代碼外提         D( ) 循環(huán)展開，循環(huán)合并

5、8. 在目標代碼生成階段，符號表用_。A( ) 目標代碼生成 B( ) 語義檢查C( ) 語法檢查 D( ) 地址分配9若項目集Ik含有A-> · ，則在狀態(tài)k時，僅當面臨的輸入符號aFOLLOW(A)時，才采取“A-> · ”動作的一定是_。A. ( ) LALR文法     B( ) LR(0)文法     C( ) LR(1)文法D( ) SLR(1)文法10堆式動態(tài)分配申請和釋放存儲空間遵守_原則。 A. ( ) 先請先放   B( ) 先請后放 C( ) 后請先放 

6、0; D. ( ) 任意三、填空題(每空1分，共10分)1詞法分析基于_正則_文法進行，即識別的單詞是該類文法的句子。 2語法分析基于_上下文無關_文法進行，即識別的是該類文法的句子。語法分析的有效工具是_語法樹_。3分析句型時，應用算符優(yōu)先分析技術時，每步被直接歸約的是_最左素短語_，而應用LR分析技術時，每步被直接歸約的是_句柄_。4語義分析階段所生成的與源程序等價的中間表示形式可以有_逆波蘭_、_四無式表示_與_三元式表示_等。5按Chomsky分類法，文法按照_規(guī)則定義的形式_進行分類。 6一個文法能用有窮多個規(guī)則描述無窮的符號串集合（語言）是因為文法中存在有_遞歸_定義的規(guī)

7、則。 四、簡答題（20分）1. 文法 GS 為： S->Ac|aB A->ab B->bc 寫出 L(GS) 的全部元素。解：S=>Ac=>abc 或S=>aB=>abc 所以L(GS)=abc2. 構造正規(guī)式 1(0|1)*101 相應的DFA。解：先構造NFA： 確定化： 重新命名，令AB為B、AC為C、ABY為D得： 所以，可得DFA為： 3. 文法 S->a|(T) T->T,S|S 對 (a,(a,a) 和 (a,a),(a),a) 的最左推導。解： 對(a,(a,a)的最左推導為： S=>(T) =>(T,S) =&

8、gt;(S,S) =>(a,S) =>(a,(T) =>(a,(T,S) =>(a,(S,S) =>(a,(a,S) =>(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

9、,a),S),S) =>(a,a),(T),S) =>(a,a),(S),S) =>(a,a),(a),S) =>(a,a),(a),a)4. 文法： S->MH|a H->LSo| K->dML| L->eHf M->K|bLM 判斷 G 是否為 LL(1) 文法，如果是，構造 LL(1) 分析表。解：各符號的FIRST集和FOLLOW集為： 預測分析表為： 由于預測分析表中無多重入口，所以可判定文法是LL(1)的。五.計算題（10分）已知文法 GS 為： S->a|(T) T-> T,S|S (1) 計算 GS 的 FIRS

10、TVT 和 LASTVT 。 (2) 構造 GS 的算符優(yōu)先關系表并說明 GS 是否未算符優(yōu)先文法。 (3) 計算 GS 的優(yōu)先函數(shù)。 (4) 給出輸入串 (a,a)# 的算符優(yōu)先分析過程。解：（1）各符號的FIRSTVT和LASTVT：（2）算符優(yōu)先關系表： （3）對應的算符優(yōu)先函數(shù)為： （4）句子(a,a)#分析過程如下： 一、選擇題（每個選擇題 2 分，共 20 分） 1 文法 G 產(chǎn)生的 的全體是該文法描述的語言。 A 句型 B. 終結符集 C. 非終結符集 D. 句子 2 若文法 G 定義的語言是無限集，則文法必然是 ： A 遞歸的 B 前后文無關的 C 二義性的 D 無二義性的 3

11、 Chomsky 定義的四種形式語言文法中， 0 型文法又稱為 文法； 1 型文法又稱為 文法； 2 型語言可由 識別。 A 短語結構文法 B 前后文無關文法 C 前后文有關文法 D 正規(guī)文法 E 圖靈機 F 有限自動機 G 下推自動機 4 一個文法所描述的語言是 ；描述一個語言的文法是 。 A 唯一的 B 不唯一的 C 可能唯一，好可能不唯一 5 數(shù)組的內情向量中肯定不含有數(shù)組的 的信息 A維數(shù) B.類型 C.維上下界 D.各維的界差 6 在下述的編譯方法中，自底向上的方法有 ，自頂向下的分析方法有 。 簡單優(yōu)先分析 算符優(yōu)先分析 遞歸下降分析 預測分析技術 LR（K）分析 SLR（k）分析

12、 LL（k）分析 LALR（K）分析 A. B. C. D. E. F. 二、簡答題（每小題 5 分，共 20 分） 1 LL （ 1 ）分析法對文法有哪些要求？ 2 常見的存儲分配策略有幾種？它們都適合于什么性質的語言？ 3 常見循環(huán)優(yōu)化都有哪些項目？ 4 什么是活動記錄？它主要由哪些內容構成？ 三、（ 8 分）化簡文法 GS ： S ASe | BCaD | aD | AC A Cb | DBS C bC | d B Ac D aD 四、（ 12 分） 設 L í a,b,c* 是滿足下述條件的符號串構成的語言： (1)若出現(xiàn) a ，則其后至少緊跟兩個 c ； (2)若出現(xiàn) b

13、，其后至少緊跟一個 c 。 試構造識別 L 的最小化的 DFA ，并給出描述 L 的正規(guī)表達式。 五、（ 12 分） 已給文法 GS ： S SaP | Sf | P P qbP | q 將 GS 改造成 LL （ 1 ）文法，并給出 LL （ 1 ）分析表。 六、（ 12 分） 給定文法 GS ： S Aa|dAb|Bb|dBa A c B c 構造文法 GS 的 LR （ 1 ）分析表。 七、（ 8 分） 將下面的條件語句表示成逆波蘭式和四元式序列： if a>b then x:=a+b*c else x:=b-a; 八、（ 8 分） 給定基本塊： A:=3*5 B:=E+F C:=

14、A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本塊后，只有 A 、 C 、 E 是活躍的，給出用 DAG 圖完成優(yōu)化后的代碼序列。 參考答案： 一、 D A A C G. A B A F A 二、 1 對于 G 中的每個產(chǎn)生式 A 1 | 2 | | m ，其各候選式均應滿足： （1）不同的候選式不能推出以同一終結符號打頭的符號串，即 FIRST( i ) FIRST( j )= （ 1 i ， j m ； i j ） （2）若有 j ，則其余候選式 i 所能推出的符號串不能以 FOLLOW(A) 中的終結符號開始，即有 FIRST( i ) FOLLOW(A)=

15、 （ i 1,2, ,m ； i j ） 2 有三種分配存儲空間的方式：（ 1 ） 靜態(tài)分配 若在編譯階段就能確定源程序中各個數(shù)據(jù)實體的存儲空間大小，則可以采用較簡單的靜態(tài)存儲管理。 適合 靜態(tài)管理 的語言應具備條件： 數(shù)組上下界是常數(shù)、過程調用不允許遞歸、不允許動態(tài)建立數(shù)據(jù)實體。 （ 2） 棧式分配 適用于允許遞歸調用的程序設計語言 ；（ 3 ） 堆式分配 對于允許程序在運行時為變量 動態(tài)申請和釋放存儲空間 的語言 ， 采用 堆式分配 是最有效的解決方案 。 3 不變運算外提；運算強度削弱；消除歸納變量；下標變量地址計算優(yōu)化。 4 一個過程的一次執(zhí)行所需信息的管理，是通過稱為 活動記錄 的連

16、續(xù)存儲塊來實現(xiàn)的。活動記錄的主要內容有：（ 1） 臨時變量域 存放目標程序臨時變量的值；（ 2 ）局部數(shù)據(jù)域 存放過程本次執(zhí)行時的局部數(shù)據(jù)、簡單變量及數(shù)組內情向量等；（ 3 ）機器狀態(tài)域 保存在調用過程前有關機器狀態(tài)的信息，包括各寄存器的當前值及返回地址等；（ 4 ）存取鏈 為訪問其它活動記錄中所存放的非局部數(shù)據(jù)所提供的鏈地址；（ 5 ）控制鏈 指向主調過程的活動記錄；（ 6 ）實參 存放主調過程為被調用過程所提供的實參信息；（ 6 ）返回值 為主調過程存放被調過程的返回值 三、化簡后： S ASe|AC A Cb C bC | d 四、 DFA 如圖所示。相應的正規(guī)式為 (c|acc|bc)* 。 五、 改造后的文法： S PS' S' aPS'| fS' | e P qP' P' bP | e 各候選式的 FIRST 集，各非終結符的 FOLLOW 集為 產(chǎn)生式 FIRST 集 FOLLOW 集 S PS' q # S' aPS' fS' e a f e # P qP' q a,f,# P' bP e b e a,f,# LL(1) 分析表為