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

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

2、產(chǎn)生可執(zhí)行程序文 件，效率低，執(zhí)行速度慢。35 / 28第二早1. 喬姆斯基文法體系中將文法分為哪幾類？文法的分類同程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)與實(shí)現(xiàn)關(guān) 系如何？答：1）0型文法、1型文法、2型文法、3型文法。2）2. 寫一個(gè)文法，使其語(yǔ)言是偶整數(shù)的集合，每個(gè)偶整數(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請(qǐng)給出句子123、301和75431的最右推導(dǎo)和最左推導(dǎo)。答:NNDN3ND3 N23D23123NNDNDDDDD 1DD12D123NNDN1ND

3、1 N01D01301NNDNDDDDD 3DD30D301NNDN1ND1 N31ND31N431ND431N5431D543175431NNDNDDNDDD NDDDDDDDDD7DDDD75DDD 754DD7543D4.證明文法S iSeS|iS| i是二義性文法。75431答：對(duì)于句型iiSeS存在兩個(gè)不同的最左推導(dǎo):S iSeS iiSesS iS iiSeS所以該文法是二義性文法。5. 給出描述下面語(yǔ)言的上下文無關(guān)文法。（1）L1=anbnci | n>=1,i>=0 （2）L2=abj|j>=i>=1（3）L3=anbmcmdn |m,n>=0答：

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

5、S=A A=0A+1B+T B=0C+1D C=0E+1A D=0B+1C E=0D+1E解以上方程組：E=1*0DA=0*1B+0T代入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+yA弋入上式B=uB+vAB=u vA其中 u=(10) *(0|11)x v=(10)*(0|11)y將 B=UvA 代入 A=0*1u*vA+0T* * * *A=(0 1uv) 0T將 A代入S=(0*1u*v)*0*T串(0

6、*1u*v)*0*即為所求。(2) 該題目理解為：至少有一個(gè) a和一個(gè)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| )AVV*第二早1詞法分析器的功能是什么？答：讀源程序的字符序列，逐個(gè)拼出單詞，并構(gòu)造相應(yīng)的內(nèi)部表示TOKEN同時(shí)檢查源程序中的詞法錯(cuò)誤。2. 試分析分隔符(空格、跳格及回車等)對(duì)詞法分析的影響。答：空格、跳格、回車等分隔符號(hào)對(duì)詞法分析不起作用，可以刪除。但是回車符號(hào)可以用于錯(cuò)誤定位，所以在刪除回車符號(hào)前需要統(tǒng)計(jì)回車的個(gè)數(shù)

7、。3. 給出識(shí)別C語(yǔ)言全部實(shí)型常數(shù)的自動(dòng)機(jī)。答：(+卜1 )(1-90-9*|0)(.0-90-9*|) (E(+|-| )0-90-9*)4. 寫出識(shí)別C語(yǔ)言中所有單詞的LEX程序。答：L=A-Z | a-zD=0-9D1= 1-9%(L|_)(L|D|_)* return (1);D1D*return (2);+return (3);第四章1. 設(shè)有如下文法GS:S aABbcd |A ASd |B SAh|eC|C Sf | Cg |(1) 求每個(gè)產(chǎn)生式的Predict集。(2) 該文法是否為 LL(1)文法？為什么？答：Predict(S aABbcd)=aPredict(S)=#,d

8、,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,gPredict(C )=g,bLL（1）文 法。(2)由于Predict(A ASd) Predict(A )，所以該文法不是2. 下列描述括號(hào)匹配的文法中，哪些是LL(1)文法？(1) S (SS' |S' ) | S (S)S |(3) S S(S)S | S (S | SS' (S')|答:（1）不是，

