20061編譯原理A卷答案

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

2、任意串。三、（12分）構(gòu)造一個(gè)DFA，它接受=a，b上所有滿足下面條件的字符串，其條件是字符串中的每個(gè)b都有a直接跟在右邊。解：正規(guī)式為V=(a|ba)*首先構(gòu)造如下圖所示的NFA MXY(a|ba)*X1abaYX1aY2ba再構(gòu)造轉(zhuǎn)換矩陣如下表、下圖所示。012aabbIIaIbX,1,Y1,Y21,Y1,Y221,Y即：見(jiàn)下表Sab01211221化簡(jiǎn)，先將狀態(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代替，見(jiàn)下表。這樣得到如圖所示的簡(jiǎn)化后的DFA M。10ba0Sab001101四、 （2

3、0分）對(duì)于文法G(E)E E + T | T T T *F | F F PF | PP (E) | i計(jì)算FIRSTVT和LASTVT；該文法是算符優(yōu)先文法嗎？計(jì)算優(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)；消除文法的左遞歸；改寫(xiě)后的文法是否是LL（1）的？為什么？出G的預(yù)測(cè)分析表。解：（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)=) 改寫(xiě)后的文法是LL(1)的。(4)該文法的預(yù)測(cè)分析表如下表所示。ab(),#EEaEbE(F)FFEFFEFFEFFFF,EF六、（16分）對(duì)下述文法構(gòu)造LR型的錯(cuò)誤校正分析程序。（*優(yōu)先級(jí)高于+，同級(jí)運(yùn)算左結(jié)合）EE+EEE*EE(E)Ei并給出輸入串 (i+(*i) 的錯(cuò)誤校正處理過(guò)程。解：使用LR分析法進(jìn)行語(yǔ)法分析，當(dāng)輸入符號(hào)既不能移入棧頂，而棧內(nèi)符號(hào)又不能歸約時(shí)，就意味著發(fā)現(xiàn)了輸入串中的語(yǔ)法錯(cuò)誤，立即調(diào)用相應(yīng)的錯(cuò)誤處理

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

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

9、264065#(E+(E* i)#移進(jìn)902642653#(E+(E*i )#歸約步 驟狀 態(tài) 棧符 號(hào) 棧輸 入 串附 注1002642658#(E+(E*E )#歸約11026426#(E+(E )#移進(jìn)120264269#(E+(E) #歸約1302647#(E+E #歸約14026#(E #調(diào)用e4，將)和狀態(tài)9移進(jìn)棧，并打印“缺右括號(hào)150269#(E) #歸約1601#E #分析完畢七、(12分) 將下列語(yǔ)句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ù)表達(dá)式a+b*(c-d)+e/(c-d)的三元式、間接三元式、樹(shù)、四元式表示。解：三元式間接三元式 間接碼表 四元式(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) (