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

一、填空題(每題2分，共20分)1、從功能上說，程序語言的語句大體可分為 語句和 語句兩大類。2、掃描器的任務(wù)是從 中識別出一個個 。3、所謂最右推導(dǎo)是指： 。4、語法分析最經(jīng)常使用的兩類方式是 和 分析法。5、一個上下文無關(guān)文法所含四個組成部份是 。6、所謂語法制導(dǎo)翻譯方式是 。7、符號表中的信息欄中記錄了每一個名字的有關(guān)的性質(zhì)，如 等等。8、一個進程相應(yīng)的DISPLAY表的內(nèi)容為 。9、經(jīng)常使用的兩種動態(tài)存貯分派方法是 動態(tài)分派和 動態(tài)分派。10、產(chǎn)生式是用于概念 的一種書寫規(guī)那么二、名詞說(每題2分，共10分)1、遍2、無環(huán)路有向圖(DAG)3、語法分析4、短語5、后綴式三、簡述題(每題4分，共24分)1、考慮下面程序…………VarProcedureVarX：integer；Begina：＝a＋1；X：＝a＋XEnd；Begina：＝5；S(a)；Print(a)End．試問：假設(shè)參數(shù)傳遞方式別離采取傳名和傳值時，程序執(zhí)行后輸出a的值是什么？2、畫出Pascal中實數(shù)(不帶正負號，可帶指數(shù)部份)的狀態(tài)轉(zhuǎn)換圖。3、寫出表達式(a＋b*c)/(a＋b)－d的逆波蘭表示及三元式序列。4、已知文法G(S)S→a|∧|(T)T→T，S|S寫出句子((a，a)，a)的標(biāo)準(zhǔn)歸約進程及每一步的句柄。5、何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？6、目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時通常應(yīng)考慮哪幾個問題？四、計算題(共41分)1、寫一個文法，使其語言是奇數(shù)集，且每一個奇數(shù)不以0開頭。(5分)2、設(shè)文法G(S)：S→(L)|aS|aL→L，S|S排除左遞歸和回溯；計算每一個非終結(jié)符的FIRST(3)構(gòu)造預(yù)測分析表。3While a＞0∨b＜0 BeginX：＝X＋1；ifa＞0thena：＝a－1elseb：＝b＋1End；(7分4、已知文法G(E)E→T|E＋TT→F|T*FF→(E)|i(1)給出句型(T*F＋i)的最右推導(dǎo)及畫出語法樹；(2)給出句型(T*F＋i)的短語、素短語。(7分)5、設(shè)布爾表達式的文法為E→E(1)∨E(2)E→E(1)∧E(2)E→i假定它們將用于條件操縱語句中，請(1)改寫文法，使之適合進行語法制導(dǎo)翻譯和實現(xiàn)回填；(2)寫出改寫后的短個產(chǎn)生式的語義動作。(6分)6、設(shè)有大體塊T1：＝2T2：＝10/TT3：＝S－RT4：＝S＋RA：＝T2*T4B：AT5：＝S＋RT6：＝T3*T5B：＝T6畫出DAG圖；假設(shè)大體塊出口時只有(6分)參考答案：一、填空題1、執(zhí)行性、說明性2、源程序、單詞符號3、任何一步αβ都是對α中最右非終結(jié)符進行替換的4、自上而下、自下而上5、一組終結(jié)符號，一組非終結(jié)符號、一個開始符號、一組產(chǎn)生式6、為每一個產(chǎn)生式配上一個翻譯子程序，并在語法分析的同時執(zhí)行這些子程序7、類型、種屬、所占單元大小、地址8、現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址9、棧式、堆式10、語法范圍二、名詞說明遍－－指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭至尾掃描一次。無環(huán)路有向圖(DAG)有向圖，簡稱DAG。語法分析－－按文法的產(chǎn)生式識別輸入的符號串是不是為一個句子的分析進程。短語－－令GS劃文法的開始符號，假定αβδ是文法GSαAδ且AB，那么稱βαβ相對非終結(jié)符A的短語。三、簡述題1、考慮下面程序…………Vara：integer；ProcedureS(X)；VarX：integer；Begina：＝a＋1；X：＝a＋XEnd；Begina：＝5；S(a)；Print(a)End．a(chǎn)的值是什么？答：傳名(2分)傳值(2分)(a＋b*c)/(a＋b)－d逆波蘭表示：abc*＋ab＋/d－ (2分)三元式序列：①(*，b，c)②(＋，a，①)③(＋，a，b)④(/，②，③)⑤(－，④，d) (2分)4、已知文法G(S)S→a|∧|(T)T→T，S|S寫出句子((a，a)，a)的標(biāo)準(zhǔn)歸約進程及每一步的句柄。句型歸約規(guī)那么句柄((a，a)，a)S→aa((S，a)，a)T→SS((T，a)，a)S→aa((T，S)，a)T→T，ST，S((S)，a)T→SS((T)，a)S→S(T)(T)(S，a)T→SS(T，a)S→aa(T，S)T→T，ST，S(T)S→(T)(T)S(4分)5、何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？答：優(yōu)化：對程序進行各類等價變換，使得從變換后的程序動身，能產(chǎn)生更有效的標(biāo)代碼。 (2分)三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。 (2分)6、目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時通常應(yīng)考慮哪幾個問題？答：目標(biāo)代碼通常采納三種形式：機械語言，匯編語言，待裝配機械語言模塊(2分應(yīng)著重考慮的問題：如何使生成的目標(biāo)代碼較短；如何充分利用寄放器，以減少訪問內(nèi)存次數(shù)；如何充分利用指僅系統(tǒng)的的特點。 (2分)四、計算題1、寫一個文法，使其語言是奇數(shù)集，且每一個奇數(shù)不以0開頭。(5分)解：文法G(N)：N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D (5分)2、設(shè)文法G(S)：S→(L)|aS|aL→L，S|S排除左遞歸和回溯；計算每一個非終結(jié)符的FIRSTFOLLOW；構(gòu)造預(yù)測分析表。解：(1)S→(L)|aS'S'→S|εL→SL'L'→SL'|ε評分細那么：排除左遞歸2分，提公共因子2分。(2)FIRST)S)＝{(，a} FOLLOW(S)＝{#，，)}FIRST(S')＝{，a,ε} FOLLOW(S')＝{#，，)}FIRST(L)＝{(，a} FOLLOW(L)＝{)}FIRST(L')＝{，ε} 〕＝{)}、While a＞0∨b＜0 BeginX：＝X＋1；ifa＞0thena：＝a－1elseb：＝b＋1End；翻譯成四元式序列。(7分)解：(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，T3)(13)(：＝，T3，－，b)(14)(j，－，－，1)(15)評分細那么：操縱結(jié)構(gòu)4分，其它3分。4、已知文法G(E)T→F|T*FF→(E)|i(T*的最右推導(dǎo)及畫出語法樹；(T*(7分)解：(1)最右推導(dǎo)：ETF(E)(E＋T)(E＋F)(E＋i)(T＋i)(T*F＋i)(2)短語：(T*F＋i)，T*F＋i，T*F，i素短語：T*F,i5、設(shè)布爾表達式的文法為E→E(1)∨E(2)E→E(1)∧E(2)E→i

(2分)(1分)假定它們將用于條件操縱語句中，請改寫文法，使之適合進行語法制導(dǎo)翻譯和實現(xiàn)回填；(6分)解：(1)E0→E(1)E→E0E(2)EA→E(1)E→EAE(2)E→i (3分)(2)E→E(1){BACKPATCH(E(1)·FC，NXQ)；E0·TC：＝E(1)·TC}E→E0E(2){E·FC：＝E(2)·FC；E·TC：＝MERG(E0·TC，E(2)·TC)}EA→E(1){BACKPATCH(E(1)·TC，NXQ)；E0·FC：＝E(1)·FC}E→EAE(2){E·TC：＝E(2)·TC；E·FC：＝MERG(EA·FC，E(2)·FC)6、設(shè)有大體塊T1：＝2

E→i{E·TC：＝NXQ；E·FC：＝NXQ＋1；GEN(jn2，ent