最新編譯原理試卷及答案

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

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

3、bB B-bS ,則該文法所描述的語言是C 。A、L (G) =b|i0B、L (G) =bi0C、L (G) =b 2i+1|i0D、L (G) =b 2i+1|i15、把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由B完成的。A、編譯器B、匯編器C、解釋器 D、預(yù)處理器6、在目標(biāo)代碼生成階段，符號表用于 D 。 TOC o 1-5 h z A、目標(biāo)代碼生成B、語義檢查C、語法檢查D、預(yù)處理器地址分配07、規(guī)范歸約是指B 。A、最左推導(dǎo)的逆過程B、最右推導(dǎo)的逆過程C、規(guī)范推導(dǎo)D、最左歸約逆過程8、使用 A可以定義一個(gè)程序的意義。A、語義規(guī)則B、詞法規(guī)則C、語法規(guī)則D、左結(jié)合規(guī)則9、經(jīng)過編譯

4、所得到的目標(biāo)程序是D 。A、三元式序列B、四元式序列 C、間接三元式D、機(jī)器語言程序或匯編語言程序10、在一個(gè)基本塊內(nèi)進(jìn)行的代碼優(yōu)化是B 。A、全局優(yōu)化B、局部優(yōu)化 C、循環(huán)優(yōu)化D、代碼外提三、簡答題(3小題，共30分)1、已知文法 GS: SfAc|aBA - abB - bc證明該文法具有二義性(本題6分)證明：因?yàn)樵撐姆ǖ木湫?abc存在如下兩棵語法樹：AA精品文檔所以，該文法具有二義性3、若有文法GS: S-bAbA一(B|a B -Aa)。構(gòu)造該文法的簡單優(yōu)先關(guān)系矩陣。(10 分)SbABa1)Sb工AM-FBaH(M四、綜合題(20分)設(shè)有文法 GS: S-BAA-BS|dB f

5、aA|bS|c證明文法G是LL (1)文法。構(gòu)造LL (1)分析表。寫出句子adccd的分析過程。解：(1)由 A-BS|d 得二HRKr(BS)nFlRST(? dJ )=軸力,酊“山=如由 B aA|bS|c 得；FlRST(aA) nFIRST(bS)n rRST(c)=(a) n |b門(明-出.可見，文法 G是是LL (1)文法。4、構(gòu)造正規(guī)表達(dá)式(a|b) * b的DFA并化簡。(14分) 解：先構(gòu)造其NFA如下：(2)abcdSS-BABABAAA-BSA-USATSA-*dBB -aAAbSBY裝 訂 線 內(nèi) 不 要 答 題確定化為DFA:33閭12IM)1A.Bi|Ag2IA

6、.H2|2俗，用tfA.njj毒N1 崎定化才UFA井耀卻(3)根當(dāng)前輸入符號輸入串#sadeed#AABadeed#AAaaeked#BAADesd#Addccd#Acud#的Bc。曲祥義:cpdiU#Scd#ffABw曲#AcCd計(jì)d*ddff并備注：學(xué)生不得在試題紙上答題(含填空題、選擇題等客觀題精品文檔精品文檔填空題(每空1分，共20分).編譯過程一般分為 、中間代碼生成、 和目標(biāo)代碼生成五個(gè)階段。.語法分析最常用的兩類方法是 和 分析法。.確定的有窮自動機(jī)是一個(gè) ,通常表示為 o.所謂最右推導(dǎo)是指 。.語法分析器的任務(wù)是 o.如果一個(gè)文法的任何產(chǎn)生式的右部都不含有的非終結(jié)符，則這種文

7、法稱為 .進(jìn)行確定的自上而下語法分析要求語言的文法是無 和 的。. LR分析法是一種 的語法分析方法。.根據(jù)優(yōu)化對象所涉及的程序范圍，代碼優(yōu)化分為 、 等。.常用的優(yōu)化技術(shù)包括： 、強(qiáng)度削弱、復(fù)寫傳播、 等。是非題(下列各題，你認(rèn)為正確的，請?jiān)陬}后的括號內(nèi)打“ ，”，錯(cuò)的打每題2分，共20分).正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。() TOC o 1-5 h z .僅考慮一個(gè)基本塊， 不能確定一個(gè)賦值是否真是無用的。 (.如果一個(gè)文法是遞歸的，則其產(chǎn)生的語言的句子是無窮個(gè)。 (.四元式之間的聯(lián)系是通過符號表實(shí)現(xiàn)的。 (.文法的二義性和語言的二義性是兩個(gè)不同的概念。(精品文檔 TOC

8、 o 1-5 h z . 一個(gè)LL（I） 文法一定是無二義的。（）.在規(guī)范規(guī)約中用最左素短語來刻劃可歸約串。（）.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 （）.編譯程序是對匯編程序的翻譯。（）.逆波蘭法表示的表達(dá)式亦稱前綴式。 （）簡答題（每題5分，共15分）1、簡述棧式存儲管理策略；2、何謂DAG ;3、何謂文法的二義性;給出下述文法對應(yīng)的正規(guī)式（7分）Sf 0A| 1BAf1S | 1Bf OS | 0已知文法G（E）:E- T | E+T | E -TT- F | T*F | T/Fx”F- （E）|ix”證明E+T*F是該文法的一個(gè)句型，并指出該句型的所有短語、直接短

9、語和句柄。（8分）設(shè)有文法GS:S aBc|bABA aAb|bB b| e構(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*T1T3=D+1T4=E-FT5=T3*T4刪除公共子表達(dá)式、 代碼外提、變換循環(huán)控制條件、 合并已知量、刪除無用賦值（任選3個(gè)）、是非題（2X10=20分）1、X2、， 3、， 4、X 5、， 6、，7、 X

10、8、， 9、X 10、X三、簡答題（見書中相應(yīng)部分）（5X3=15分）四、解：首先得正規(guī)式方程組：S=0A+1BA=1S+1B=0S+0求解該方程組得：S=（01|10）（01|10）*（8 分）五、解五、解（2分）是文法GS的句型。短語：E+T*F, T*F（2 分）直接短語：T*F（2分）句柄：T*F（2分）六、解：、因?yàn)?FOLLOW（B）=FIRST（c） U FOLLOW0=c,#（2 分）,所以構(gòu)造文法 GS的 LL （1）分析表（5）如 下：參考答案、填空題（1X20=20分）詞法分析、語法分析、代碼優(yōu)化自上而下、自下而上五元組、DFA=（K , E, M, S, Z）任何一步都是對中最右非終結(jié)符進(jìn)行替換分析一個(gè)文法的句子結(jié)構(gòu)相鄰、算符左遞歸、公共左因子自下而上局部優(yōu)化、循環(huán)優(yōu)化、局部優(yōu)化aBc#SaBcbABAaAbbBb精品文檔精品文檔符號串baabbb是該文法的句子（3分）（分析過程略）。七（2分）狀態(tài)ACTION()#0S2r2r21acc