編譯原理課后習(xí)題答案

1、第一章1典型的編譯程序在邏輯功能上由哪幾部分組成？答：編譯程序主要由以下幾個部分組成：詞法分析、語法分析、語義分析、中間代碼生成、中間代碼優(yōu)化、目標代碼生成、錯誤處理、表格管理。2. 實現(xiàn)編譯程序的主要方法有哪些？答：主要有：轉(zhuǎn)換法、移植法、自展法、自動生成法。3. 將用戶使用高級語言編寫的程序翻譯為可直接執(zhí)行的機器語言程序有哪幾種主要的方式？答：編譯法、解釋法。4. 編譯方式和解釋方式的根本區(qū)別是什么？答：編譯方式：是將源程序經(jīng)編譯得到可執(zhí)行文件后，就可脫離源程序和編譯程序單獨執(zhí)行，所以編譯方式的效率高，執(zhí)行速度快；解釋方式：在執(zhí)行時，必須源程序和解釋程序同時參與才能運行，其不產(chǎn)生可執(zhí)行程序

2、文件，效率低，執(zhí)行速度慢。第二章1. 喬姆斯基文法體系中將文法分為哪幾類？文法的分類同程序設(shè)計語言的設(shè)計與實現(xiàn)關(guān)系如何？答：1）0型文法、1型文法、2型文法、3型文法。2）2. 寫一個文法，使其語言是偶整數(shù)的集合，每個偶整數(shù)不以0為前導(dǎo)。答：ZSME | BS1|2|3|4|5|6|7|8|9Me | D | MDD0|SB2|4|6|8E0|B3. 設(shè)文法G為：N D|NDD 0|1|2|3|4|5|6|7|8|9請給出句子123、301和75431的最右推導(dǎo)和最左推導(dǎo)。答：NNDN3ND3N23D23123NNDNDDDDD1DD12D123NNDN1ND1N01D01301NNDNDDD

3、DD3DD30D301NNDN1ND1N31ND31N431ND431N5431D543175431NNDNDDNDDDNDDDDDDDDD7DDDD75DDD754DD7543D754314. 證明文法 SiSeS|iS| i是二義性文法。答：對于句型iiSeS存在兩個不同的最左推導(dǎo)：SiSeSiiSesSiSiiSeS所以該文法是二義性文法。5. 給出描述下面語言的上下文無關(guān)文法。（1） L1=anbnci |n=1,i=0 （2） L2=aibj|j=i=1（3） L3=anbmcmdn |m,n=0答：（1） SABAaAb | abBcB | e（2） SASb |abAa | e（

4、3） SaSd | A | eAbAc | e6. 設(shè)計一個最簡的DFA M,使其能夠識別所有的被3整除的無符號十進制整數(shù)。答：7. 設(shè)計一個DFA,使其能夠接受被4整除的二進制數(shù)。答：8. 寫出表達下列各項的正則表達式。（1）二進制數(shù)且為5的倍數(shù)。（2）=a,b,c,第一個a位于第一個b之前的字符串。（3）=a,b,c,包含偶數(shù)個a的字符串。（4）=0，1,不包含11子串的字符串。答：（1）可以先畫出相應(yīng)的有限自動機:添加新的開始狀態(tài)S和終止?fàn)顟B(tài)T:根據(jù)以上自動機，列出以下方程： S=A A=0A+1B+T B=0C+1D C=0E+1A D=0B+1C E=0D+1E解以上方程組： E=1

5、*0D A=0*1B+0*T代入 C=01*0D+1A代入 C=01*00B+01*01C+1A C=xB+yA 其中x=(01*01)*01*00 y=(01*01)*1代入 B=0C+10B+11C B=(0|11)C+10B B=(10)*(0|11)C將C=xB+yA代入上式 B=uB+vA B=u*vA其中u=(10)*(0|11)x v=(10)*(0|11)y將B=u*vA代入 A=0*1u*vA+0*T A=(0*1u*v)*0*T將A代入 S=(0*1u*v)*0*T串(0*1u*v)*0*即為所求。（2）該題目理解為：至少有一個a和一個b，且a出現(xiàn)在b的前面（可以有間隔），

