編譯原理試卷及答案

1、裝 訂 線裝 訂 線 內(nèi) 不 要 答 題學(xué) 號姓 名班 級東 北 大 學(xué) 秦 皇 島 分 校課程名稱： 編譯原理 試卷： (B )答案 考試形式： 閉卷授課專業(yè)： 計算機(jī)科學(xué)與技術(shù) 考試日期： 年 月 日 試卷：共 2 頁 題號一二三四總分得分閱卷人一、 填空題（每空2分，共30分）1、編譯程序的整個過程可以從邏輯上劃分為詞法分析、 語法分析 、語義分析、中間代碼生成、 代碼優(yōu)化 和目標(biāo)代碼生成等幾個階段，另外還有兩個重要的工 作是 理 和出錯處理。表格管2、規(guī)范規(guī)約中的可歸約串是 句柄 ，算符優(yōu)先分析中的可歸約串是 最左素短語 。3、語法分析方法主要可分為 自頂向下 和 自底向上 兩大類。4

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

3、唯一出口結(jié)點(diǎn) C、唯一首結(jié)點(diǎn) D、唯一尾結(jié)點(diǎn)4、設(shè)有文法GS：Sb|bBBbS，則該文法所描述的語言是 C 。A、L（G）=bi|i0 B、L（G）=b2i|i0 C、L（G）=b2i+1|i0 D、L（G）=b2i+1|i15、把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由 B 完成的。A、編譯器 B、匯編器 C、解釋器 D、預(yù)處理器6、在目標(biāo)代碼生成階段，符號表用于 D 。A、目標(biāo)代碼生成 B、語義檢查 C、語法檢查 D、預(yù)處理器地址分配07、規(guī)范歸約是指 B 。A、最左推導(dǎo)的逆過程 B、最右推導(dǎo)的逆過程 C、規(guī)范推導(dǎo) D、最左歸約逆過程8、使用 A 可以定義一個程序的意義。A、語義規(guī)

4、則 B、詞法規(guī)則 C、語法規(guī)則 D、左結(jié)合規(guī)則9、經(jīng)過編譯所得到的目標(biāo)程序是 D 。A、三元式序列 B、四元式序列 C、間接三元式 D、機(jī)器語言程序或匯編語言程序10、在一個基本塊內(nèi)進(jìn)行的代碼優(yōu)化是 B 。A、全局優(yōu)化 B、局部優(yōu)化 C、循環(huán)優(yōu)化 D、代碼外提三、簡答題（3小題，共30分）1、已知文法GS：SAc|aBAab Bbc證明該文法具有二義性（本題6分）證明：因?yàn)樵撐姆ǖ木湫蚢bc存在如下兩棵語法樹：所以，該文法具有二義性裝 訂 線裝 訂 線 內(nèi) 不 要 答 題學(xué) 號姓 名班 級3、若有文法GS：SbAb A（B|a BAa）。構(gòu)造該文法的簡單優(yōu)先關(guān)系矩陣。（10分）解：4、構(gòu)造正規(guī)

