最新編譯原理課后習題答案

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

2、時參與才能運行，其不產(chǎn)生可執(zhí)行程序文 件，效率低，執(zhí)行速度慢。精品文檔尺N zzfe 弟早1 .喬姆斯基文法體系中將文法分為哪幾類？文法的分類同程序設(shè)計語言的設(shè)計與實現(xiàn)關(guān) 系如何？答：1) 0型文法、1型文法、2型文法、3型文法。2)2 .寫一個文法，使其語言是偶整數(shù)的集合，每個偶整數(shù)不以0為前導(dǎo)。答：Z SME|BS 1|2|3|4|5|6|7|8|9M |D|MDD 0|SB 2|4|6|8E 0|B3 .設(shè)文法G為：N D|NDD 0|1|2|3|4|5|6|7|8|9請給出句子123、301和75431的最右推導(dǎo)和最左推導(dǎo)。答：N ND N3 ND3 N23 D23 123N ND N

3、DD DDD 1DD 12D 123N ND N1 ND1 N01D01 301N ND NDD DDD 3DD 30D 301N ND N1 ND1 N31 ND31 N431 ND431N5431D54317543175431N ND NDD NDDD NDDDD DDDDD 7DDDD 75DDD 754DD 7543D4 .證明文法 S iSeS|iS| i是二義性文法。答：對于句型iiSeS存在兩個不同的最左推導(dǎo):S iSeS iiSesS iS iiSeS所以該文法是二義性文法。5 .給出描述下面語言的上下文無關(guān)文法。(1) L1=anbnci |n=1,i=0 (2) L2=ai

4、bjj=i=1(3) L3=anbmcmdn |m,n=0答：(1) S ABA aAb | abB cB |(2) S ASb |ab精品文檔A a |(3) S aSd | A |A bAc |6 .設(shè)計一個最簡的 DFA M,使其能夠識別所有的被 3整除的無符號十進制整數(shù)。 答：2|5|80|3|6|90|3|6|91|4|71|4|72|5|80|3|6|91|4|77 .設(shè)計一個DFA使其能夠接受被4整除的二進制數(shù)。8 .寫出表達下列各項的正則表達式。(1)二進制數(shù)且為 5的倍數(shù)。(2) 2 =a,b,c,第一個a位于第一個b之前的字符串。(3) 2 =a,b,c,包含偶數(shù)個a的字符

5、串。(4) 2=0, 1,不包含11子用的字符串。(D可以先畫出相應(yīng)的有限自動機：100101BDE1010添加新的開始狀態(tài)S和終止狀態(tài)T:1根據(jù)以上自動機，列出以下方程：S=A A=0A+1B+T B=0C+1D C=0E+1A D=0B+1C E=0D+1E解以上方程組： E=1*0D A=0*1B+6T代入C=01*0D+1A代入C=01*00B+01*01C+1AC=xB+yA其中 x=(01*01)*01*00 y=(01 *01)*1代入B=0C+10B+11CB=(0|11)C+10BB=(10) *(0|11)C將C=xB+yAf弋入上式B=uB+vAB=u vA其中 u=(1

6、0) *(0|11)x v=(10)*(0|11)y將 B=iivA 代入 A=0*1u*vA+dTA=(0 * 1u*v) *0*T將 A代入 S=(0*1u*v)*0*T申(0*1u*v) *0*即為所求。(2)該題目理解為：至少有一個 a和一個b,且a出現(xiàn)在b的前面(可以有問 隔)，則答案為: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| )尺K*弟二早TOKEN同時檢查源程1 .詞法分析器的功能是什么?答：讀源程序的字符序列，逐個拼出單詞，并構(gòu)造相應(yīng)的內(nèi)部表示 序中的詞法錯誤。2

