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

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

2、件，效率低，執(zhí)行速度慢。第二章喬姆斯基文法體系中將文法分為哪幾類(lèi)？文法的分類(lèi)同程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)與實(shí)現(xiàn)關(guān) 系如何？答： 1) 0 型文法、 1 型文法、 2 型文法、 3 型文法。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|B設(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

3、123N ND N1 ND1 N01 D01 301N ND NDD DDD 3DD 30D 301N ND N1 ND1 N31 ND31 N431 ND431 N5431 D5431 75431N ND NDD NDDD NDDDD DDDDD 7DDDD 75DDD 754DD 7543D 75431證明文法 S iSeS|iS| i 是二義性文法。 答：對(duì)于句型 iiSeS 存在兩個(gè)不同的最左推導(dǎo)：/ 23S iSeS iiSesS iS iiSeS 所以該文法是二義性文法。給出描述下面語(yǔ)言的上下文無(wú)關(guān)文法。 =1,i=0 =i=1 =0答：1)SABAaAb| abBcB |2)SA

4、Sb|abAa |3)SaSd| A |AbAc|設(shè)計(jì)一個(gè)最簡(jiǎn)的 DFA M,使其能夠識(shí)別所有的被 3 整除的無(wú)符號(hào)十進(jìn)制整數(shù)。 答：2|5|81|4|7設(shè)計(jì)一個(gè) DFA,使其能夠接受被 4 整除的二進(jìn)制數(shù)。 答：0寫(xiě)出表達(dá)下列各項(xiàng)的正則表達(dá)式。 1)二進(jìn)制數(shù)且為 5 的倍數(shù)。2) =a,b,c,第一個(gè) a位于第一個(gè) b 之前的字符串。 3) =a,b,c,包含偶數(shù)個(gè) a 的字符串。 4) =0，1, 不包含 11 子串的字符串。 答：/ 23*01*00 y=(01 *01*1代入 B=0C+10B+11C B=(0|11C+10BB=(10 *(0|11C將 C=xB+yA代入上式 B=u

5、B+vAB=u *vA其中 u=(10*(0|11x v=(10 *(0|11y 將 B=u*vA 代入 A=0 *1u* vA+0*T/ 23A=(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 的前面 *b(a|b|c*a(b|c*a*(b|c*(a(b|c*a | b | c*(1| 第三章詞法分析器的功能是什么？ 答：讀源程序的字符序列，逐個(gè)拼出單詞，并構(gòu)造相應(yīng)的內(nèi)部表示TOKEN；同時(shí)檢查源程序中的詞法錯(cuò)誤。試分析分隔符 (1-90-9*|0(.0-90-9*

6、| (E(+|-| 0-90-9*4. 寫(xiě)出識(shí)別 C 語(yǔ)言中所有單詞的 LEX程序。答：L=A-Z | a-zD=0-9D1=1-9%(L|_(L|D|_*return (1 。 D1D*return (2 。+return (3 。第四章設(shè)有如下文法 GS:S aABbcd |A ASd |B SAh | eC |C Sf | Cg |(1) 求每個(gè)產(chǎn)生式的 Predict 集。(2) 該文法是否為 LL(1文法？為什么？ 答： (1Predict(S aABbcd=aPredict(S =#,d,f,a,h Predict(A ASd=a,d/ 23Predict(A =h,a,d,b,e

7、Predict(B SAh=a,d,hPredict(B eC=ePredict(B =bPredict(C Sf=a,fPredict(C Cg=a,f,gPredict(C =g,b(2因?yàn)?Predict(A ASd Predict(A ，所以該文法不是 LL(1文法。下列描述括號(hào)匹配的文法中，哪些是LL(1文法？(1 S (SS |S |(2 S (SS |(3 S S(SS |(4 S (S | S S (S |答： (1不是， (2是， (3不是， (4不是已知文法 GE:E E+T | TT T*F | FF i | (E 請(qǐng)按遞歸下降法構(gòu)造該文法的語(yǔ)法分析程序。答：求產(chǎn)生式的

8、predict 集合： predict(E E+T=i,(predict(E T=i,(predict(T T*F=i,(predict(T F=i,(因?yàn)槲姆ㄖ蟹墙K極符號(hào) E和 T 對(duì)應(yīng)的產(chǎn)生式的 predict 集合的交集都不為空，所以該文法 不滿足自頂向下分析的條件，現(xiàn)對(duì)文法進(jìn)行等價(jià)變換得到如下文法：ETEE+TE |TFTT*FT |FiF(E求新文法的predict 集合Predict(E TE =(,iPredict(E +TE =+Predict(E =#,Predict(T FT =i,(Predict(T *FT =*/ 23Predict(T =+,#Predict(F i

9、=iPredict(F (E=(因?yàn)橐陨衔姆ㄖ腥我夥墙K極符號(hào)對(duì)應(yīng)的產(chǎn)生式的 predict 集合的交集都為空，所以滿足自 頂向下分析的條件，所以可以寫(xiě)出如下的遞歸下降語(yǔ)法分析偽代碼：Void E( if(token (,i T( 。 E (。 else Error( 。 void E ( if(token + Match( 。+T(。E (。else if(token #, 。 else Error( 。 void T( if(token i,( F( 。 T (。 else Error( 。 void T ( if(token * Match( 。*F(。T (。else if(token

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

11、dict(F=#對(duì)任意非終極符號(hào)對(duì)應(yīng)的產(chǎn)生式的 predict 集合的交集都為空，所以該文法是LL(1文/ 23法。已知文法 GA為： A aABe | aB Bb | d(1) 試給出與 GA等價(jià)的 LL(1文法 G A。(2) 構(gòu)造 G A的 LL(1分析表并給出輸入串 aade#的分析過(guò)程。 答： (1所求 GA為 ：AaA(1A ABe(2A(3BdB(4B bB(5B(6Predict(A aA =aPredict(AABe=aPredict(A=#,dPredict(BdB =dPredict(BbB =bPredict(B=e對(duì)任意非終極符號(hào)對(duì)應(yīng)的產(chǎn)生式的 predict 集合的

12、交集都為空，所以該文法是LL(1文法。(3) 分析表如下：abde#A(1A(2(3(3B(4B(5(6aade#的分析過(guò)程如下分析棧輸入流動(dòng)作A#aade#替換 (1aA #aade#匹配A #ade#替換 (2ABe#ade#替換 (1aA Be#ade#匹配ABe#de#替換 (3Be#de#替換 (4dBe#de#匹配Be#e#替換e#e#匹配#成功第五章 S aA/ 23A AbAb(2SaSSbSaSSSSc(3SASSbASAAa(4ScASccBBccBBbAcAAa構(gòu)造上述文法的LR(0歸約活前綴狀態(tài)機(jī)，并給出LR(0分析表。答：(1Ch05-1-(1) 有移入、規(guī)約沖突(2

13、Ch05-1-(2)/ 23Z .S (1)S .aSSb (2)S .aSSS (3)S .c (4)actiongotoabc#SS0s2s51S1AccS2s2s53S3s2s54S4s2s6s57S5R4R4R4R4S6R2R2R2R2S7R3R3R3R3(3Ch05-1-(3) 有移入、規(guī)約沖突(49 / 23ZS (1) S cA (2) SccB (3) B ccB (4)Bb (5) AcA (6)Aa (7)actiongotoabc#ABSS0s12S1s3s54S2AccS3R7R7R7R7S4R6R6R6R6S5s3s9s876S6R3R3R3R3S7R2R2R2R2S

14、8s3s107S9R5R5R5R5S10s3s9s8711S11R4R4R4R4(4SaSb | bSa | ab(5SSab | bRRS | a(6SSAB | BABbAaA | B(7SAaAb | BbBa2. 設(shè)有下列文法：(1 S SaS | b(2 S bSb | cSc | b | c (3 S bSb | bSc | dB10 / 23A(8 A aABe | BaB dB |說(shuō)明上述文法是否為 SLR(1文法。若是，請(qǐng)構(gòu)造 SLR(1分析表；若不是，請(qǐng)說(shuō)明理由。 答：(1Ch05-2-(1) 不是 SLR( 1)Follow(S)=#,a(2Ch05-2-(2)不是 SL

15、R(1)Follow(S)=#,b,c0Z.SbS.bSbS.cScS.bS.cSb.SbSb.S.bSbS.cScS.bS.c(3Ch05-2-(3)是 SLR (1)11 / 23Z .S (1)S.bSb (2)S.bSc (3)S .d (4)(4(5(6actiongotobcd#SS0s2s31S1AccS2s2s3Ch05-2-7 4S3R4R4R4S4s5s6S5R2R2R2S6R3R3R3Ch05-2-(4) 不是 SLR ( 1)Follow(S)=#,a,bCh05-2-(5) 不是 SLR(1)Follow(R)=#,a12 / 23Ch05-2-(6) 是 SLR(

16、1)Z S (1)SSAB (2)S BA (3)A aA (4)A B (5)B b (6)actiongotoab#ABSS0s231S1s6s2Acc85S2R6R6R6Ch05-2-7S3s6s245S4R3R3R3S5R5R5R5S6s6s275S7R4R4R4S8s29S9R2R2R2(7Ch05-2-(7) 不是 SLR( 1)Follow(A)=a,b Follow(B)=a,b(80 Z.S S.AaAb S.BbBa A.B.42S Aa.Ab68AS A.aAbaA.AS AaA.bbS AaAb.1 S ZS.B3S B.bBaS Bb.Ba B.79BS BbB.aa

17、S BbBa.13 / 23Ch05-2-(8)不是SLR (1) Follow(B)=a,e設(shè)有下列文法：S aAd | bBd | aBe | bAe Ag Bg說(shuō)明該文法是 LR(1文法，但不是 LALR(1文法。 答：Ch05-3 是 LR(1)文法0 Z.S S.aAd S.bBd S.aBe S.bAe#2Sa.Ad#Sa.Be#A.gdaB.ge4 S aA.d#7S aAd.#AZS.9123eASbA.e#SbAe.#Sb.Bd#Sb.Ae#1013A.geBSbB.d#dSbBd.#B.gd11gA g.eBg.db14 / 23Ch05-3 不是 LALR(1) 文法設(shè)有

18、下列文法：(1 E E+T | TT TF | TF (E | F* | a | b(2 S Aa | bAc | dc | bdaAd說(shuō)明上述文法是否為SLR(1文法？是否為L(zhǎng)ALR(1文法？并構(gòu)造相應(yīng)的分析表。答： (1Ch05-4-(1) 不是 SLR(1)文法Follow(T)=#,(,a,b,+,)Z.0E E.E+T E.T T.TF T.T1EE2+.TZE.+T.TFEE.+TT.T+109F(E).)F(E.)EE.+TEE3 EE+T. TT.F TT. F.(E) F.F* F.a F.bTTF.FF.*6 Fa.7 Fb.115FF*.(8 F(.E) E.E+T E.

19、T T.TF T.TET.TT.F TT.F.(E)F.F*F.aF.bF4a6b715 / 23Ch05-4-(1) 不是 LALR(1) 文法1ZE.EE.+T# #+E0Z .E E.E+T E.T T.TF T.T# #+ #+ #+(ab #+(ab+(22EE+.T#+(ab*)T.TF#+(abT.T#+(ab+9F(E.)EE.+T#+(ab*)#+(ab*)(10F(E).#+(ab*)3E E+T. TT.F TT. F.(E) F.F* F.a F.b#+ #+(ab #+(ab #+(ab* #+(ab* #+(ab* #+(ab*Fa bF b. #+(ab*5FF*

20、.#+(ab*4TTF.FF.*#+(ab#+(ab*F a. #+(ab*8(11F(.E)E .E+T#+(ab*)#+(ab*)ET.TT.F#+(ab*)#+(ab*)EE.T#+(ab*)TT.#+(ab*)T.TF#+(ab*)F.(E)#+(ab*)T.T#+(ab*)TF.F*#+(ab*)F .a#+(ab*)F.b#+(ab*)Ch05-4-(2) 不是 SLR(1)文法 Follow(A)=a,c0 Z .S S.Aa S.bAc S.dc S.bda A.dS1 ZS.Z S.#S0Z .S#S.Aa#S.bAc#S.dc#S.bda#A.dad2Sd.c#Ad.aCh

21、05-4-(2) 是 LALR(1) 文法1c3 S dc.#5SAa.#a46S b.Ac#S b.da#A.dcd7Sbd.a#Ad.ca8S bda.#A S A.abA#9S bA.c#c10S bAc.#16 / 23actiongotoabcd#ASS0s6s241S1AccS2R6s3S3R4S4s5S5R2S6s79S7s8R6S8R5S9s10S10R3Z .S (1)S .Aa (2)S .bAc (3)S .dc (4)S .bda (5) A .d (6)設(shè)有下列文法：L MLb | aM說(shuō)明上述文法是否為 LR(1文法，若不是，請(qǐng)說(shuō)明理由。 答：Ch05-5 是LR(

22、1) 文法5L a.baL .a M.# aL1ZL.#Z.LL .MLb2L M.Lb#L .MLbbL .abM.aM10L a.b3L ML.b#L4L M.LbbL .MLbbL .abM.aMM7LMLb.#8b9LML.bbLMLb.b試寫(xiě)出下列類(lèi)型的內(nèi)部表示：integerb.ARRAY 1.5 of RECORD i:integer 。 b:boolean ENDc.ARRAY 1.5 of RECORD a:ARRAY 1.10 。 r:RECORD i,j:integer END END d. RECORD r: RECORD x,y:real END。a: ARRAY 1

23、.10 of integer END設(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試寫(xiě)出各標(biāo)識(shí)符的內(nèi)部表示。/ 23設(shè)當(dāng)前層數(shù)和區(qū)距分別為 l 和 off ，且有函數(shù)說(shuō)明首部：FUNCTION fA： atype ； VAR B： atype ； VAR X： real )： integer 其中 atype 的定義見(jiàn)題 5，試寫(xiě)出 f 的內(nèi)部表示。要求在下面括號(hào)中寫(xiě)上相

24、應(yīng) ?層數(shù))和區(qū)距 off )。 )PROCEDURE g：A atype ；)VAR B： atype ；)VAR X：real ) )。main。根據(jù)標(biāo)識(shí)符的作用域規(guī)則，分別給出圖 6.5 的程序中，過(guò)程 P、Q、R、 S中有效的標(biāo)識(shí) 符。第七章將算術(shù)表達(dá)式 (a+b*(c+d-(a+b+c 翻譯成四元式序列。將下列語(yǔ)句翻譯成四元式序列：a. IF x0 THEN x:=0 ELSE x:=1WHILE x0 DO x:=x-1IF x0 THEN x:=x+1 ELSEIF x 0 DOWHILE y 0 DOBEGIN y:=y-x。 x:=x-1 END給出如下程序段的四元式序列。

25、(四元式的操作符可用自身代替。其中 A： Array of1.10 of integer 。a:=1。/ 23 while a=10 dobegin if ab then Aa:=Ab+2 。else a:=a+1。 b:=b+1 。end試將 FOR語(yǔ)句翻譯成四元式序列。試將 UNTIL 語(yǔ)句翻譯成四元式序列。試將 CASE語(yǔ)句翻譯成四元式序列。試給出 4、5、6 題中翻譯過(guò)程的語(yǔ)法制導(dǎo)程序。第八章將下面的程序段劃分為基本塊并畫(huà)出其程序流圖。 read(A 。read(B。F:=1。C:=A*A 。D:=B*B 。if C 。 goto L3 。L1: E:=B*B 。F:=F+2。 wri

26、te(E 。 if E100 goto L2 。 goto L3 。L2:F:=F-1。goto L1 。L3: write(E 。假設(shè)有如下語(yǔ)句序列，寫(xiě)出常表達(dá)式優(yōu)化前和優(yōu)化后的四元式中間代碼。 (1i:=1 。(2a:=20。j:=i*(i+1 。b:=a*(a+10 。k:=2*(i+j 。c:=a*b 。假設(shè)有如下語(yǔ)句序列或表達(dá)式，寫(xiě)出公共表達(dá)式優(yōu)化前和優(yōu)化后的四元式中間代碼。 (1x:=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寫(xiě)出如下循環(huán)語(yǔ)句不變式外提后的四元式中間代碼。 while i=100 do/ 23 begin u:=A*B 。m:=u*u 。S:=S+m*m。 i:=i+1 。end寫(xiě)出下面循環(huán)語(yǔ)句不變式外提后的四元式中間代碼，其中數(shù)組各下標(biāo)的類(lèi)