湖南工業(yè)大學編譯原理A卷答案通信

1、 編譯原理試卷（A卷） 答案_通信02一、是非題（下列各題，你認為下確的，請在題干的括號內(nèi)打“”錯的打“×”。每題2分，共10分）1、雖然名字都是用標識符表示的，但名字和標識符有著本質(zhì)的區(qū)別。（）2、優(yōu)先關(guān)系表所對應的優(yōu)先函數(shù)，如果存在，則一定唯一。 （×）3、對于任何一個含有左遞歸的文法必存在一個等價的不含左遞歸的文法。（）4、每個過程的DISPLAY表的體積在編譯時就可確定。 （）5、一個文法的句子也一定是該文法的句型。 （）二、填空題（每題2分，共16分）1、對文法G 的每個非終結(jié)符P，定義集合FIRSTVT（P）=（a|P=> a或P => Qa ，aV

2、T而QVN）。2、如果一個文法的任何產(chǎn)生式的右部都不含有兩個相繼（并列）的非終結(jié)符，則這種文法稱為（算符）文法。3、表達式a/(b*c+d)的逆波蘭表示為（abc*d+/）。4、一張符號表的每一項（或稱入口）包含兩大欄，即（名字）欄和（信息）欄。5、如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是（二義的）。6、在一個基本塊內(nèi)，通常可實行的三種優(yōu)化是：合并已知量、（刪除多余運算）、（刪除無用賦值）。7、文法G 所產(chǎn)生的句子的全體是（語言），將它記為（L（G）。8、根據(jù)優(yōu)化所涉及的程序范圍，優(yōu)化可分為（局部）優(yōu)化、（循環(huán)）優(yōu)化和（全局）優(yōu)化三個不同的級別。三、名詞解釋題（每題3分，共

3、15分）1、語言的語義語言的語義是一組規(guī)則，用它可以定義一個程序的意義。2、句型假定G是一個文法，S是它的開始符號，如果S=>，則稱是一個句型。3、語法分析器按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分析程序。4、語法制導翻譯在語法分析過程中，根據(jù)每個產(chǎn)生式所對應的語義子程序進行翻譯的辦法叫做語法制導翻譯法。5、 活動記錄一個過程在運行時所需數(shù)據(jù)中，編譯時可確定體積的部分稱該過程的活動記錄。四、論述題（每題4分，共24分）1、對于下面的程序段 procedure p(x，y，z)； begin y：= x + y ； Z：= Z*Z end begin A: =2； B：=A*2；

4、P（B-A，A，B）； Print A，B end. 若參數(shù)傳遞方式分別為：（1）傳地址，（2）傳值，試問程序執(zhí)行所輸出的A、B的值分別是什么？傳地址，A=4， B=16傳值， A=2， B=4評分細則：每個值1分2、狀態(tài)轉(zhuǎn)換圖的用途是什么？試舉一簡單例子說明。一個狀態(tài)轉(zhuǎn)換圖可用于識別一定的字符串。例如，識別標識符的轉(zhuǎn)換圖如下字 母1其 它*字母或數(shù)字2 評分細則：用途2分，舉例2分3、目標代碼一般有哪幾種形式？生成目標代碼時要著重考慮的問題是什么？ 目標代碼一般有三種形式： 機器語言代碼； 待裝配的機器語言模塊； 匯編語言代碼。 生成目標代碼時要著重考慮兩個問題： 如何使生成的目標代碼較短；

5、 如何充分利用計算機的寄存器，減少目標代碼中訪問存儲單元的次數(shù)。4、寫出表達式 a*b+(a+b/c)*d的三元式序列。三元式：（*，a,b）(/,b,c)(+,a,)(*, ,d)(+,)評分細則：錯一個三元式扣1分5、設(shè)文法G（E）為E T | E+TT F | T*FF（E）| i給出句子i*i+i的最右推導，并畫出語法樹。最右推導：E E+T E+F E+i T+i T*F+i T*i+i F*i+i i*i+i 語法樹：6、簡述自下而上語法分析方法的分析過程。自下而上分析方法的分析過程是：從輸入串開始，逐步進行“歸約”直至歸到文法的開始符號，或者說，從語法樹的末端開始步步向上“歸約”

6、，直至根結(jié)。五、計算題（共35分）1、請按簡單代碼生成算法對以下四元式序列生產(chǎn)目標代碼；T1：=A+BT2：=T1*3T3：=A-BT4：=T2*T3（假設(shè)可用寄存器為R0、R1，只有T4是基本塊之后的活躍變量） （6分）LD R0，AADD R0，BMuL R0，3LD R1,ASuB R1,BMuL R0,R1ST R0,T4評分細則：答錯一條指令扣1分，最多扣6分2、設(shè)文法G（S）為： S|a|（T） TT，S|S給出消去G（S）左遞歸后的文法G（S）左遞歸后的文法G；計算G的每個非終結(jié)符的FIRST和FOLLOW；構(gòu)造預測分析表。 （8分）G（S）：S|a|（T）TSTT ,ST| （

7、2分）FIRST（S）=FIRST（T）=a，（ FIRST（T）=, FOLLOW（S）=#，,） FOLLOW（T）=FOLLOW（T）=） （3分）a（）#ST TS aTS TA T STS（T）TS TTT,ST(3分)3、對語句 if E then S 寫出適合語法制導翻譯的產(chǎn)生式；寫出各產(chǎn)生式對應的語義動作。 （6分）產(chǎn)生式Cif E thenSC S(1) (3分)語義動作 Cif E then BACK（E.TC,NXQ）；C.chain ：=E.FC SC S(1)S.chain：=MERG（C.chain,S(1).Chain） (3分)4、把語句 while a10 do if c0 then a:=a+1 else a:=a*3-1；翻譯成四元式序列。 （7分）四元式序列 (j<,a,10,)12 (j, ， ) (j>,c,0,) (j,，) (+,a,1,T1) (:=, T1,a ) (j, ,，) (*，a, 3,T2 ) (，T2，1，T3) (：=， T3，a) (j， ) 評分細則：錯一條四元式扣1分5、對以下基本塊進行優(yōu)化 D：=ACE：=A*CF：=D*ES：=2T：=ACQ：=A*CG：=2*SJ：=T*QK：=G*5L：=K+JM：=L要求：畫出DAG圖；