7、 .試分析分隔符(空格、跳格及回車等)對詞法分析的影響。答：空格、跳格、回車等分隔符號對詞法分析不起作用，可以刪除。但是回車符號可以用 于錯誤定位，所以在刪除回車符號前需要統(tǒng)計回車的個數(shù)。3 .給出識別C語言全部實型常數(shù)的自動機。答：(+|-1 )(1-90-9*|0)(.0-90-9*|) (E(+|-| )0-90-9*)4 .寫出識別C語言中所有單詞的 LEX程序。答：L=A-Z | a-zD=0-9D1=1-9%(LL)(L|D|_)* return ;D1D*return (2);+return (3);精品文檔精品文檔第四章1.設(shè)有如下文法GS:S aABbcd |A ASd |B

8、 SAh|eC|C Sf | Cg |(1)求每個產(chǎn)生式的Predict集。(2)該文法是否為 LL(1)文法？為什么？答：Predict(S aABbcd尸aPredict(S)=#,d,f,a,h Predict(A ASd)=a,dPredict(A)=h,a,d,b,ePredict(B SAh)=a,d,hPredict(B eC)=ePredict(B )=bPredict(C Sf)=a,fPredict(C Cg尸a,f,gLL文法。Predict(C )=g,b(2)由于Predict(A ASd) Predict(A ),所以該文法不是2 .下列描述括號匹配的文法中，哪些是

9、LL文法？(1) S (SS |S ) |(2) S (S)S |(3) S S(S)S |(4) S (S | S S (S ) |答：(1)不是，(2)是，(3)不是，(4)不是3 .已知文法 GE:E E+T | TT T*F | FF i | (E)請按遞歸下降法構(gòu)造該文法的語法分析程序。答：求產(chǎn)生式的predict集合：predict(E E+T)=i,(predict(E T)=i,(predict T*F)=i,(predict(T F)=i,(由于文法中非終極符號E 和 T 對應(yīng)的產(chǎn)生式的predict 集合的交集都不為空，法不滿足自頂向下分析的條件，現(xiàn)對文法進行等價變換得到如

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

11、 () if(token +) Match();+ );T();E ();else if(token #,) ;else Error();void T() if(token i,() F();T ();else Error();void T () if(token *) Matc h( * );F();T ();else if(token +,),#) ;else Error();void F() if(token i) Match( i );else if(token () Match( ( );E();Match( ) ); else Error();4 .構(gòu)造一個LL(1)文法G,它能識

12、別語言L:L= | 為字母表上不包括兩個相鄰的1 的非空串，其中=0， 1。并證明你所構(gòu)造的文法是LL(1)文法。答：A 0E | 1FB 0E | 1FC 0EE B IF C IPredict(A 0E)=0Predict(A 1F尸1Predict(B 0E)=0Predict(B 1F尸1Predict(E B尸0,1Predict(E )=#Predict(F C)=0Predict(F )=#對任意非終極符號對應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文法。5 .已知文法 GA為:A aABe|aB Bb | d(1)試給出與GA等價的LL文法G A(2)構(gòu)

13、造G簡LL(1汾析表并給出輸入串a(chǎn)ade#的分析過程。答：所求G A的:AaA(1)AABe(2)A(3)BdB(4)BbB(5)B(6)Predict(A aA )=aPredict(A ABe)=aPredict(A )=#,dPredict(B dB )=dPredict(B bB )=bPredict(B )=e對任意非終極符號對應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文法。(3)分析表如下:abde#A(1)A(2)(3)(3)精品文檔B(4)B，(5)(6)aade#的分析過程如下分析棧輸入流動作A#aade#替換aA #aade#匹配A #ade#替換(

14、2)ABe#ade#替換aABe#ade#匹配A Be#de#替換Be#de#替換(4)dB e#de#匹配B e#e#替換e#e#匹配#成功精品文檔第五章(這章答案是錯的)1 .設(shè)有下列文法：(1) S aAA AbA b(2) S aSSbS aSSSS c(3) S ASS bA SAA a(4) S cAS ccBB ccBB bA cAA a構(gòu)造上述文法的LR(0)歸約活前綴狀態(tài)機，并給出LR(0)分析表。答：(1)Ch05-1-(1)有移入、規(guī)約沖突(2)Ch05-1-(2)Zf .S (1)S .aSSb (2)S .aSSS (3)S7 .c(4)actiongotoabc#S

15、S0s2s51S1AccS2s2s53S3s2s54S4s2s6s57S5R4R4R4R4S6R2R2R2R2S7R3R3R3R3有移入、規(guī)約沖突Ch05-1-(3)Zf S- cA (2)S- ccB (3)B- ccB (4)B- b (5) 2 cA (6)A a (7)actiongotoabc#ABSS0s12S1s3s54S21AccS3R7R7R7R7S4 R6R6R6R6S5s3s9s876S6R3R3R3R3S7 1R2R2R2R2S8s3s107S9R5R5R5R5S10：s3s9s87r iiS11R4R4R4R42.設(shè)有下列文法:(1) S SaS | b(2) S b

16、Sb | cSc | b | c(3) S bSb | bSc | d(4) S aSb | bSa | ab(5) S Sab | bR R S | a(6) S SAB | BA B bA aA | B S AaAb | BbBaBA(8) A aABe | BaB dB |說明上述文法是否為SLR(1反法。若是，請構(gòu)造SLR(1分析表；若不是，請說明理由。答：(1)Ch05-2-(1)不是 SLR (1)(2)Ch05-2-(2)不是 slr (1)Follow(S)=#,b,c-bZf.SS7 .bSbS7.cScSf.bSf.crS b.Sb Sf b.Sf .bSbS7 .cScS

17、f .bSf .cCh05-2-(3) 是 SLR (1)3_S 一 d.1d 2Sf b.SbSf b.ScS- .bSbS 一 .bScS 一 .d5 S- bSb.b4 Sf bS.b Sf bS.ccZf .S (1)S7 .bSb (2)S7 .bSc (3)S7 .d (4)actiongotobcd#SS0s2s31S1AccS2s2s3Ch05-2-7 4S3r R4R4R4S4s5s6S5R2R2R2S6R3R3R36 S- bSc.Ch05-2-(4)不是 SLR( 1)Follow(S)=#,a,b-b-4S- aSb.(5)Ch05-2-(5)不是slr(i)Follo

18、w(R)=#,a(6)0Zf.S S .SAB Sf .BA Bf .b|bCh05-2-(6) 是SLR (1)SJ卡1Zf S.S S.ABZ .aAZ .B3一 a3S B.AZ .aA-B-Z .BBf .ba-5Af B.Bf .b-A-S1189S SA.BS SAB.IBBf .b5一 Z 2B4S- BA.Af a.AAf .aAAf .BBf .bAT7 A-aA.Z-S A SAB (2) A BA (3) A- aA (4) A- B (5) B- b (6)actiongotoab#ABSS01s231S1s6s2Acc85S2R6R6R6Ch05-2-7S31s6s2

19、45S4R3R3R3S5R5R5R5S61s6s275S7R4R4R4S8s29S9R2R2R2Ch05-2- 不是 SLR ( 1)Follow(A)=a,b Follow(B)=a,b0- ZSSf .AaAb Sf .BbBa 2.1-SZ Zf s.4TSf A.aAb-a-3Sf Aa.Ab A一.68Sf AaA.bSf AaAb.ATBf.BTSf B.bBa-b-Sf Bb.Ba B 一.7-o9Sf BbB.aSf BbBa.BT(8)Ch05-2-(8)不是 SLR (1) Follow(B尸a,e3 .設(shè)有下列文法：S aAd | bBd | aBe | bAeA gB

20、g說明該文法是 LR(1)文法，1不是LALR(1)文法。答：Ch05-3是LR文法0 ZfS Sf.aAd SfbBd Sf.aBe SfbAe#-a-5Sfa.Ad Sfa.Be Afg BfgZfS.3 Sfb.Bd Sfb.Ae Afg Bfg# # e d4SfaA.d#-At5SfaB.e#-Bt6Ag.dbg.e9SfbA.e#一At10S-bB.d #-Bf11 g A-g.B-g.7S-aAd.#-d-i8S-aBe.#一g12| SfbAe.#-e-d-J13 S-bBd.#Ch05-3不是LALR文法4 .設(shè)有下列文法：(1) E E+T | TT TF | TF (E)

21、 | F* | a | b(2) S Aa | bAc | dc | bda A d說明上述文法是否為SLR(1區(qū)法？是否為LALR(1戌法？并構(gòu)造相應(yīng)的分析表。答：Ch05-4-(1)不是 SLR文法Follow(T)=#,(,a,b,+,)F-(E).卜)Zf.E ef.e+t ef.t TfTF TfTEt1 ZfE.efe.+tEfE+.T* T f .TFT f .TT+-T-j3E-E+T.TfT.F TfT.F f(E) F f .F* Ff.a Ff.b -rr 8T-TF. F-F.*-a F-a.7Ffb.1110F-(E.)Le-efe.+tf-(.e) ef.e+t e

22、f.t TfTF TfT-TEfT.TfT.F TfT. Ff(E) Ff.F* Ff.a Ff.b5- F f F*-FJ J-a.TF#+(abT一.T#+(ab+9F-(E.) efe.+t#+(ab*)#+(ab*),10F-(E).#+(ab*)E3ef e+t.#+TfT.F#+(abT f T.#+(abFf(E)#+(ab* -F fF*#+(ab*F f.a#+(ab* F fb#+(ab*工18f-(.e)#+(ab*)ef.e+t#+(ab*)Ef.T#+(ab*)T f .TF#+(ab*)T f .T#+(ab*)5F-F*.#+(ab*J,*4T-TF.F -F.*

23、#+(ab#+(ab*Ft6Fa.#+(ab*7F fb.#+(ab*11e f t.#+(ab*)TfT.F#+(ab*)T f T.#+(ab*)F-.(E)#+(ab*)Ff.F*#+(ab*)Ff .a#+(ab*)Ff.b#+(ab*)-Tt(2)Ch05-4-(2)不是 SLR(1)文法 Follow(A)=a,cCh05-4-(2) 是 LALR(1)文法ZSr#TSr0 zf .sr#SAa.r#-Ta4-At S-A.aSf.AaSf.bAcSf.dcSf.bdaA f.d# # # a6S-b.AcSfb.daAf.d9SfbA.cSfd.c Afd.7 S-bd.a A

24、fd.S- bAc. #S dc.S-bda.Z. .S(1)Sf .Aa (2)Sf .bAc (3)Sf .dc(4)Sf .bda (5)Af.d(6)actiongotoabcd#ASS0s6s241S1AccS2R6s3S3R4S4s5S5R2S6s79S7s8R6S8R5S9s10S10R35 .設(shè)有下列文法：L MLb | aM說明上述文法是否為 LR(1)文法，若不是，請說明理由。答：Ch05-5 是 LR(1)文法精品文檔精品文檔第六章1. 試寫出下列類型的內(nèi)部表示：egerb.ARRAY1.5 of RECORDi:integer; b:boolean ENDc.

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

26、（ A： atype； VAR 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;）。

27、6 .給出題1中程序掃描到語句 c=a+b+x時相應(yīng)的全局符號表（采用外拉鏈的散列表結(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 ELSEIF x 0 DOWHILE y 0 DOBEGIN y:=y-x; x:=x-1 END3 .給出如下程序段的四元式序列。(四元式的操作符可用自身代替)。其中A: Array of 1.10of integer。a:=1;while a=10 dobegin if ab thenAa:=Ab+2;else a:=a+1;b:=b+1; end4 .試將FOR語句翻譯成四元式序列。5 .試將UNTIL語句翻譯成四元式序列。6