20061編譯原理A卷答案

1、 2006年期末考試A卷參考答案一、（12分）簡答題：簡述編譯程序分成哪幾個階段。答： 編譯過程通常需要經(jīng)過詞法分析、語法分析、中間代碼生成、代碼優(yōu)化和目標代碼生成五個階段。另外還包括表格管理和出錯處理。為什么要將詞法分析與語法分析分離？答：將編譯過程的分析工作劃分成詞法分析和語法分析兩個階段的理由如下：（1）使整個編譯程序的結(jié)構(gòu)更簡潔、清晰和條理化（2）編譯程序的效率會改進 ；（3）增強編譯程序的可移植性。二、（6分）敘述由下列正規(guī)式描述的語言： (a|b)*(aa|bb)(a|b)*。含有相繼2個a或b的a,b上的任意串。（0|1）（0|1）（0|1）0（0|1）* 第四位為0的0，1上的

2、任意串。三、（12分）構(gòu)造一個DFA，它接受=a，b上所有滿足下面條件的字符串，其條件是字符串中的每個b都有a直接跟在右邊。解：正規(guī)式為V=(a|ba)*首先構(gòu)造如下圖所示的NFA MXY(a|ba)*X1abaYX1aY2ba再構(gòu)造轉(zhuǎn)換矩陣如下表、下圖所示。012aabbIIaIbX,1,Y1,Y21,Y1,Y221,Y即：見下表Sab01211221化簡，先將狀態(tài)分終態(tài)組J1=0,1和非終態(tài)組J2=2考察J1，0,1a=10,1 0,1b=23不能再分組。重新命名上述狀態(tài)子集將0,1用1代替 將2用1代替，見下表。這樣得到如圖所示的簡化后的DFA M。10ba0Sab001101四、 （2

3、0分）對于文法G(E)E E + T | T T T *F | F F PF | PP (E) | i計算FIRSTVT和LASTVT；該文法是算符優(yōu)先文法嗎？計算優(yōu)先關(guān)系。解：（1）構(gòu)造FIRSTVT集合的LASTVT集合。FIRSTVT(P)=(,i),FIRSTVT(F)=,(,i),FIRSTVT(T)=*,(,i),FIRSTVT(E)=+,*,(,i);LASTVT(P)=,i,LASTVT(F)= ,i,LASTVT(T)=*, ,i,LASTVT(E)=+,*, ）(2)是算符優(yōu)先文法。（3）構(gòu)造算符優(yōu)先表如下。 +*（）i#+*(= =) i#= =五、(14分)設(shè)有文法G(

