編譯原理模擬試題六

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

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

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

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

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

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

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

8、gt;(S,S) =>(a,S) =>(a,(T) =>(a,(T,S) =>(a,(S,S) =>(a,(a,S) =>(a,(a,a) 對(duì)(a,a),(a),a) 的最左推導(dǎo)為： 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) 文法，如果是，構(gòu)造 LL(1) 分析表。解：各符號(hào)的FIRST集和FOLLOW集為： 預(yù)測(cè)分析表為： 由于預(yù)測(cè)分析表中無(wú)多重入口，所以可判定文法是LL(1)的。五.計(jì)算題（10分）已知文法 GS 為： S->a|(T) T-> T,S|S (1) 計(jì)算 GS 的 FIRS

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

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

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

13、，其后至少緊跟一個(gè) c 。 試構(gòu)造識(shí)別 L 的最小化的 DFA ，并給出描述 L 的正規(guī)表達(dá)式。 五、（ 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 構(gòu)造文法 GS 的 LR （ 1 ）分析表。 七、（ 8 分） 將下面的條件語(yǔ)句表示成逆波蘭式和四元式序列： 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 對(duì)于 G 中的每個(gè)產(chǎn)生式 A 1 | 2 | | m ，其各候選式均應(yīng)滿足： （1）不同的候選式不能推出以同一終結(jié)符號(hào)打頭的符號(hào)串，即 FIRST( i ) FIRST( j )= （ 1 i ， j m ； i j ） （2）若有 j ，則其余候選式 i 所能推出的符號(hào)串不能以 FOLLOW(A) 中的終結(jié)符號(hào)開始，即有 FIRST( i ) FOLLOW(A)=

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

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