5、表達(dá)式（a|b）* b的DFA并化簡。（14分）解：先構(gòu)造其NFA如下：確定化為DFA： 將其最小化如下：四、綜合題（20分）設(shè)有文法GS：SBAABS|dBaA|bS|c（1） 證明文法G是LL（1）文法。（2） 構(gòu)造LL（1）分析表。（3） 寫出句子adccd的分析過程。解：（1）可見，文法G是是LL（1）文法。（2）（3） 備注: 學(xué)生不得在試題紙上答題(含填空題、選擇題等客觀題 一、 填空題（每空1分，共20分）1編譯過程一般分為 、 、中間代碼生成、 和目標(biāo)代碼生成五個階段。2語法分析最常用的兩類方法是 和 分析法。3確定的有窮自動機(jī)是一個 ，通常表示為 。4所謂最右推導(dǎo)是指 。5語

6、法分析器的任務(wù)是 。6如果一個文法的任何產(chǎn)生式的右部都不含有 的非終結(jié)符，則這種文法稱為 文法。7進(jìn)行確定的自上而下語法分析要求語言的文法是無 和 的。8LR分析法是一種 的語法分析方法。9根據(jù)優(yōu)化對象所涉及的程序范圍，代碼優(yōu)化分為 、 和 等。10常用的優(yōu)化技術(shù)包括： 、 、強(qiáng)度削弱、復(fù)寫傳播、 等。 二、 是非題（下列各題，你認(rèn)為正確的，請在題后的括號內(nèi)打“ ”，錯的打“×”。每題2分，共20分）1正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 ( )2僅考慮一個基本塊，不能確定一個賦值是否真是無用的。（ ）3如果一個文法是遞歸的，則其產(chǎn)生的語言的句子是無窮個。 （ ）4四元式

7、之間的聯(lián)系是通過符號表實(shí)現(xiàn)的。（ ）5文法的二義性和語言的二義性是兩個不同的概念。 （ ）6一個LL( l)文法一定是無二義的。 ( )7在規(guī)范規(guī)約中用最左素短語來刻劃可歸約串。 ( )8目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機(jī)的寄存器的問題。 ( )9編譯程序是對匯編程序的翻譯。 （ ）10逆波蘭法表示的表達(dá)式亦稱前綴式。 ( ) 三、 簡答題（每題5分，共15分）1、簡述棧式存儲管理策略； 2、何謂DAG； 3、何謂文法的二義性；四、 給出下述文法對應(yīng)的正規(guī)式 （7分） S 0A| 1BA1S | 1B0S | 0 五、 已知文法G(E)：ET | E+T | E-TTF | T*F |

8、T/FF(E) | i證明E+T*F是該文法的一個句型，并指出該句型的所有短語、直接短語和句柄。（8分） 六、 設(shè)有文法GS：SàaBc|bABAàaAb|bBàb|構(gòu)造其LL(1)分析表，并分析符號串baabbb是否是該文法的句子. (10分) 七、 設(shè)有文法GE:Eà (E) |試判斷該文法是否為SLR(1)文法，若不是，請說明理由；若是請構(gòu)造SLR(1)分析表。(10分) 八、 假設(shè)可用寄存器為R0和R1，試寫出下列四元式序列對應(yīng)的目標(biāo)代碼。（10分）T1=B-CT2=A*T1 T3=D+1 T4=E-F T5=T3*T4 參考答案 一、填空題(1

9、X20=20分)1 詞法分析、語法分析、代碼優(yōu)化2 自上而下、自下而上3 五元組、DFA=(K , M, S, Z)4 任何一步都是對中最右非終結(jié)符進(jìn)行替換5 分析一個文法的句子結(jié)構(gòu)6 相鄰、算符7 左遞歸、公共左因子8 自下而上9 局部優(yōu)化、循環(huán)優(yōu)化、局部優(yōu)化10 刪除公共子表達(dá)式、代碼外提、變換循環(huán)控制條件、合并已知量、刪除無用賦值（任選3個） 二、是非題（2X10=20分） 1、× 2、 3、 4、× 5、 6、 7、 × 8、 9、× 10、× 三、簡答題（見書中相應(yīng)部分）（5X3=15分） 四、解：首先得正規(guī)式方程組： S=0A+1B A=1S+1 B=0S+0 求解該方程組得：S=(01|10)(01|10)* （8分） 五、解 （2分） 是文法GS的句型。 短語：E+T*F, T*F （2分） 直接短語：T*F （2分） 句柄：T*F （2分）六、解：、因?yàn)镕OLLOW(B)=FIRST(c)FOLLOW(S)=c,#(2分),所以構(gòu)造文法GS的LL（1）分析表（5）如下： aBc#SaBcbAB AaAbb B b符號串baabbb是該文法的句子(3分)（分析過程略）。 七 (2分) 所以該文法為SLR(1)文法。其分析表如下：(8分)狀態(tài)ACTIONGOTO()#E0S2r2r