(完整word版)編譯原理試卷及答案(word文檔良心出品)

1、-1 - A C 課程名稱： 編譯原理 試卷：(B (B ) )答案 考試形式： 閉卷 授課專業(yè)： 計算機科學(xué)與技術(shù) 考試日期: 年 月曰 試卷：共_2_頁 一、 填空題(每空 2 2 分，共 3030 分) 1、 編譯程序的整個過程可以從邏輯上劃分為詞法分析、 語法分析 、語義分析、 中間代碼生成、 代碼優(yōu)化 和目標(biāo)代碼生成等幾個階段，另外還有兩個重要的工 作是 理 和出錯處理。表格管 2 2、 規(guī)范規(guī)約中的可歸約串是 句柄 ，算符優(yōu)先分析中的可歸約串是 最左素短語 3、 語法分析方法主要可分為 自頂向下 和 自底向上 兩大類。 4、 LR (0)文法的項目集中不會出現(xiàn) 移進-歸約 沖突和

2、歸約-歸約 沖突。 5、 數(shù)據(jù)空間的動態(tài)存儲分配方式可分為 棧式 和 堆式 兩種。 6 6、 編譯程序是指能將 源語言程序翻譯成 目標(biāo)語言程序的程序。 7、 確定有窮自動機 DFA 是 NFA 的一個特例。 &表達式 (a+b)*c 的逆波蘭表示為 ab+c* 。 二、 選擇題(每題 2 2 分，共 2020 分) 1、 LR 語法分析棧中存放的狀態(tài)是識別 B 的 DFA 狀態(tài)。 A、前綴 B、可歸前綴 C、項目 D、句柄 2、 D _ 不可能是目標(biāo)代碼。 A、匯編指令代碼 B、可重定位指令代碼 3、 一個控制流程圖就是具有 C 的有向圖 A、唯一入口結(jié)點 B、唯一出口結(jié)點 C、唯一首

3、結(jié)點 D、唯一尾結(jié)點 4、 設(shè)有文法 GS : ST b|bB B 宀 bS，則該文法所描述的語言是 C 。 A、L (G) =bi|i 0 B、L (G) =b2i|i 0 2i+1 2i+1 C、L (G) =b |i 0 D、L (G) =b |i 1 5、 把匯編語言程序翻譯成機器可執(zhí)行的目標(biāo)程序的工作是由 B 完成的。 A、編譯器 B、匯編器 C、解釋器 D、預(yù)處理器 6、 在目標(biāo)代碼生成階段，符號表用于 D 。 A、目標(biāo)代碼生成 B、語義檢查 C、語法檢查 D、預(yù)處理器地址分配 0 7、 規(guī)范歸約是指 B 。 A、最左推導(dǎo)的逆過程 B、最右推導(dǎo)的逆過程 C、規(guī)范推導(dǎo) D、最左歸約逆

4、過程 8、 使用 A可以定義一個程序的意義。 A、語義規(guī)則 B、詞法規(guī)則 C、語法規(guī)則 D、左結(jié)合規(guī)則 9、 經(jīng)過編譯所得到的目標(biāo)程序是 D 。 A、三元式序列 B、四元式序列 C、間接三元式 D、機器語言程序或匯編語言程序 10、 在一個基本塊內(nèi)進行的代碼優(yōu)化是 _ 。 A、全局優(yōu)化 B、局部優(yōu)化 C、循環(huán)優(yōu)化 D、代碼外提 三、簡答題(3 3 小題，共 3030 分) 1 1、已知文法 GS : ST Ac|aB A T ab B T bc 證明該文法具有二義性 (本題 6 6 分) 證明：因為該文法的句型 abc 存在如下兩棵語法樹: 東北大學(xué)秦皇島分校 C、絕對機器指令代碼 D、中間代