9、（2）是，（3）不是，（4）不是3.已知文法GE:E E+T | TT T*F | FF i | (E)請(qǐng)按遞歸下降法構(gòu)造該文法的語(yǔ)法分析程序。答:求產(chǎn)生式的predict 集合：predict(EE+T)=i,(predict(ET)=i,(predict(TT*F)=i,(predict(TF)=i,(由于文法中非終極符號(hào)E和T對(duì)應(yīng)的產(chǎn)生式的predict集合的交集都不為空,法不滿足自頂向下分析的條件，現(xiàn)對(duì)文法進(jìn)行等價(jià)變換得到如下文法：E TE'E' +TE' |T FT'T' *FT' |FiF (E)求新文法的 predict 集合：Pr

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

11、en +) Match( else if(token #,) ; else Error();'();+' );T();E' ();Void E()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();Ma

12、tch( ) ');else Error();4. 構(gòu)造一個(gè)LL(1)文法G,它能識(shí)別語(yǔ)言L:L= | 為字母表 上不包括兩個(gè)相鄰的 1 的非空串 ，其中 =0， 1。 并證明你所構(gòu)造的文法是LL(1)文法。答：A 0E|1FB 0E | 1FC 0EE B |F C |Predict(A 0E)=0Predict(A 1F)=1Predict(B 0E)=0Predict(B 1F)=1Predict(E B)=0,1Predict(E )=#Predict(F C)=0Predict(F )=#對(duì)任意非終極符號(hào)對(duì)應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文法

13、。5. 已知文法 GA為：A aABe|aB Bb | d(1) 試給出與GA等價(jià)的LL文法G' A(2) 構(gòu)造G' A的 LL(1)分析表并給出輸入串a(chǎn)ade#的分析過程。(1)所求G A為:A aA'(1)A' ABe(2)A'(3)B dB'(4)B' bB'(5)B'(6)Predict(AaA' )=aPredict(AABe)=aPredict(A')=#,dPredict(BdB' )=dPredict(BbB' )=bPredict(B')=e對(duì)任意非終極符號(hào)對(duì)應(yīng)的產(chǎn)

14、生式的predict集合的交集都為空，所以該文法是LL(1)文法。(3)分析表如下:abde#A(1)A'(2)(3)(3)BB'aade#的分析過程如下分析棧輸入流動(dòng)作A#aade#替換(1)aA' #aade#匹配A' #ade#替換ABe#ade#替換(1)aA'e#ade#匹配A' Be#de#替換Be#de#替換dB' e#de#匹配B' e#e#替換e#e#匹配#成功第五章(這章答案是錯(cuò)的)1. 設(shè)有下列文法：(1)SaAAAbAbSaSSbSaSSSScSASSbASAAaScASccBBccBBbAcAAa構(gòu)造上述

15、文法的LR(O)歸約活前綴狀態(tài)機(jī)，并給出LR(O )分析表。答：(1)Ch05-1-(1)有移入、規(guī)約沖突Ch05-1-(2)Z .S(1)S .aSSb (2)S .aSSS S .c (4)actio ngotoabc#SSOs2s51S1AccS2s2s53S3s2s54S4s2s6s57S5R4R4R4R4S6R2R2R2R2S7R3R3R3R3Ch05-1-(3)有移入、規(guī)約沖突ZS S cA S ccB B ccB B b (5) A cA A a (7)2.設(shè)有下列文法:acti ongotoabc#ABSS0s12S1s3s54S2：AccS3R7R7R7R7S4 :R6R6R

16、6R6S5s3s9s876S6R3R3R3R3S7 :R2R2R2R2S8s3s107S9R5R5R5R5S10：s3s9s87r 11S11R4R4R4R4(1)SSaS | bSbSb|cSc|b | cSbSb|bSc|dSaSb | bSa | abSSab | bRRS | aSSAB | BABbAaA | BSAaAb | BbBaBA(8) A aABe | BaB dB |說明上述文法是否為SLR(1文法。若是，請(qǐng)構(gòu)造 SLR(1分析表；若不是，請(qǐng)說明理由。答：(1)Ch05-2-(1)不是 SLR( 1)Follow(S)=#,a34aS Sa.SS .SaSS .b-ST

17、EaS SaS.S S.aSbCh05-2-(2)不是 slr (1)Follow(S)=#,b,c0Z.S-bS .bSbSf .cScS .bS .c1S b.SbS b.S .bSbS .cScS .bS .c03Z .S-d5S d.S .bSb1S .bSc2S .d>S b.SbSS b.Sc*1S .bSb1Z S.bS .bScS .d(1)Ch05-2-(3)是 SLR5S bSb.hb4OS bS.bSS bS.cc6S bSc.Z .S (1)S .bSb S .bSc S .d (4)actio ngotobcd#SS0s2s31S1AccS2s2s3Ch05-2

18、-7 4S3P R4R4R4S4s5s6S5R2R2R2S6R3R3R3Ch05-2-不是 SLR ( 1)Follow(S)=#,a,bCh05-2-(5)不是 SLR (1)Follow(R)=#,aS4 SAB 4 BA At aA At B (5)Bt b (6)actiongotoab#ABSS0s231S1s6s2Acc85S2R6R6R6-C105-2-/S3 :s6s245S4R3R3R3S5R5R5R5S6s6s275S7R4R4R4S8s29S9R2R2R2Ch05-2- 不是 SLR ( 1)Follow(A)=a,b Follow(B)=a,bSt .AaAb4St B

19、bBa-AT2St Aa Ab68o. dudciAt .St a.aAb-a-iAt .-ATSt AaA b-bJSt AaAb.-BTBt .5St B.bBa970 Zt .SZts .St Bb.BaBt .BTSt BbB.a-e St BbBa.(8)Ch05-2-(8) 不是 SLR (1) Follow(B)=a,e3.設(shè)有下列文法：S aAd | bBd | aBe | bAeA gB g說明該文法是 LR(1)文法，但不是LALR(1)文法。答：Ch05-3是LR文法0Z t .s St .aAd St .bBdSt .aBe St .bAe#%sZ t s.#aT2St

20、 a.Ad#St a.Be#A t .gdB t .ge-B-3St b.Bd#St b.Ae#A t .geB t .gdA2St a.Ad#St a.Be#0A t .gdZt .S#-a->B t .geSt .aAd#St .bBd#St .aBe#St .bAe#-bp3Ch05-3不是LALR文法-BT# e dSt b.Bd St b.Ae A t .gBt .gS1 Zt s.St aA.d6'Atg.dB t g.e5St aB.e #7St aAd.#-d-i8St aBe.#912St bA.e#誦| St bAe.#10dT13St bBd.#11 A t

21、g.eB t g.dSt bB.d I#4St aA.d#|-A彳5St aB.e#StaBe. I #6A t g. B t g.d, ee, dg.9-AT7St aAd.#812St bAe.#1 101 13St bB.d#St bBd.#St bA.e#-BT4. 設(shè)有下列文法：(1) E E+T | TT TF | TF (E) | F* | a | b(2) S Aa | bAc | dc | bdaA d說明上述文法是否為 SLR(1)文法？是否為L(zhǎng)ALR(1)文法？并構(gòu)造相應(yīng)的分析表。答: (1)Ch05-4-(1)不是 SLR(1)文法 Follow(T)=#,(,a,b,

22、+,)Z .EE.E+TE.TT .TFT .T1 ZE.E E.+TE E+.T申 T .TFT .T"T+T-j3 E E+T. TT.F TT. F .(E) F .F* F .a F .b4TTF.FF.*F b.11Ch05-4-(1)5 F F*.(*-r3F (.E)E .E+TE .T T .TF T .T100-9F (E).F(E.) E E.+T£E不是LALR(1)文法Z E.E E.+T#+ -fZ .E E .E+T E .TT.TF T.T# #+#+ #+(ab #+(ab2EE+.T T.TF T.T#+(ab*)#+(ab#+(ab7 L

23、F (E.) E E.+TTF(E).#+(ab*)#+(ab*)#+(ab*) (-TET.TT.F TT.F.(E)F.F*F.aF.b4 -CHE E+T.#+T T.F#+(abT T.#+(abF .(E)#+(ab*F .F*#+(ab*F .a#+(ab*F .b#+(ab*5FF*.#+(ab*J、*4T TF.F F.*#+(ab #+(ab*6F a. #+(ab*F(.E)#+(ab*)E .E+T#+(ab*)E .T#+(ab*)T .TF#+(ab*)T .T#+(ab*)eE(2)Ch05-4-(2)不是 SLR(1)文法 Follow(A)=a,c0 Z .S

24、S .Aa S .bAc S .dc S .bda A .da S Aa.-AS A.a4cS dc.6Sd.c Ad.ZS.如 S b.Ac Sb.da A .dS bAc.S bA.c9-dSbd.a A d.p0S bda.E T.#+(ab*)T T.F#+(ab*)T T.#+(ab*)F .(E)#+(ab*)F .F*#+(ab*)F .a#+(ab*)F .b#+(ab*)F b. #+(ab*jTCh05-4-(2) 是 LALR(1)文法ZT .S(1)St .AaSt .bAcSt .dCSt .bda(5)At .d(6)actiongotoabcd#AsS0s6s24

25、1S1AccS2R6s3S3R4S4s5S5R2S6s79S7s8R6S8R5S9s10S10R35.設(shè)有下列文法:L MLb | aM說明上述文法是否為L(zhǎng)R(1)文法，若不是，請(qǐng)說明理由。答：Ch05-5 是 LR(1)文法0Z T丄 L T .MLb L t .a M t .#a*4L1Z T L.#5L t a.ba2L t M.Lb#L t .MLbbL t .abM t .a-MJ3L t ML.b#7L t MLb.#10L t a.b4L t M.LbbL t .MLbbL t .abM t .aM8L t ML.bb9L t MLb.b1. 試寫出下列類型的內(nèi)部表示：a. in

26、tegerb. ARRAY1.5 of RECORDi:integer; b:boolean ENDc. ARRAY1.5 of RECORDa:ARRAY1.10; r: RECORDi,j:integer END ENDd. RECORDr: RECORDx,y:real END;a: ARRAY1.10 of integer END2. 設(shè)當(dāng)前層數(shù)為I，可用區(qū)距為101，且有下列程序段：CONST mm=333； nn=444 ；TYPE atype =ARRAY1.10 OF reaI;rtype = RECORDi,j:integer END; VAR a,b:atype;x,y:r

27、eaI 試寫出各標(biāo)識(shí)符的內(nèi)部表示。3. 設(shè)當(dāng)前層數(shù)和區(qū)距分別為 I 和 off ，且有函數(shù)說明首部：FUNCTION f（A： atype ； VAR B： atype ； VAR X： reaI ）： integer 其中 atype 的定義見題 5，試寫出 f 的內(nèi)部表示。4. 要求在下面括號(hào)中寫上相應(yīng) ?（層數(shù)）和區(qū)距（ off ）。（）（） PROCEDURE （g A： atype ；（）（）VAR B： atype ；（）（） VAR X： reaI （）（）（）（） .5. 給出下面C程序掃描到語(yǔ)句 c=a+b+x時(shí)相應(yīng)的全局符號(hào)表（采用順序表結(jié)構(gòu)）。main（）int a=0;

28、fIoat c=1.0;fIoat a=3.0;fIoat x=1.3;fIoat b=0.3;int b=10; c=a+b+x;6給出題1中程序掃描到語(yǔ)句 c=a+b+x時(shí)相應(yīng)的全局符號(hào)表（采用外拉鏈的散列表結(jié)構(gòu) ）。 7. 根據(jù)標(biāo)識(shí)符的作用域規(guī)則，分別給出圖 6.5 的程序中，過程 P、Q、R、S 中有效的標(biāo)識(shí) 符。第七章1. 將算術(shù)表達(dá)式 (a+b)*(c+d)-(a+b+c)翻譯成四兀式序列。2. 將下列語(yǔ)句翻譯成四元式序列：a. IF x>0 THEN x:=0 ELSE x:=1b. WHILE x>0 DO x:=x-1c. IF x>0 THEN x:=x+

29、1 ELSEIF x <0 THEN x:=x+1 ELSE x:=x+1d. WHILE x > 0 DOWHILE y > 0 DOBEGIN y:=y-x; x:=x-1 END3. 給出如下程序段的四元式序列。(四元式的操作符可用自身代替)。其中A: Array of 1.10of integer。a:=1;while a<=10 dobegi n if a<>b the nAa:=Ab+2;else a:=a+1;b:=b+1;end4. 試將FOR語(yǔ)句翻譯成四元式序列。5. 試將UNTIL語(yǔ)句翻譯成四元式序列。6. 試將CASE語(yǔ)句翻譯成四元式序

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

31、*(a+10);k:=2*(i+j);c:=a*b;3假設(shè)有如下語(yǔ)句序列或表達(dá)式，寫出公共表達(dá)式優(yōu)化前和優(yōu)化后的四元式中間代碼。(1) x:=x*y+z; y:=x*y+z; z:=x*y+z;(2) (a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c)4. 寫出如下循環(huán)語(yǔ)句不變式外提后的四元式中間代碼。while i<=100 dobegin u:=A*B;m:=u*u;S:=S+m*m;i:=i+1;end1.10。5. 寫出下面循環(huán)語(yǔ)句不變式外提后的四元式中間代碼，其中數(shù)組各下標(biāo)的類型為while i<=100 dobegi nj:=1;while j<=

32、100 doendbegin k:=1;while k<=100 do Aijk:=0; end第九章1過程活動(dòng)記錄包含哪些信息？各信息的作用？何時(shí)填寫它們？2下面是一個(gè)調(diào)用遞歸函數(shù)的Pascal程序program PP(i nput,output)VAR k:i nteger;FUNCTION F( n:in teger):i ntegerbeginif n<=0 the n F:=1else F:=n*F( n-1);en d;begink:=F(10);en d.當(dāng)?shù)诙?遞歸地)進(jìn)入 F后，DISPLA丫的內(nèi)容是什么？當(dāng)時(shí)整個(gè)運(yùn)行棧的內(nèi)容是什么？3對(duì)于下面的程序：procedure P(X,Y,Z);