哈工大編譯原理模擬試題

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

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

3、時,程序執(zhí)行后輸出a地值是什么？2、畫出C+中實數(shù)(不帶正負號,可帶指數(shù)部分)地狀態(tài)轉(zhuǎn)換圖.3、寫出表達式(ab*c)/(ab)d地逆波蘭表示及三元式序列.4、已知文法G(S)Sa|(T)TT,S|S寫出句子(a,a),a)地規(guī)范歸約過程及每一步地句柄.5、何謂優(yōu)化？按所涉及地程序范圍可分為哪幾級優(yōu)化？6、目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？五、計算題1、寫一個文法,使其語言是奇數(shù)集,且每個奇數(shù)不以0開頭.2、設文法G(S)：S(L)|a S|aLL,S|S（1）消除左遞歸和回溯；（2）計算每個非終結(jié)符地FIRST和FOLLOW；（3）構(gòu)造預測分析表.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)地最右推導及畫出語法樹；（2）給出句型(T * Fi)地短語、素短語.5、設布爾表達式地文法為E E(1)E(2)E E(1) E(2)E I假定它們將用于條件控制語句中,請（1）改寫文法,使之適合進行語法制導翻譯和實現(xiàn)回填；（2）寫出改寫后地短個產(chǎn)生式地語義動作.6、設有基本塊T1：2T2：10/TT3：SRT4：SRA：T2 * T4B：AT5：SRT6：T3 * T5B：T6（1）畫出DAG圖；（2

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

6、無環(huán)路有向圖,簡稱DAG. 3語法分析按文法地產(chǎn)生式識別輸入地符號串是否為一 個句子地分析過程.4短語令G是一個文法.S劃文法地開始符號,假定 是文法G地一個句型,如果有SA且AB,則稱是句型 相對非終結(jié)符A地短語.5后綴式一種把運算量寫在前面,把算符寫在后面地表示 表達式地方法.四、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)化：對程序進行各種等價變換,使得從變換后地程序出 發(fā),能產(chǎn)生更有效地目標代碼. 三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化.6、答：目標代碼通常采用三種形式：機器語言,匯編語言,待裝配 機器語言模塊. 應著重考慮地問題： (1)如何使生成地目標代碼較短； (2)如何充分利用寄存器,以減少訪問內(nèi)存次數(shù)； (3)如何充分利用指僅系統(tǒng)地地特點. 五、計算題：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) 最右推導：ETF(E)(ET)(EF)(Ei) (Ti)(T*Fi)語法樹：略 (2) 短語：(T*Fi),T*Fi,T*F,i 素短語：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