5、碼 題號 -一一 -二二 四 總分 得分 閱卷人 裝 訂 線 內(nèi) 不 -2 - 所以，該文法具有二義性 四、綜合題（2020 分） 3 3、若有文法 GS : STbAb A（ B|a B Aa）。構(gòu)造該文法的簡單優(yōu)先關(guān)系矩陣。 （10 分） 設(shè)有文法 GS: ST BA AT BS|d B T aA|bS|c S S b b A A B B a a ) S b b = = A A F B B a a H ( 工 D 可見，文法 G 是是 LL (1)文法。 (3) k S.B M 1 2 IJLBJ I A.B i IMJ2J 2 l 氐創(chuàng) t fA.BJJ 3 棧 當(dāng)兩輸入符號 輸入爭 #

6、s a deed# 肖AB a deed# #AAa a deed# BAA D ccd# d ccd# #A c 皿 c ffSc c pdiU #S c d# ffAB c 曲 #Ac C 血 d ft d ff # ft 備注：學(xué)生不得在試題紙上答題（含填空題、選擇題等客觀題 -3 - 填空題（每空1分，共20分） 1 編譯過程一般分為 _ 、 _ 、中間代碼生成、 _ 和目標(biāo)代碼生成五個階段。 2 語法分析最常用的兩類方法是 _ 和 _ 分析法。 3 確定的有窮自動機是一個 _ ，通常表示為 _ 。 4 所謂最右推導(dǎo)是指 _ 。 5 語法分析器的任務(wù)是 _ 。 6 .如果一個文法的任何

7、產(chǎn)生式的右部都不含有 的非終結(jié)符，則這種文法稱為 _ 文法。 7 進行確定的自上而下語法分析要求語言的文法是無 _ 和 _ 的。 8 LR分析法是一種 _ 的語法分析方法。 9 根據(jù)優(yōu)化對象所涉及的程序范圍，代碼優(yōu)化分為 _ 、 _ 和 等。 是非題（下列各題，你認(rèn)為正確的，請在題后的括號內(nèi)打“ V”，錯的打“X 6 一個LL（ I） 文法一定是無二義的。 . （ 7 在規(guī)范規(guī)約中用最左素短語來刻劃可歸約串。 . （） 8 目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。 . （） 9 編譯程序是對匯編程序的翻譯。 . （ 10 逆波蘭法表示的表達式亦稱前綴式。 . （ 三、 簡答題（

8、每題5分，共15分） 1、簡述棧式存儲管理策略； 2、何謂DAG ; 3、何謂文法的二義性; 四、 給岀下述文法對應(yīng)的正規(guī)式 （7分） ST 0A| 1B AT 1S | 1 BT 0S | 0 五、 已知文法G（E）: ET T | E+T | E -T TT F | T*F | T/F FT （E） | i 證明E+T*F是該文法的一個句型，并指岀該句型的所有短語、直接短語和句柄。 每題2分，共20分） 1 正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 . （） 2 僅考慮一個基本塊， 不能確定一個賦值是否真是無用的。 . （ ） 3 如果一個文法是遞歸的，則其產(chǎn)生的語言的句子是無窮個

9、。 （ ） 4 四元式之間的聯(lián)系是通過符號表實現(xiàn)的。 . （ ） 5文法的二義性和語言的二義性是兩個不同的概念。 . （ ） 六、 設(shè)有文法GS: S aBc|bAB A aAb|b 10.常用的優(yōu)化技術(shù)包括: _、強度削弱、復(fù)寫傳播、 （8 分） 七、 設(shè)有文法GE: 1、 x 2、V 3、V 4、 X 5、V 6、“ 7、 X 8、V 9、 X 10、 X -4 - B b| 構(gòu)造其 LL（1）分析表，并分析符號串 baabbb是否是該文法的句子 .（10 分） -5 - E （E） | 試判斷該文法是否為 SLR（1）文法，若不是，請說明理由；若是請構(gòu)造 SLR（1）分析表。（10 分）

10、 八、 假設(shè)可用寄存器為 R0和R1，試寫岀下列四元式序列對應(yīng)的目標(biāo)代碼。 （10 分） T仁 B-C T2=A*T1 T3=D+1 T4=E-F T5=T3*T4 參考答案 、填空題（1X20=20分） 1. 詞法分析、語法分析、代碼優(yōu)化 2. 自上而下、自下而上 3. 五元組、DFA=(K , E, M, S, Z) 4. 任何一步 都是對 中最右非終結(jié)符進行替換 5. 分析一個文法的句子結(jié)構(gòu) 6. 相鄰、算符 7. 左遞歸、公共左因子 8. 自下而上 9. 局部優(yōu)化、循環(huán)優(yōu)化、局部優(yōu)化 10 . 刪除公共子表達式、代碼外提、變換循環(huán)控制條件、合并已知量、刪除 無用賦值（任選3個） 、是非

11、題（2X10=20分） 三、 簡答題（見書中相應(yīng)部分） 四、 解：首先得正規(guī)式方程組： (5X3=15 分) (8分) S=0A+1B A=1S+1 B=0S+0 求解該方程組得： S=(01|10)(01|10)* 五、解 （2分） 是文法 GS的句型。 短語：E+T*F, T*F （2分） 直接短語：T*F （2分） 句柄：T*F （2分） 六、解： 、因為 FOLLOW(B)=FIRST(c) U FOLLOW(S)=c,#(2 分),所以構(gòu)造文法 GS的LL （ 1）分析表（5 ）如 下： a B c # S aBc bAB A aAb b B b 符號串 baabbb 是該文法的句子 （3分）（分析過程略）。 七 （2分） 所以該文法為SLR（1）文法。 其分析表如下：（8分） 狀態(tài) ACTION GOTO ( ) # E 七、 設(shè)有文法GE: 1、 x 2、V 3、V 4、 X 5、V 6、“ 7、 X 8、V 9、 X 1