哈工大編譯原理模擬試題

1、編譯原理模擬試題一、是非題(下列各題,你認(rèn)為正確地,請(qǐng)?jiān)陬}干地括號(hào)內(nèi)打“ ”,錯(cuò)地打“×”)1、算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)地優(yōu)先函數(shù).（ ）2、數(shù)組元素地地址計(jì)算與數(shù)組地存儲(chǔ)方式有關(guān).（ ）3、僅考慮一個(gè)基本塊,不能確定一個(gè)賦值是否真是無(wú)用地.（ ）4、每個(gè)文法都能改寫(xiě)為L(zhǎng)L(1)文法.（ ）5、對(duì)于數(shù)據(jù)空間地存貯分配,FORTRAN采用動(dòng)態(tài)貯存分配策略.（ ）二、填空題1、從功能上說(shuō),程序語(yǔ)言地語(yǔ)句大體可分為（ ）語(yǔ)句和（ ）語(yǔ)句兩大類(lèi).2、掃描器地任務(wù)是從（ ）中識(shí)別出一個(gè)個(gè)（ ）.3、所謂最右推導(dǎo)是指：（ ）.4、語(yǔ)法分析最常用地兩類(lèi)方法是（ ）和（ ）分析法.5、一個(gè)上下文

2、無(wú)關(guān)文法所含四個(gè)組成部分是（ ）.6、所謂語(yǔ)法制導(dǎo)翻譯方法是（ ）.7、符號(hào)表中地信息欄中登記了每個(gè)名字地有關(guān)地性質(zhì),如（ ）等等.8、一個(gè)過(guò)程相應(yīng)地DISPLAY表地內(nèi)容為（ ）.9、常用地兩種動(dòng)態(tài)存貯分配辦法是（ ）動(dòng)態(tài)分配和（ ）動(dòng)態(tài)分配.10、產(chǎn)生式是用于定義（ ）地一種書(shū)寫(xiě)規(guī)則.三、名詞解釋1、遍2、無(wú)環(huán)路有向圖(DAG)3、語(yǔ)法分析4、短語(yǔ)5、后綴式四、簡(jiǎn)述題1、考慮下面程序Var a：integer；Procedure S(X)；Var X：integer；Begina：a1；X：aXEnd；Begina：5；S(a)；Print(a)End試問(wèn)：若參數(shù)傳遞方式分別采取傳名和傳值

3、時(shí),程序執(zhí)行后輸出a地值是什么？2、畫(huà)出C+中實(shí)數(shù)(不帶正負(fù)號(hào),可帶指數(shù)部分)地狀態(tài)轉(zhuǎn)換圖.3、寫(xiě)出表達(dá)式(ab*c)/(ab)d地逆波蘭表示及三元式序列.4、已知文法G(S)Sa|(T)TT,S|S寫(xiě)出句子(a,a),a)地規(guī)范歸約過(guò)程及每一步地句柄.5、何謂優(yōu)化？按所涉及地程序范圍可分為哪幾級(jí)優(yōu)化？6、目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問(wèn)題？五、計(jì)算題1、寫(xiě)一個(gè)文法,使其語(yǔ)言是奇數(shù)集,且每個(gè)奇數(shù)不以0開(kāi)頭.2、設(shè)文法G(S)：S(L)|a S|aLL,S|S（1）消除左遞歸和回溯；（2）計(jì)算每個(gè)非終結(jié)符地FIRST和FOLLOW；（3）構(gòu)造預(yù)測(cè)分析表.3、Whilea0

4、b0do BeginX：X1；if a0 then a：a1else b：b1End；翻譯成四元式序列.4、已知文法G(E)ET|ETTF|T * FF(E)|I（1）給出句型(T * Fi)地最右推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)；（2）給出句型(T * Fi)地短語(yǔ)、素短語(yǔ).5、設(shè)布爾表達(dá)式地文法為E E(1)E(2)E E(1) E(2)E I假定它們將用于條件控制語(yǔ)句中,請(qǐng)（1）改寫(xiě)文法,使之適合進(jìn)行語(yǔ)法制導(dǎo)翻譯和實(shí)現(xiàn)回填；（2）寫(xiě)出改寫(xiě)后地短個(gè)產(chǎn)生式地語(yǔ)義動(dòng)作.6、設(shè)有基本塊T1：2T2：10/TT3：SRT4：SRA：T2 * T4B：AT5：SRT6：T3 * T5B：T6（1）畫(huà)出DAG圖；（2

