編譯原理習題解答參考.doc

編譯原理習題解答參考1.計算機執(zhí)行用高級語言編寫的程序的途徑有哪些？它們之間主要區(qū)別是什么？答：計算機執(zhí)行用高級語言編寫的程序途徑有兩種：解釋方式和編譯方式。解釋方式下直接對源程序進行解釋執(zhí)行，并得到計算結(jié)果，特點是計算機并不事先對高級語言進行全盤翻譯將其全部變?yōu)闄C器代碼，而是每讀入一條語句，就用解釋器將其翻譯為機器代碼，予以執(zhí)行，然后再讀入下一條高級語句，翻譯為機器代碼，再執(zhí)行，如些反復(fù)，即邊翻譯邊執(zhí)行；編譯方式下對源程序的執(zhí)行需要經(jīng)過翻譯階段和運行階段才能得到計算結(jié)果，其特點是計算機事先對高級語言進行全盤翻譯將其全部變?yōu)闄C器代碼，再統(tǒng)一執(zhí)行，即先翻譯后執(zhí)行。簡單來說解釋方式不生成目標代碼，編譯方式生成目標代碼。2.名字與標識符的區(qū)別是什么？答：在程序設(shè)計語言中，凡是以字母開頭的有限個字母數(shù)字的序列都是標識符。當給予一個標識符確切的含義后，該標識符就叫做一個名字。標識符是一個沒有意義的字符序列，而名字有確切的含義，一個名字代表一個存儲單元，該單存放該名字的值。此外，名字還有屬性（如類型和作用域等）。如objectint, 作為標識符，它沒有任何含義，但作為名字，它可能表示變量名、函數(shù)名等。3.許多編譯程序在真正編譯之前都要進行預(yù)處理操作，請問預(yù)處理的目的是什么？預(yù)處理主要做哪些工作？答：在源程序中有時存在多個連續(xù)的空格、回車、換行及注釋等編輯性字符，它們不是程序的必要組成部分，它們的意義只是改善程序的易讀性和易理解性。為了降低編譯程序的處理負擔，許多編譯程序在編譯之前通過預(yù)處理工作將這些部分刪除。 預(yù)處理的主要工作是對源程序進行格式方面的規(guī)范化處理，如去掉注釋、將回車換行變成空格、將多個空格替換為一個空格等。P35 4，6，7，8，9，11（1，2）4答：256，86（1）答：所產(chǎn)生的語言是：所有正整數(shù)集，且可以以0打頭；0127，34，568的推導略。7答：SABD|AD|D A2|4|6|8|D B0|A|B0|BA D1|3|5|7|98答：略。9答：文法對于句子iiieii存在兩棵不同的語法樹，所以該文法是二義性文法。11（1）答：SAB|A SAB AaAb|ab AaAb|ab BBc|c BBc|c| （2）答：SAB|B AaA|a BbBc|bc1.化簡文法GS： SBe B Ce|Af A Ae|e C Cf D f答：SBeBAfAAe|e2.給出描述語言L(G)=a2nbn|n1的2型文法。答：語言中語句的特點是a的個數(shù)是b的個數(shù)的2倍，且a全部在句子的前部分，b全部在句子的后部分，2型文法為：Saab|aaSb3.構(gòu)造一個文法，使其描述的語言是不能被5整除的偶整數(shù)集合。S（+|-）AB|BA0|1|2|3|4|5|6|7|8|9|AAB2|4|6|8 如果不以0打頭，則文法描述如下：S（+|-）（AD|D）AAB|CB0|C|BBC1|2|3|4|5|6|7|8|9D2|4|6|8P64 7（1），8（123）127答：1|（0|1）*1011)NFA如下：XY53241Y1111002）確定化：II1I00 X1,3,21 1,3,23,2,43,22 3,2,43,2,43,2,53 3,23,2,43,24 3,2,53,2,4,Y3,25 3,2,4,Y3,2,43,2,53）DFA自己畫8（1）（0|1）*01 （2）（0|1| |9）*(0|5) (3)（00|11）*（10|01）12答：a圖：首先用子集法確定化：IIaIbA 00,11B 0,10,11C 10用ABC表示三個狀態(tài)，則確定化后的自動機如下所示：ACBBaaab下面用分割法將其最小化：首先得到兩個子集：非終態(tài)K1=A，C和終態(tài)K2=B，由于狀態(tài)A和狀態(tài)C輸入a后分別到達狀態(tài)B和A，故狀態(tài)A和狀態(tài)C不等價，K1不能再分割，所以該DFA已經(jīng)是最小化的DFA了。（b）答：觀察原圖已經(jīng)是DFA了，最小化如下：首先得到兩個子集：非終態(tài)和終態(tài)：2，3，4，5和0，10，1a=10,10,1b=2,42,3,4,5所以0，1是不可分割的因為2，3，4，5a=1，3，0，5又因為2，4a=0，10,13，5a=3，5所以該狀態(tài)集劃分為兩個狀態(tài)集2，4和3，52，4b=3，53，53，5b=2，42，4所以狀態(tài)2，4和3，5不可分割，最終狀態(tài)集劃分三個狀態(tài)集：0，1 2，4 3，5，得到最小化的DFA如下：A320aabbbaP81 23、文法GA如下： 4、已知文法GS如下：ABaC|CbB S aABbcd|B Ac|c A ASd| C Bb|b B SAh|eC| 消除其左遞歸 C Sf|Cg| D aBD| 求每一非終結(jié)符的FIRST 合和FOLLOW集合， 該文法是LL（1）文法嗎？為什么？2 解答：1) FIRST(E)=(,a,b, FIRST(E)=+, FIRST(T)= (,a,b, FIRST(T)= (,a,b, FIRST(F)= (,a,b, FIRST(F)= *, FIRST(P) (,a,b, FOLLOW(E)=),# FOLLOW(E)= ),# FOLLOW(T)= ),+,# FOLLOW(T)= ),+,# FOLLOW(F)= ),+,#, (,a,b, FOLLOW(F)= ),+,#, (,a,b, FOLLOW(P)= ),+,#, (,a,b, 2) 由上知，文法的所有首符集兩兩不相交。 FIRST（E）與FOLLOW（E）= FIRST（T）與FOLLOW（T）= FIRST（F）與FOLLOW（F）= 所以，該文法是LL（1）文法。 3）分析表和遞歸下降分析程序自己完成。3解答：利用消除左遞歸的算法，將非終結(jié)符排序為：U1=A，U2=B，U3=C，執(zhí)行算法得： U1代入U2得：BBaCc|CbBc|c,消除B的左遞歸，BC bBcB|c BBaCc B| U2代入U3得：CCbBcBb|cB|bCc BbC|b CCbBc Bb C|所以，方法消除左遞歸后的結(jié)果為：ABaC|CbBBC bBcB|c BBaCc B|Cc BbC|b CCbBc Bb C|4解答：首先將文法化簡得到如下文法： S aABbcd| A ASd| B SAh|eC| C Sf|Cg| 非終結(jié)符的FIRST集合如下：FIRST（S）=a, FIRST(A)=a,d, FIRST(B)=a,d,e,h, FIRST(C)=a,f,g, 非終結(jié)符的FOLLOW集合如下：FOLLOW(S)=#,a,d,h,fFOLLOW(A)=b,a,d,h,eFOLLOW(B)=bFOLLOW(C)=b,g該文法不是LL（1）文法，因為FIRST（C Sf）FIRST（C Cg）FIRST(A) FOLLOW(A) 作業(yè)：P133 1,3,51解答：E=E+T=E+T*F短語：T*F，E+T*F直接短語：T*F句柄 ：T*F3解答： FIRSTVT（S）=a (FIRSTVT（T）=, a (LASTVT（S）=, a (LASTVT（T）=, a (1)=S(T)有（=）2） T, 則有LASTVT（T） ， T), 則有LASTVT（T） )3) (T，則有 （FIRSTVT(T) , S, 則有 ,(=,)后面的答案略。5解答：4、文法GS如下,是LR（1）文法但不是LALR（1）文法，對嗎？為什么？（武大） S aAa|aBb|bAb|bBa A c B c解答：識別擴展后文法活前綴的DFA如圖所示：I0:S.S,#S.aAa,#S.aBb,#S.bAb,#S.bBa,#I1:SS,.#I2:Sa.Aa,#Sa.Bb,#A.c,aB.c,bI3:Sb.Ab,#Sb.Ba,#A.c,bB.c,aI4:SaA.a,#I5:SaB.b,#I6:Ac.,aAc.,bI7:SbA.b,#I8:SbB.a,#I9:Ac.,bAc.,aI10:SaAa.,#I11:SaBb.,#I12:SbAb.,#I13SbBa.,#cABAbSaBcaabb 由于不存在移進-歸約沖突和歸約-歸約沖突，所以文法是LALR（1）文法。若將同心集I6和I9合并，則會出現(xiàn)歸約歸約沖突，所以文法不是LALR（1）文法。原題說法不正確。5、已知文法GS如下，請構(gòu)造該文法的算符優(yōu)先關(guān)系矩陣，并判斷是否為算符優(yōu)先文法？（清華） S iBtS|iBtAeS|a A iBtAeS|a B b解答：求該非終結(jié)符的FIRSTVT集合和LASTVT集合 FIRSTVT（S）=i,a FIRSTVT（A）= i,a FIRSTVT（B）=b