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

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

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

3、15分）1、語言的語義語言的語義是一組規(guī)則，用它可以定義一個(gè)程序的意義。2、句型假定G是一個(gè)文法，S是它的開始符號(hào)，如果S=>，則稱是一個(gè)句型。3、語法分析器按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析程序。4、語法制導(dǎo)翻譯在語法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語義子程序進(jìn)行翻譯的辦法叫做語法制導(dǎo)翻譯法。5、 活動(dòng)記錄一個(gè)過程在運(yùn)行時(shí)所需數(shù)據(jù)中，編譯時(shí)可確定體積的部分稱該過程的活動(dòng)記錄。四、論述題（每題4分，共24分）1、對(duì)于下面的程序段 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評(píng)分細(xì)則：每個(gè)值1分2、狀態(tài)轉(zhuǎn)換圖的用途是什么？試舉一簡(jiǎn)單例子說明。一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別一定的字符串。例如，識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖如下字 母1其 它*字母或數(shù)字2 評(píng)分細(xì)則：用途2分，舉例2分3、目標(biāo)代碼一般有哪幾種形式？生成目標(biāo)代碼時(shí)要著重考慮的問題是什么？ 目標(biāo)代碼一般有三種形式： 機(jī)器語言代碼； 待裝配的機(jī)器語言模塊； 匯編語言代碼。 生成目標(biāo)代碼時(shí)要著重考慮兩個(gè)問題： 如何使生成的目標(biāo)代碼較短；

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

6、，直至根結(jié)。五、計(jì)算題（共35分）1、請(qǐng)按簡(jiǎn)單代碼生成算法對(duì)以下四元式序列生產(chǎn)目標(biāo)代碼；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評(píng)分細(xì)則：答錯(cuò)一條指令扣1分，最多扣6分2、設(shè)文法G（S）為： S|a|（T） TT，S|S給出消去G（S）左遞歸后的文法G（S）左遞歸后的文法G；計(jì)算G的每個(gè)非終結(jié)符的FIRST和FOLLOW；構(gòu)造預(yù)測(cè)分析表。 （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、對(duì)語句 if E then S 寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；寫出各產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作。 （6分）產(chǎn)生式Cif E thenSC S(1) (3分)語義動(dòng)作 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， ) 評(píng)分細(xì)則：錯(cuò)一條四元式扣1分5、對(duì)以下基本塊進(jìn)行優(yōu)化 D：=ACE：=A*CF：=D*ES：=2T：=ACQ：=A*CG：=2*SJ：=T*QK：=G*5L：=K+JM：=L要求：畫出DAG圖；