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

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

2、其不產(chǎn)生可執(zhí)行程序文 件，效率低，執(zhí)行速度慢。13弟早1 .喬姆斯基文法體系中將文法分為哪幾類？文法的分類同程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)與實(shí)現(xiàn)關(guān) 系如何？答：1) 0型文法、1型文法、2型文法、3型文法。2)2 .寫(xiě)一個(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)。答：N ND N3 ND3 N23 D23 123N ND NDD DDD 1DD 12D 123

3、N 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是二義性文法。答：對(duì)于句型iiSeS存在兩個(gè)不同的最左推導(dǎo):S iSeS iiSesS iS iiSeS所以該文法是二義性文法。5 .給出描述下面語(yǔ)言的上下文無(wú)關(guān)文法。(1) L1=anbnci |n>=1,i>=0 (2) L2=aibjj>=i&

4、gt;=1(3) L3=anbmcmdn |m,n>=0答：(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整除的無(wú)符號(hào)十進(jìn)制整數(shù)。2|5|81|4|77.設(shè)計(jì)一個(gè)DFA使其能夠接受被4整除的二進(jìn)制數(shù)。 答：答：8.寫(xiě)出表達(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子用的字符串。(D可以先畫(huà)出相應(yīng)的有限自動(dòng)機(jī)

5、0 A添加新的開(kāi)始狀態(tài)1 /1d一。/ B0 C1DE< JJ<710S和終止?fàn)顟B(tài)T:1根據(jù)以上自動(dòng)機(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=(10) *(0|11)x v=(10)*(0

6、|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)該題目理解為：至少有一個(gè) a和一個(gè)b,且a出現(xiàn)在b的前面(可以有問(wèn) 隔)，則答案為: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*弟二早1 .詞法分析器的功能是什么？答：讀源程序的字符序列，逐個(gè)拼出單詞，并構(gòu)造相應(yīng)的內(nèi)部表示TOKEN同時(shí)檢查源程序中的詞法錯(cuò)誤。2 .試分析分隔符(空格、跳格及回車(chē)等)對(duì)詞法

7、分析的影響。答：空格、跳格、回車(chē)等分隔符號(hào)對(duì)詞法分析不起作用，可以刪除。但是回車(chē)符號(hào)可以用于錯(cuò)誤定位，所以在刪除回車(chē)符號(hào)前需要統(tǒng)計(jì)回車(chē)的個(gè)數(shù)。3 .給出識(shí)別C語(yǔ)言全部實(shí)型常數(shù)的自動(dòng)機(jī)。答：(+|-1 )(1-90-9*|0)(.0-90-9*|) (E(+|-| )0-90-9*)4 .寫(xiě)出識(shí)別C語(yǔ)言中所有單詞的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 SAh|eC|C Sf | Cg |(1)求每個(gè)產(chǎn)生式的Pre

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

9、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)請(qǐng)按遞歸下降法構(gòu)造該文法的語(yǔ)法分析程序。答：求產(chǎn)生式的predict集合：predict(E E+T)=i,(predict(E T)=i,(predict" T*F)=i,(predict(T F)=i,(由于文法中非終極符號(hào)E 和 T 對(duì)應(yīng)的產(chǎn)生式的predict 集合的交集都不為空，法不滿足自頂向下分析的條件，現(xiàn)對(duì)文法進(jìn)行等價(jià)變換得到如下

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)=(由于以上文法中任意非終極符號(hào)對(duì)應(yīng)的產(chǎn)生式的predict 集合的交集都為空，Void E() if(token (,i) T();E else Error();void E () if(token +) Match( else if(token #,)

11、 ; else Error();void T() if(token i,() F();T else Error();void T () if(token *) Match( else if(token +,),#) ; else Error();void F() if(token i) Match( else if(token () Match();+ );T();E ();();* );F();T ();i ); ( );E();Match( ) );所以該文所以滿足自頂向下分析的條件，所以可以寫(xiě)出如下的遞歸下降語(yǔ)法分析偽代碼：else Error();4 .構(gòu)造一個(gè)LL(1)文法G,它能識(shí)

12、別語(yǔ)言L:L= | 為字母表上不包括兩個(gè)相鄰的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 )=#對(duì)任意非終極符號(hào)對(duì)應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文法。5 .已知文法 GA為:A aABe|aB Bb | d(1)試給出與GA等價(jià)的LL文法G'

13、 A(2)構(gòu)造G'簡(jiǎn)LL(1汾析表并給出輸入串a(chǎn)ade#的分析過(guò)程。答：所求G A的:AaA'(1)AABe(2)A(3)BdB'(4)B'bB'(5)B'(6)Predict(A aA' )=aPredict(A ABe)=aPredict(A ' )=#,dPredict(B dB' )=dPredict(B bB' )=bPredict(B ' )=e對(duì)任意非終極符號(hào)對(duì)應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文法。(3)分析表如下:abde#A(1)A(2)(3)(3)B(4

14、)B，(5)(6)aade#的分析過(guò)程如下分析棧輸入流動(dòng)作A#aade#替換aA' #aade#匹配A #ade#替換(2)ABe#ade#替換aA' Be#ade#匹配A Be#de#替換Be#de#替換(4)dB' e#de#匹配B' e#e#替換e#e#匹配#成功第五章(這章答案是錯(cuò)的)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)機(jī)，并給出LR(0)分析表。答：(1)Ch05-1-(1

15、)有移入、規(guī)約沖突(2)Ch05-1-(2)Zf .S (1)S .aSSb (2)S .aSSS (3)S7 .c(4)actiongotoabc#SS0s2s51S1AccS2s2s53S3s2s54S4s2s6s57S5R4R4R4R4S6R2R2R2R2S7R3R3R3R314有移入、規(guī)約沖突Ch05-1-(3)24Zf S- cA (2)S- ccB (3)B- ccB (4)B- b (5) 2 cA (6) A a (7)actiongotoabc#ABSS0s12S1s3s54S21AccS3R7R7R7R7S4 R6R6R6R6S5s3s9s876S6R3R3R3R3S7 1

16、R2R2R2R2S8s3s107S9R5R5R5R5S10：s3s9s87r iiS11R4R4R4R42.設(shè)有下列文法:(1) S SaS | b(2) S bSb | cSc | b | c(3) S bSb | bSc | d(4) S aSb | bSa | ab(5) S Sab | bRR S | a(6) S SAB | BA B bA aA | B S AaAb | BbBaBA(8) A aABe | BaB dB |說(shuō)明上述文法是否為SLR(1反法。若是，請(qǐng)構(gòu)造SLR(1分析表；若不是，請(qǐng)說(shuō)明理由。答：(1)Ch05-2-(1)不是 SLR (1)(2)Ch05-2-(2)

17、不是slr(i)Follow(S)=#,b,cZf.SS7 .bSbS7.cScSf.bSf.c-brS b.Sb Sf b.Sf .bSbS7 .cScSf .bSf .cCh05-2-(3) 是 SLR (1)3_ S 一 d.1d2 Sf b.SbSf b.ScS- .bSb S 一 .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

18、 S- bSc.Ch05-2-(4)不是 SLR( 1)Follow(S)=#,a,b-b-4S- aSb.(5)Ch05-2-(5)不是slr(i)Follow(R)=#,a(6)0Zf.S S .SAB Sf .BA Bf .b|b>Ch05-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

19、(3) A- aA (4) A- B (5) B- b (6)actiongotoab#ABSS01s231S1s6s2Acc85S2R6R6R6Ch05-2-7S31s6s245S4R3R3R3S5R5R5R5S61s6s275S7R4R4R4S8s29S9R2R2R2Ch05-2- 不是 SLR ( 1)Follow(A)=a,b Follow(B)=a,b0- ZSSf .AaAb Sf .BbBa 2.1-SZ Zf s.4TBf.BTSf A.aAb-a-3Sf Aa.Ab A一.68Sf AaA.bSf AaAb.ATSf B.bBa-b->Sf Bb.Ba B 一.(8)C

20、h05-2-(8)不是 SLR (1) Follow(B尸a,e7-o9Sf BbB.aSf BbBa.BT3.設(shè)有下列文法：S aAd | bBd | aBe | bAeA gB g說(shuō)明該文法是 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#-Bt6A>g.db>g.e9SfbA.e#一At10S-bB.d #-Bf11 g A-g.B-g.

21、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) | F* | a | b(2) S Aa | bAc | dc | bda A d說(shuō)明上述文法是否為SLR(1區(qū)法？是否為L(zhǎng)ALR(1戌法？并構(gòu)造相應(yīng)的分析表。答：Ch05-4-(1)不是 SLR文法Follow(T)=#,(,a,b,+,)26Zf.e ef.e+t ef.t TfTF TfTEt1 ZfE.efe.+tEfE+.T* T f .TFT f .T"T+-T-j3E-E+

22、T.TfT.F TfT.F f(E) F f .F* Ff.a Ff.b -rr 8T-TF. F-F.*-a F-a.7Ffb.11Ch05-4-(1)10F-(E).卜)F-(E.)Le-efe.+t不是LALR(1)文法1Z fe.efe.+t#+f,e0Zf.e ef.e+t ef.t TfTF Tf.T#+#+#+(ab#+(ab(2)5- F f F*2efe+.t#+(ab*)T一>.TF#+(abT一>.T#+(ab+9F-(E.) efe.+t#+(ab*)#+(ab*),10F-(E).#+(ab*)Ef-(.e) ef.e+t ef.t TfTF TfT-TE

23、fT.TfT.F TfT. Ff(E) Ff.F* Ff.a Ff.b-F<J J -aQ| -bm3ef 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*)Tt5F-F*.#+(ab*J,*4T-TF.F -F.*#+(ab#+(ab*Ft6Fa.#+(ab*7F fb.#+(ab*11e f t.#+(ab*)TfT.F#+(ab*)T f T.#

24、+(ab*)F-.(E)#+(ab*)Ff.F*#+(ab*)Ff .a#+(ab*)Ff.b#+(ab*)Ch05-4-(2)不是 SLR(1)文法 Follow(A)=a,cCh05-4-(2) 是 LALR(1)文法SAa.r#ZSr#TSr"0 zf .sr#-Ta4-At S-A.a28Sf.AaSf.bAcSf.dcSf.bdaA f.d# # # a6S-b.AcSfb.daAf.d9SfbA.cSfd.c Afd.7 S-bd.aA fd.S- bAc. #S dc.S-bda.Z. .S(1)Sf .Aa (2)Sf .bAc (3)Sf .dc(4)Sf .bda

25、 (5)Af.d(6)actiongotoabcd#ASS0s6s241S1AccS2R6s3S3R4S4s5S5R2S6s79S7s8R6S8R5S9s10S10R35 .設(shè)有下列文法：L MLb | aM說(shuō)明上述文法是否為 LR(1)文法，若不是，請(qǐng)說(shuō)明理由。答：Ch05-5 是 LR(1)文法第六章1. 試寫(xiě)出下列類型的內(nèi)部表示：egerb.ARRAY 1.5 of RECORDi:integer; b:boolean ENDc.ARRAY 1.5 of RECORDa:ARRAY 1.10; r: RECORDi,j:integer END ENDd. RECORDr: RE

26、CORDx,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 = RECORDi,j:integer END;VAR a,b:atype;x,y:real試寫(xiě)出各標(biāo)識(shí)符的內(nèi)部表示。3. 設(shè)當(dāng)前層數(shù)和區(qū)距分別為l和off,且有函數(shù)說(shuō)明首部：FUNCTION f（ A： atype； VAR B： atype； VAR X： real） ： integer其中 atype 的定義見(jiàn)題5，試寫(xiě)出f 的

27、內(nèi)部表示。4. 要求在下面括號(hào)中寫(xiě)上相應(yīng)?（層數(shù)）和區(qū)距（off） 。（）（）PROCEDURE （g A： atype； （）（）VAR B： atype； （）（）VAR X： real （）（） （）（）.5. 給出下面C程序掃描到語(yǔ)句 c=a+b+x時(shí)相應(yīng)的全局符號(hào)表（采用順序表結(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中程序掃描到語(yǔ)句 c=a+b+x時(shí)相應(yīng)的全局符號(hào)表（采用外拉鏈的散列表結(jié)構(gòu)7. 根據(jù)標(biāo)識(shí)符的作用域規(guī)則，分別給出圖6.5 的程序

28、中，過(guò)程P、 Q、 R、 S 中有效的標(biāo)識(shí)符。36第七章1 .將算術(shù)表達(dá)式 (a+b)*(c+d)-(a+b+c)翻譯成四元式序列。2 .將下列語(yǔ)句翻譯成四元式序列：a. IF x>0 THENx:=0ELSEx:=1b. WHILE x>0 DO x:=x-1c. IFx>0 THEN x:=x+1 ELSEIFx<0 THEN x:=x+1 ELSE x:=x+1d. WHILEx>0 DOWHILEy>0DOBEGIN y:=y-x; x:=x-1 END3 .給出如下程序段的四元式序列。(四元式的操作符可用自身代替)。其中A: Array of1.1

29、0of integer。a:=1;while a<=10 dobegin ifa<>b thenAa:=Ab+2;else a:=a+1;b:=b+1; end4 .試將FOR語(yǔ)句翻譯成四元式序列。5 .試將UNTIL語(yǔ)句翻譯成四元式序列。6 .試將CASE語(yǔ)句翻譯成四元式序列。7 .試給出4、5、6題中翻譯過(guò)程的語(yǔ)法制導(dǎo)程序。第八章I .將下面的程序段劃分為基本塊并畫(huà)出其程序流圖。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;II : E:

30、=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ǔ)句序列，寫(xiě)出常表達(dá)式優(yōu)化前和優(yōu)化后的四元式中間代碼。(1) i:=1;(2) a:=20;j:=i*(i+1);b:=a*(a+10);k:=2*(i+j);c:=a*b;3 .假設(shè)有如下語(yǔ)句序列或表達(dá)式，寫(xiě)出公共表達(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 .寫(xiě)出如下循環(huán)語(yǔ)句不變式

31、外提后的四元式中間代碼。while i<=100 dobegin u:=A*B;m:=u*u;S:=S+m*m;i:=i+1;end1.10。5 .寫(xiě)出下面循環(huán)語(yǔ)句不變式外提后的四元式中間代碼，其中數(shù)組各下標(biāo)的類型為while i<=100 dobegin j:=1;while j<=100 doendbegin k:=1;while k<=100 doAijk:=0;end第九章1 .過(guò)程活動(dòng)記錄包含哪些信息？各信息的作用？何時(shí)填寫(xiě)它們？2 .下面是一個(gè)調(diào)用遞歸函數(shù)的Pascal程序program PP(input,output)VAR k:integer;FUNCTION F(n:integer):integerbeginif n<=0 then F:=1else F:=n*F(n-1);end;begink:=F(10); end.當(dāng)?shù)诙?遞歸地)進(jìn)入 F后，DISPLAY的內(nèi)容是什么？當(dāng)時(shí)整個(gè)運(yùn)行棧的內(nèi)容是什么？3 .對(duì)于下面的程序：procedure P(X,Y,Z);beginY:=