6、則答案為：c*a(a|c)*b(a|b|c)*（3）(b|c)*a(b|c)*a)*(b|c)*(a(b|c)*a | b | c)*（4）(0|10)*(1|e)第三章1. 詞法分析器的功能是什么？答：讀源程序的字符序列，逐個拼出單詞，并構(gòu)造相應(yīng)的內(nèi)部表示TOKEN；同時檢查源程序中的詞法錯誤。2. 試分析分隔符（空格、跳格及回車等）對詞法分析的影響。答：空格、跳格、回車等分隔符號對詞法分析不起作用，可以刪除。但是回車符號可以用于錯誤定位，所以在刪除回車符號前需要統(tǒng)計回車的個數(shù)。3. 給出識別C語言全部實型常數(shù)的自動機。答：(+|-|e)(1-90-9*|0)(.0-90-9*|e) (E(

7、+|-|e)0-90-9*)4. 寫出識別C語言中所有單詞的LEX程序。答：L=A-Z | a-zD=0-9D1=1-9%(L|_)(L|D|_)*return (1);D1D*return (2);+return (3);第四章1. 設(shè)有如下文法GS:SaABbcd | eAASd | eBSAh | eC | eCSf | Cg | e(1) 求每個產(chǎn)生式的Predict集。(2) 該文法是否為LL(1)文法？為什么？答：(1)Predict(SaABbcd)=aPredict(S e)=#,d,f,a,h Predict(AASd)=a,dPredict(A e)=h,a,d,b,ePr