4、E)：E a|b|(F)F F,E| E給出句子(a,a),b,(a,b)的最右推導(dǎo)；消除文法的左遞歸；改寫后的文法是否是LL（1）的？為什么？出G的預(yù)測分析表。解：（1）最右推導(dǎo)為：E(F) (F,E) (F,(F) (F,(F,E) (F,(F,b) (F,(E,b) ( F,(a,b) (E,(a,b) (F,E,(a,b) (F,b,(a,b) (E,b,(a,b) (F),b,(a,b) (F,E),b,(a,b) (F,a),b,(a,b) (E,a),b,(a,b) (a,a),b,(a,b)(2)消除左遞歸，將文法改為：Ea|b|(F)FEFF,EF| (3)構(gòu)造該文法的FIR

5、ST集和FOLLOW集：FIREF(E)=FIREF(F)=a,b,()FIREF(F)=，, FOLLOW(E)=#, ，,FOLLOW(F)=FOLLOW(F)=) 改寫后的文法是LL(1)的。(4)該文法的預(yù)測分析表如下表所示。ab(),#EEaEbE(F)FFEFFEFFEFFFF,EF六、（16分）對下述文法構(gòu)造LR型的錯誤校正分析程序。（*優(yōu)先級高于+，同級運算左結(jié)合）EE+EEE*EE(E)Ei并給出輸入串 (i+(*i) 的錯誤校正處理過程。解：使用LR分析法進行語法分析，當(dāng)輸入符號既不能移入棧頂，而棧內(nèi)符號又不能歸約時，就意味著發(fā)現(xiàn)了輸入串中的語法錯誤，立即調(diào)用相應(yīng)的錯誤處理

6、子程序進行錯誤處理。前面給出的表達式文法G是一個二義性文法。下面給出與此文法相應(yīng)的包含錯誤處理子程序的LR分析表。表中：Si表示把下一狀態(tài)i和現(xiàn)行輸入符號移進棧；ri表示按第i個產(chǎn)生式進行歸約，acc是接受狀態(tài)；e1、e2、e3和e4是相應(yīng)的錯誤處理子程序，其功能分別為：e1：/*處在狀態(tài)0、2、4、5時，當(dāng)遇到+、*或#等符號時，調(diào)用此程序*/將一假想的i和狀態(tài)3移進棧，并打印錯誤信息：“缺少運算量”。e2：/*當(dāng)處在狀態(tài)0、1、2、4、5而遇到右括號時，調(diào)用此程序*/從輸入端刪除右括號），并打印錯誤信息：“右括號不配對”。輸入符號狀 態(tài)ACTIONGOTOi + * ( ) #E0S3 e

7、1 e1 S2 e2 e111e3 S4 S5 e3 e2 acc2S3 e1 e2 S2 e2 e163r4 r4 r4 r4 r4 r44S3 e1 e1 S2 e2 e175S3 e1 e1 S2 e2 e186e3 S4 S5 e3 S9 e47r1 r1 S5 r1 r1 r18r2 r2 r2 r2 r2 r29r3 r3 r3 r3 r3 r3e3：/*當(dāng)處在1或6狀態(tài)而又遇到i或左括號）時，調(diào)用此程序*/將運算符+和狀態(tài)4移進棧，并打印錯誤信息：“缺少運算符”。e3：/*當(dāng)處在1或6狀態(tài)而又遇到i或左括號）時，調(diào)用此程序*/將運算符+和狀態(tài)4移進棧，并打印錯誤信息：“缺少運算符

8、”。e4：/*當(dāng)處在狀態(tài)6，遇到#時，調(diào)用此程序*/將右括號）和狀態(tài)9移進棧，并打印錯誤信息：“缺少右括號”。下面給出出錯處理過程，在此使用了一個狀態(tài)棧和一個符號棧，從而使分析過程更為清楚醒目。對輸入串 (i+(*i)的錯誤校正處理過程如表所示：步 驟狀 態(tài) 棧符 號 棧輸 入 串附 注00#(i+(*i)#移進102#(i+(*i)#移進2023#(i+(*i)#歸約3026#(E+(*i)#移進40264#(E+(*i)#移進502642#(E+( *i)#調(diào)用e1，將i和狀態(tài)3移進棧，并打印“缺運算量”6026423#(E+(i *i)#歸約70266426#(E+(E *i)#移進80

9、264065#(E+(E* i)#移進902642653#(E+(E*i )#歸約步 驟狀 態(tài) 棧符 號 棧輸 入 串附 注1002642658#(E+(E*E )#歸約11026426#(E+(E )#移進120264269#(E+(E) #歸約1302647#(E+E #歸約14026#(E #調(diào)用e4，將)和狀態(tài)9移進棧，并打印“缺右括號150269#(E) #歸約1601#E #分析完畢七、(12分) 將下列語句if AB then z:=x-y else z:=x+y 翻譯成四元式序列.解： 100(J),A,B,102)101(J,，105)102(-,x,y, T1)103(:=,T1，z)( J,，107)105(+,x,y, T2)106(:=, T2，z)107八、（8分）給出算術(shù)表達式a+b*(c-d)+e/(c-d)的三元式、間接三元式、樹、四元式表示。解：三元式間接三元式 間接碼表 四元式(1) (-,c,d)(1) (-,c,d)(1) (1) (-,c,d,T1)(2) (*,b,(1)(2) (*,b,(1)(2) (2) (*,b, T1,T2)(3) (+,a,(2) (3) (