5、）假設(shè)基本塊出口時(shí)只有A,B還被引用,請(qǐng)寫(xiě)出優(yōu)化后地四元序列.參考答案：一是非題1234×5×二填空題1執(zhí)行性、說(shuō)明性；2源程序、單詞符號(hào)；3任何一步都是對(duì)中最右非終結(jié)符進(jìn)行替換地；4自上而下、自下而上；5一組終結(jié)符號(hào),一組非終結(jié)符號(hào)、一個(gè)開(kāi)始符號(hào)、一組產(chǎn)生式；6為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序,并在語(yǔ)法分析地同時(shí)執(zhí)行 這些子程序；7類(lèi)型、種屬、所占單元大小、地址；8現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄地地址；9棧式、堆式；10語(yǔ)法范疇.三名詞解釋1遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描 一次.2無(wú)環(huán)路有向圖(DAG)如果有向圖中任一通路都不是環(huán)路, 則稱(chēng)廬有向圖為

6、無(wú)環(huán)路有向圖,簡(jiǎn)稱(chēng)DAG. 3語(yǔ)法分析按文法地產(chǎn)生式識(shí)別輸入地符號(hào)串是否為一 個(gè)句子地分析過(guò)程.4短語(yǔ)令G是一個(gè)文法.S劃文法地開(kāi)始符號(hào),假定 是文法G地一個(gè)句型,如果有SA且AB,則稱(chēng)是句型 相對(duì)非終結(jié)符A地短語(yǔ).5后綴式一種把運(yùn)算量寫(xiě)在前面,把算符寫(xiě)在后面地表示 表達(dá)式地方法.四、1、答：傳名：a12 傳值：a6 2、答：略3、逆波蘭表示：abc*ab/d 三元式序列： (*,b,c) (,a,) (,a,b) (/,) (,d)4、答：句型歸約規(guī)則句柄(a,a),a)Saa(S,a),a)TSS(T,a),a)Saa(T,S),a)TT,S T,S(S),a) TSS(T),a) SS(

7、T) (T)(S,a)TSS(T,a) Saa(T,S) TT,S T,S(T) S(T)(T)S5、答：優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換,使得從變換后地程序出 發(fā),能產(chǎn)生更有效地目標(biāo)代碼. 三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化.6、答：目標(biāo)代碼通常采用三種形式：機(jī)器語(yǔ)言,匯編語(yǔ)言,待裝配 機(jī)器語(yǔ)言模塊. 應(yīng)著重考慮地問(wèn)題： (1)如何使生成地目標(biāo)代碼較短； (2)如何充分利用寄存器,以減少訪(fǎng)問(wèn)內(nèi)存次數(shù)； (3)如何充分利用指僅系統(tǒng)地地特點(diǎn). 五、計(jì)算題：1、解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D2、解： (1)S(L)|aSSS|LSL

8、LSL|(2)FIRST)S)(,aFOLLOW(S)#,)FIRST(S),a,FOLLOW(S)#,)FIRST(L)(,aFOLLOW(L) )FIRST(L),FOLLOW(L )(3)a,()SSLLSaSS(L)SSSSSSSLSLLSLLL 3、解：(1) (j,a,0,5)(2) (j,3)(3) (j,b,0,5)(4) (j,15)(5) (,×,1,T1)(6) (：,T1,×)(7) (j,a,0,9)(8) (j,12)(9) (,a,1,T2)(10) (：,T2,a)(11) (j,1)(12) (,b,1,   

9、 T3)(13) (：,T3,b)(14) (j,1)(15)4、解：(1) 最右推導(dǎo)：ETF(E)(ET)(EF)(Ei) (Ti)(T*Fi)語(yǔ)法樹(shù)：略 (2) 短語(yǔ)：(T*Fi),T*Fi,T*F,i 素短語(yǔ)：T*F,i 5、解：(1) E0E(1) EE0E(2) EAE(1) EEAE(2) Ei (2) EE(1)  BACKPATCH(E(1)·FC,NXQ)； E0·TC：E(1)·TC EE0E(2)  E·FC：E(2)·FC； E·TC：MERG(E0·TC,E(2)·TC) EAE(1) BACKPATCH(E(1)·TC,NXQ)； E0·FC：E(1)·FC EEAE(2)  E·TC：E(2)·TC； E·FC：MERG