8、edict(BSAh)=a,d,hPredict(B eC)=ePredict(B e)=bPredict(CSf)=a,fPredict(C Cg)=a,f,gPredict(C e)=g,b(2)由于Predict(AASd) Predict(A e)，所以該文法不是LL(1)文法。2. 下列描述括號匹配的文法中，哪些是LL(1)文法？(1)S(SS | eS ) | e(2)S(S)S | e(3)SS(S)S | e(4)S(S | SS(S) | e答：(1)不是，(2)是，(3)不是，(4)不是3. 已知文法GE:EE+T | TTT*F | FFi | (E)請按遞歸下降法構(gòu)造該

9、文法的語法分析程序。答：求產(chǎn)生式的predict集合：predict(EE+T)=i,(predict(ET)=i,(predict(TT*F)=i,(predict(TF)=i,(由于文法中非終極符號E和T對應(yīng)的產(chǎn)生式的predict集合的交集都不為空，所以該文法不滿足自頂向下分析的條件，現(xiàn)對文法進行等價變換得到如下文法：ETEE+TE | eTFTT*FT | eFiF(E)求新文法的predict集合：Predict(ETE)=(,iPredict(E+TE)=+Predict(Ee)=#,)Predict(TFT)=i,(Predict(T*FT)=*Predict(Te)=+,),#

10、Predict(Fi)=iPredict(F(E)=(由于以上文法中任意非終極符號對應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以滿足自頂向下分析的條件，所以可以寫出如下的遞歸下降語法分析偽代碼：Void E() if(token(,i) T();E(); else Error();void E() if(token+) Match(+);T();E(); else if(token#,) ; else Error();void T() if(tokeni,() F();T(); else Error();void T() if(token*) Match(*);F();T(); else

11、if(token+,),#) ; else Error();void F() if(tokeni) Match(i); else if(token() Match();E();Match(); else Error();4. 構(gòu)造一個LL(1)文法G，它能識別語言L:L=w | w為字母表S上不包括兩個相鄰的1的非空串，其中S=0，1。并證明你所構(gòu)造的文法是LL(1)文法。答：A0E | 1FB0E | 1FC0EEB | eFC | ePredict(A0E)=0Predict(A1F)=1Predict(B0E)=0Predict(B1F)=1Predict(EB)=0,1Predict(

12、Ee)=#Predict(FC)=0Predict(Fe)=#對任意非終極符號對應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文法。5. 已知文法GA為：AaABe | aBBb | d(1) 試給出與GA等價的LL(1)文法GA。(2) 構(gòu)造GA的LL(1)分析表并給出輸入串a(chǎn)ade#的分析過程。答：(1)所求GA為：AaA(1)AABe (2)A e(3)BdB(4)BbB (5)B e(6)Predict(AaA)=aPredict(AABe)=aPredict(Ae)=#,dPredict(BdB)=dPredict(BbB)=bPredict(Be)=e對任意非終

13、極符號對應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文法。(3) 分析表如下：abde#A(1)A(2)(3)(3)B(4)B(5)(6)aade#的分析過程如下分析棧輸入流動作A#aade#替換(1)aA #aade#匹配A #ade#替換(2)ABe#ade#替換(1)aABe#ade#匹配ABe#de#替換(3)Be#de#替換(4)dBe#de#匹配Be#e#替換e#e#匹配#成功第五章（這章答案是錯的）1. 設(shè)有下列文法：(1)SaAAAbAb(2)SaSSbSaSSSSc(3)SASSbASAAa(4)ScASccBBccBBbAcAAa構(gòu)造上述文法的LR(0

14、)歸約活前綴狀態(tài)機，并給出LR(0)分析表。答：(1)(2)(3)(4)2. 設(shè)有下列文法：(1)SSaS | b(2)SbSb | cSc | b | c(3)SbSb | bSc | d(4)SaSb | bSa | ab(5)SSab | bRRS | a(6)SSAB | BABbAaA | B(7)SAaAb | BbBaBeAe(8)AaABe | BaBdB | e說明上述文法是否為SLR(1)文法。若是，請構(gòu)造SLR(1)分析表；若不是，請說明理由。答：(1)(2)(3)(4)(5)(6)(7)(8)3. 設(shè)有下列文法：SaAd | bBd | aBe | bAeAgBg說明該

15、文法是LR(1)文法，但不是LALR(1)文法。答：4. 設(shè)有下列文法：(1)EE+T | TTTF | TF(E) | F* | a | b(2)SAa | bAc | dc | bdaAd說明上述文法是否為SLR(1)文法？是否為LALR(1)文法？并構(gòu)造相應(yīng)的分析表。答：(1)(2)5. 設(shè)有下列文法：LMLb | aMe說明上述文法是否為LR(1)文法，若不是，請說明理由。答：第六章1.試寫出下列類型的內(nèi)部表示： eger b.ARRAY 1.5 of RECORD i:integer; b:boolean END c.ARRAY 1.5 of RECORD a:ARRAY

16、1.10; r:RECORD i,j:integer END END d. RECORD r: RECORD x,y:real END;a: ARRAY 1.10 of integer END2. 設(shè)當(dāng)前層數(shù)為l，可用區(qū)距為101，且有下列程序段： CONST mm=333；nn=444； TYPE atype = ARRAY1.10 OF real; rtype = RECORD i,j:integer END; VAR a,b:atype; x,y:real 試寫出各標識符的內(nèi)部表示。3. 設(shè)當(dāng)前層數(shù)和區(qū)距分別為l和off，且有函數(shù)說明首部： FUNCTION f（A：atype；VAR

17、B：atype；VAR X：real）：integer 其中atype的定義見題5，試寫出f的內(nèi)部表示。4. 要求在下面括號中寫上相應(yīng)（層數(shù)）和區(qū)距（off）。 （）（）PROCEDURE g（A：atype；（）（）VAR B：atype；（）（）VAR X：real（）（）（）（）.5. 給出下面C程序掃描到語句c=a+b+x時相應(yīng)的全局符號表(采用順序表結(jié)構(gòu))。main（）int a=0;float c=1.0;float a=3.0;float x=1.3;float b=0.3; int b=10; c=a+b+x;6. 給出題1中程序掃描到語句c=a+b+x時相應(yīng)的全局符號表(采用

18、外拉鏈的散列表結(jié)構(gòu))。7. 根據(jù)標識符的作用域規(guī)則，分別給出圖6.5的程序中，過程P、Q、R、S中有效的標識符。第七章1. 將算術(shù)表達式 (a+b)*(c+d)-(a+b+c) 翻譯成四元式序列。2. 將下列語句翻譯成四元式序列：a. IF x0 THEN x:=0 ELSE x:=1b. WHILE x0 DO x:=x-1c. IF x0 THEN x:=x+1 ELSE IF x 0 DOWHILE y 0 DO BEGIN y:=y-x; x:=x-1 END3. 給出如下程序段的四元式序列。(四元式的操作符可用自身代替)。其中A：Array of 1.10 of integer。 a

19、:=1;while a=10 do begin if ab then Aa:=Ab+2; else a:=a+1; b:=b+1; end4. 試將FOR語句翻譯成四元式序列。5. 試將UNTIL語句翻譯成四元式序列。6. 試將CASE語句翻譯成四元式序列。7. 試給出4、5、6題中翻譯過程的語法制導(dǎo)程序。第八章1. 將下面的程序段劃分為基本塊并畫出其程序流圖。read(A);read(B);F:=1;C:=A*A;D:=B*B;if C100 goto L2;goto L3;L2:F:=F-1;goto L1;L3:write(E);2. 假設(shè)有如下語句序列，寫出常表達式優(yōu)化前和優(yōu)化后的四元式中間代碼。(1)i:=1;(2)a:=20;j:=i*(i+1);b:=a*(a+10);k:=2*(i+j)