華東交通大學(xué)編譯原理試題庫(kù)試卷二

1、一、是非題(下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“”，錯(cuò)的打“×”。每題1分,共5分) 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ù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。二、填空題(每題2分，共20分) 1、從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為_(kāi)語(yǔ)句和_語(yǔ)句兩大類。2、掃描器的任務(wù)是從_中識(shí)別出一個(gè)個(gè)_。 3、所謂最右推導(dǎo)是指：_。 4、語(yǔ)法分析最常用的兩類方法是_和_分析法。 5、一個(gè)上下文無(wú)關(guān)文法所含四個(gè)組成部分

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

3、d 試問(wèn)：若參數(shù)傳遞方式分別采取傳名和傳值時(shí)，程序執(zhí)行后輸出a的值是什么？ 2、畫(huà)出Pascal中實(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ì)算題(共41分) 1、寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。(5分) 2、設(shè)文法G(S)： S(L)|a S|a LL，S|S (1)消除左遞歸和

4、回溯； (2)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW； (3)構(gòu)造預(yù)測(cè)分析表。 3、Whilea0 b0do Begin X：X1； if a0 then a：a1 else b：b1 End； 翻譯成四元式序列。(7分) 4、已知文法G(E) ET|ET TF|T *F F(E)|i (1)給出句型(T *Fi)的最右推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)； (2)給出句型(T *Fi)的短語(yǔ)、素短語(yǔ)。(7分) 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ǔ)義

5、動(dòng)作。(6分) 6、設(shè)有基本塊 T1：2 T2：10/T T3：SR T4：SR A：T2 *T4 B：A T5：SR T6：T3 *T5 B：T6 (1)畫(huà)出DAG圖； (2)假設(shè)基本塊出口時(shí)只有A，B還被引用，請(qǐng)寫(xiě)出優(yōu)化后的四元序列。(6分)  參考答案： 一、 × ×二、 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、 類型、種屬、所占單元大小、地址

6、 8、 現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址 9、 棧式、 堆式 10、 語(yǔ)法范疇 三、名詞解釋1遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。 2無(wú)環(huán)路有向圖(DAG)如果有向圖中任一通路都不是環(huán)路，則稱廬有向圖為 無(wú)環(huán)路有向圖，簡(jiǎn)稱DAG。 3語(yǔ)法分析按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過(guò)程。 4短語(yǔ)令G是一個(gè)文法。S劃文法的開(kāi)始符號(hào)，假定是文法G的一個(gè)句 型，如果有SA且AB，則稱是句型相對(duì)非終結(jié)符A的短語(yǔ)。 5后綴式一種把運(yùn)算量寫(xiě)在前面，把算符寫(xiě)在后面的表示表達(dá)式的方法。 四、簡(jiǎn)述題1、答：傳名：a12(2分) 傳值：a6 (2分) 3、答：逆波蘭表示： a

7、bc*ab/d(2分) 三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d)(2分) 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(T) (T) (S，a) TSS (T，a) Saa (T，S) TT，S T，S (T) S(T)(T) S(4分) 5、 答：優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。(2分) 三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。(2分) 6、 答：目標(biāo)代碼通常采用三種形式：機(jī)器語(yǔ)言，匯

8、編語(yǔ)言，待裝配機(jī)器語(yǔ)言模塊。(2分) 應(yīng)著重考慮的問(wèn)題： (1)如何使生成的目標(biāo)代碼較短； (2)如何充分利用寄存器，以減少訪問(wèn)內(nèi)存次數(shù)； (3)如何充分利用指僅系統(tǒng)的的特點(diǎn)。 (2分)五、計(jì)算題 1、解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D(5分) 2、解:(1) S(L)|aS' S'S| LSL' L'SL'| 評(píng)分細(xì)則：消除左遞歸2分，提公共因子2分。 (2) FIRST)S)(，aFOLLOW(S)#，) FIRST(S')，a,FOLLOW(S')#，) FIRST(L)

9、(，aFOLLOW(L) ) FIRST(L')，F(xiàn)OLLOW(L' ) 3、解： (1) (j，a，0，5) (2) (j，3) (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， T3) (13) (：，T3，b) (14) (j，1) (15) 評(píng)分細(xì)則：控制結(jié)構(gòu)4分，其它3分。 4、解：(1) 最右推導(dǎo)： ETF(E)(ET)(EF)(Ei) (Ti)(T*Fi) (2) 短語(yǔ)：(T*Fi)，T*F

10、i，T*F，i(2分) 素短語(yǔ)：T*F,i (1分) 5、解：(1) E0E(1) EE0E(2) EAE(1) EEAE(2) Ei(3分) (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&