編譯原理試卷國教

1、編譯原理考試試題（所有答案必須寫在答題紙上）(2006.12.25)一、(5×6分)回答下列問題：1什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？2什么是句柄？什么是素短語？3劃分程序的基本塊時(shí)，確定基本塊的入口語句的條件是什么？4運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？5對下列四元式序列生成目標(biāo)代碼： A:=B*CD:=E+FG:=A+DH:=G*2其中，H是基本塊出口的活躍變量， R0和R1是可用寄存器二、(8分)設(shè)S=0，1上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成，請給出該字集對應(yīng)的正規(guī)式，并構(gòu)造一個(gè)識別該正規(guī)集的DFA。三、(6分)寫一個(gè)文

2、法使其語言為L(G)= anbmambn | m,n1。四、(8分)對于文法G(E): E®T|E+TT®F|T*FF®(E)|i1. 寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。2. 寫出上述句型的短語，直接短語、句柄和素短語。五、(12分)設(shè)文法G(S)：1 構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合；2 構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)。六、(9分)設(shè)某語言的do-while語句的語法形式為 S ® do S(1) While E真假S(1)的代碼E的代碼其語義解釋為：針對自下而上的語法分析器，按如下要求構(gòu)造該語句的翻譯模式：(1) 寫出適合語法制

3、導(dǎo)翻譯的產(chǎn)生式；(2) 寫出每個(gè)產(chǎn)生式對應(yīng)的語義動作。七、(8分)將語句 if (A<X) Ù (B>0) then while C>0 do C:=C+D; 翻譯成四元式。八、(10分) 設(shè)有基本塊如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)畫出DAG圖；(2)設(shè)A,B是出基本塊后的活躍變量，請給出優(yōu)化后的四元式序列。九、(9分) 設(shè)已構(gòu)造出文法G(S)：(1) S ® BB (2) B ® aB (3) B® b的LR分析表如下ACTIO

4、NGOTO狀態(tài)ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定輸入串為abab，請給出LR分析過程(即按照步驟給出狀態(tài)，符號，輸入串的變化過程)。（END）編譯原理考試試題（所有答案必須寫在答題紙上）(2006.12.25)一、 回答下列問題：(30分)1什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？解答：S-屬性文法是只含有綜合屬性的屬性文法。 （2分）L-屬性文法要求對于每個(gè)產(chǎn)生式AàX1X2Xn，其每個(gè)語義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是Xj的一個(gè)繼承屬性，且該屬性僅依賴于：（1） 產(chǎn)生式Xj的左

5、邊符號X1,X2Xj-1的屬性；（2） A的繼承屬性。 （2分）S-屬性文法是L-屬性文法的特例。 （2分）2什么是句柄？什么是素短語？一個(gè)句型的最左直接短語稱為該句型的句柄。（3分）素短語是這樣的一個(gè)短語，它至少包含一個(gè)終結(jié)符并且不包含更小的素短語。（3分）3劃分程序的基本塊時(shí)，確定基本塊的入口語句的條件是什么？解答：（1）程序第一個(gè)語句，或（2）能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或（3）緊跟在條件轉(zhuǎn)移語句后面的語句。4(6分)運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動記錄區(qū)的同時(shí)建立一張嵌套層次

6、顯示表diaplay.假定現(xiàn)在進(jìn)入的過程層次為i，則它的diaplay表含有i+1個(gè)單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層、直至最外層(主程序，0層)等每層過程的最新活動記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變量。5(6分)對下列四元式序列生成目標(biāo)代碼： A:=B*CD:=E+FG:=A+DH:=G*2其中，H是基本塊出口的活躍變量， R0和R1是可用寄存器答：LD R0， BMUL R0， CLD R1， EADD R1， FADD R0， R1MUL R0， 2ST R0， H二、設(shè)S=0，1上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成，請給出該字集對應(yīng)的正

7、規(guī)式，并構(gòu)造一個(gè)識別該正規(guī)集的DFA。(8分)答：構(gòu)造相應(yīng)的正規(guī)式：(0|1)*1(0|1) (3分)NFA: (2分) 1 110432 e e e e 1 0 0確定化：(3分)I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1 1三、寫一個(gè)文法使其語言為L(G)= anbmambn | m,n1。(6分)答：文法G(S):S ® aSb | BB ® bBa | ba四、對于文法G(E): (8分)E®T|E+TT&

8、#174;F|T*FF®(E)|iETF(E)E+TFiTT*F1. 寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。2. 寫出上述句型的短語，直接短語、句柄和素短語。答：1. (4分)EÞTÞFÞ(E) Þ(E+T) Þ(E+F) Þ(E+i) Þ(T+i) Þ(T*F+i) 2. (4分)短語：(T*F+i), T*F+i, T*F, i直接短語：T*F, i句柄：T*F素短語：T*F, i五、設(shè)文法G(S)：(12分)3 構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合；4 構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)。

9、(12分)答：(6分)FIRSTVT(S)= i，+，)，( FIRSTVT(A)= +，)，( FIRSTVT(B)= )，( LASTVT(S)= i，+，*，( LASTVT(A)= +，*，( LASTVT(B)= *，( 優(yōu)先關(guān)系表: (3分)i+()*i><<<+>><<>(>>>)<<<*>>>優(yōu)先函數(shù): (3分)i+()*f26616g14661六、設(shè)某語言的do-while語句的語法形式為 (9分) S ® do S(1) While E其語義解釋為：真假S(

10、1)的代碼E的代碼針對自下而上的語法分析器，按如下要求構(gòu)造該語句的翻譯模式：(1) 寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；(2) 寫出每個(gè)產(chǎn)生式對應(yīng)的語義動作。答：(1). 適合語法制導(dǎo)翻譯的文法(3分) G(S): R® do U®R S(1) While S®U E (2). (6分) R® do R.QUAD:=NXQ U®R S(1) While U.QUAD:=R.QUAD; BACKPATCH(S.CHAIN, NXQ) S®U E BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC 答案二：(1) S

11、® do M1 S(1) While M2 E M ® (3分)(2) M ® M.QUAD := NXQ (6分)S ® do M1 S(1) While M2 EBACKPATCH(S(1).CHAIN, M2.QUAD);BACKPATCH(E.TC, M1.QUAD); S.CHAIN:=E. FC七、(8分)將語句if (A<X) Ù (B>0) then while C>0 do C:=C+D翻譯成四元式。(8分)答：100 (j<， A， X， 102)101 (j， -， -， 109)102 (j>

12、;， B， 0， 104)103 (j， -， -， 109)104 (j>， C， 0， 106)105 (j， -， -， 109)106 (+， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)109 (控制結(jié)構(gòu)3分，其他5分)八、(10分) 設(shè)有基本塊如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)畫出DAG圖；(2)設(shè)A,B是出基本塊后的活躍變量，請給出優(yōu)化后的四元式序列。T1,T5, B3T24SR+/*_T3T4AT6,Bn4n5n1n2n3n6n8n7答：(1) DAG如右圖：(6分)(2) 四元式序列：(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*4九、(9分) 設(shè)已構(gòu)造出文法G(S)：(1) S ® BB(2) B ® aB(3) B® b的LR分析表如下ACTIONGOTO狀態(tài)ab#