1、編譯原理習(xí)題答案習(xí)題11.1翻譯程序：把用某種程序設(shè)計(jì)語(yǔ)言（源語(yǔ)言）編寫的程序（源程序）翻譯成與 之等價(jià)的另一種語(yǔ)言（目標(biāo)語(yǔ)言）的程序（目標(biāo)程序）。編譯程序：一種翻譯程序，將高級(jí)語(yǔ)言編寫的源程序翻譯成等價(jià)的機(jī)器語(yǔ)言或 匯編語(yǔ)言的目標(biāo)程序。1.2詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成1.3詞法分析：根據(jù)語(yǔ)言的詞法規(guī)則對(duì)構(gòu)成源程序的符號(hào)進(jìn)行掃描和分解，識(shí)別出 一個(gè)個(gè)的單詞。語(yǔ)法分析：根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類語(yǔ)法單位。語(yǔ)義分析及中間代碼生成：對(duì)語(yǔ)法分析識(shí)別出的語(yǔ)法單位分析其含義，并進(jìn)行初步翻譯。代碼優(yōu)化：對(duì)中間代碼進(jìn)行加工變換，以產(chǎn)生更高效的目標(biāo)代碼。目

2、標(biāo)代碼生成：將中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼、可重定位的指令代碼或會(huì)變指令代碼。以上5個(gè)階段依次執(zhí)行。習(xí)題22.1（ 1）有窮非空的符號(hào)集合（2 ）利用產(chǎn)生是規(guī)則 A-v將A替換為v時(shí)與A的上下文無(wú)關(guān)。（3 ）略（4）推導(dǎo)是把句型中的非終結(jié)符用一個(gè)產(chǎn)生是規(guī)則的右部開(kāi)替代的過(guò)程；直接推導(dǎo)是將非終結(jié)符的替代結(jié)果只用了一次產(chǎn)生式規(guī)則(5 )略(6) 一個(gè)句型的最左直接短語(yǔ)(7 )如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)或有兩個(gè)不同的最左(右)推導(dǎo)，則稱這個(gè)文法是二義的。22( 1)VN = Z,A,B VT =a,b,c,d,e(2) abbcde,abbbcde 是，acde 不是。2

3、.3 (1) LG=d 汕bln,m 列(2)2.4 (1) _A=B=c=fAg=fBg=fCg=feg(2) A=AaB=AaC=Aae=Bae=BcCae=Bceae=Cceae=eceae(3) A=B=BcC=BcfAg=BcfAaBg=BcfAaCg=BcfAaeg=BcfBaeg=BcfCaeg=Bcfeaeg=Ccfeaeg=ecfeaeg(3) 中題目有錯(cuò) 應(yīng)為C fCg|e2.5 LG= a?b?c?|aab,n 22.6 (1) ZAB A Aa| B Bb| (2) ZaZb|ab(3) ZaAb A aAb|b(4) ZAB A aAb|ab B cB| (5) Za

4、aAb|abZ aaBb|bb A aaAb|ab 4 aaBb|bb2.7 一位數(shù)：Z2|4|6|8兩位數(shù)：ZAB A 1|2|3|4|5|6|7|8|9 B 0|2|4|6|8ZACBA 1|2|3|4|5|6|7|8|9B 0|2|4|6|8C CDD 0|1|2|3|4|5|6|7|8|92.8 證明：E=E+T=E+T*F2.9語(yǔ)法樹(shù)：EE * FTf F2.10 (1)語(yǔ)法樹(shù)短語(yǔ)：E*T , (E*T) , F fE*T) , F ,E* F fE*T)直接短語(yǔ)：E*T , F句柄：F(2)直接短語(yǔ)：a , Z句柄：Z2.11 最左推導(dǎo)：Z=ZaB=BaB=B+AaB=A+AaB=

5、(+)Z*aB=(+)ZaB*aB=(+)+aB*aB=(+)+aA*aB= (+)+a(*aB= (+)+a(*aA=(+)+a(*a(直接短語(yǔ)：(，+句柄：(2.12(1) S=iSeS=iiSeS=iileS=iilelS=iS=iiSeS=iileS=iilel S=SaS=cSaS=cfaS=cfafS=cS=cSaS=cfaS=cfaf(3) E=EOE=EOEOE=iOEOE=i+EOE=i+iOE=i+i-E=i+i-iE=EOE=iOE=i+E=i+EOE=i+iOE=i+i-E=i+i-i2.13 Z t aABZ|cCACdA t bAB|aZA|cCCB t bAB|C

6、zbC t cZ|c習(xí)題33.1(1)確定的有限自動(dòng)機(jī)(2) 不確定的有限自動(dòng)機(jī)(3) 正規(guī)集是一類特殊的單詞集合，正規(guī)式是正規(guī)集的描述工具3.2 (1) (1|2|3|4|5|6|7|8|9|0)*(1|3|5|7|9)(2) 11(0|1)*00 * +3.3 證明：b (a|b) = a,b,ab,ba,aa,bb (a|b) += a,b,ab,ba,aa,bb 3.4 (1)(3)3.6(1) (01|10)*(01|10)(2) (0(1|00)*)|00Z t ABA t 0A| &B t (0|1)B| &3.7(1) Z t 1ABA t (0|1)AA t0|1B t ob

7、B t &3.8 r=a(a|b )*bb3.9 Z t 1BB t 0Z|0Z t 0Z| &3.103.11ABDbaCb習(xí)題44.1 (1)若文法GZ滿足文法不含左遞歸4.2(1) First(S)=a,dFirst(B)=a,d,c, First(A)=a,d,e,cFirst(D)=a,d, Follow(S)=#,a,b,d,eFollow(A)=bFollow(B)=a,dFollow(D)=e,a,d,b(2)不是Follow(S)=#,a,b,c,dFollow(A)= #,a,b,c,d Follow(B)= a,b,c,d 4.3 (1)證明：First(Z)=a,b,c

8、First(A)=a,b,c,dFirst(B)=a,d,c是LL(1)文法。、輸入 非終結(jié)符、abcd#ZZBAZBAZ BAAA BZA BZA BZAdBBaABbZB c略4.4 (1) Z NZ1乙E| &E ZE1E1 *E| &Ni(2) First(Z)=iFirst(Z1)=, Follow(Z)=#,*,Follow(Z 1)= #,*,First(E)=iFirst(E1 )=*, First(N)=iFollow(E)= Follow(E 1 )= Follow(N )=#,* 俞入非終結(jié)符、*i#ZZ NZi乙乙EZ1 Z1 EE ZEiEiE1 Ei *ENN i4

9、.5 (1) First(A)=a, Follow(A)= #,a 不是LL(1)文法 void A()lf(sym= getsymbol();A()；If(sym= getsymbol();Else error();4.6 ABB XB B KB XaX |bX，X aX |bX|gvoid A() if(sym= ) getsymbol(); B();void B() X(); if(sym= ) getsymbol(); B (); void B() if(sym= ) A(); getsymbol(); B (); void X()if(sym= )getsymbol(); X ();

10、else if(sym= ) getsymbol(); X ();else error();4.7(1) Z(L)|aZ|bLZL)LZL B dBB)B|&(2) First(Z)=(,a,b First(L)= (,a,b First(L )=, ? First(B )=d First(B (=b, (3) 4.8(1) ZaPZ|*aPZZaPZ|&P+aPP-P|(2) First(Z)=a,*First(Z )= *, First(P)=+Follow(Z)=,),#Follow(L)=),Follow(L )= )Follow(B )=# Follow(B =# Follow(Z)

11、= #Follow(Z )=# Follow(P)= #,*Follow(P )=#,* First(P)=+, 俞入非終結(jié)符、a*+#ZZaPZZ*aPZ ZiZ aPZZ PP+aPPPP P習(xí)題55.1分析：先求出FirstVT丄astVT集STFirstVTa b (,a b (LastVTa b ),a b )(1) 算符優(yōu)先關(guān)系表如下:(2) 因?yàn)殛P(guān)系表中無(wú)多重定義項(xiàng)，顧是算符優(yōu)先文法(3) 種優(yōu)先函數(shù)如下ab()Jf22022g444005.2(1)FirstVT丄astVT 集如下STFirstVTa c da c d ,LastVTb c db c d ,(2)算符優(yōu)先關(guān)系表

12、abcDJa1cdJ(3)是算符優(yōu)先文法(4)優(yōu)先函數(shù)abcdJf03332g40331(5)題目有誤5.3S S S SASA S.ASSS b ASAS .ASA aAAbS A.SaS .ASbaSAbSAA S.AS .ASS .ASA .SAA .SAA .SAS .bS .bS .bS .bI4: S A.SA .aA . SAA .aA .aA .aA. SAA . SAI6:S AS.I3: S b.I5: A S.AI6:A SA.I0: S .SI2:A a.A .aS .ASS .b(2) LR(O)分析表狀態(tài)ACTIONGOTOab#SA0S2S3141S2S3acc5

13、62r5r5r53r3r3r34S2S3745S2S3566S2/r4S3/r4r4747S2/r2S3/r2r256(3)不是LR(O)文法5.4(1)文法要拓廣 S SSLR(1)分析表先求 Follow(S)=#Follow(A)=a,b狀態(tài)ACTIONGOTOab#SA0S4/r6S3/r6121acc2S4/r6S3/r6563r34r5r55r26S4/r6/r4S3/r6/r456(3) 不是SLR(1)文法(4) LR(1)項(xiàng)目集族io：S J. S, #S J . AS, #SJ. b , #A J. AA , b/aA j . a, b/aA j . , b/aI4:A j

14、 a. ,b/aSI2:AS J A . S , #A J A . A, b/aS J. AS , #S J. b, #A J. AA , b/aA j . a , b/aA j . , b/aI1: S J S.,#AI2:A jAA . b/aS JA . S, #A jA . A, b/aaI3: SJ b . , #I5: S J AS . ,#S J . AS , #S J. b , #A j . AA , b/aA j. a, b/aA j .(5) LR(1)分析表狀態(tài)ACTIONGOTOab#SA0S4/r6S3/r6121acc2S4/r6S3/r6563r34r5r55r2

15、6S4/r6/r4S3/r6/r456不是LR文法5.5(1)拓廣文法 SA AaAd AaAb A 是SLR文法，其SLR表如下:狀態(tài)ACTIONGOTOabd#A0S2r4r4r411acc2S2r4r4r433S5S44r2r2r25r3r3r3#ab#分析過(guò)程:S20#nn2a丄2jhr4A-歸約S53A2jg5b3A2a0#r3nn2a丄acc成功At aAb歸約5.6LR(O)項(xiàng)目集族:從上述項(xiàng)目集族中，狀態(tài)集19是歸約-歸約沖突。因而不是LR(O)文法狀態(tài)集16時(shí)歸約-移進(jìn)沖突。但在 SLR中，F(xiàn)ollow(A)=#,b,c Follow(B)=a因而在SLR(1 )中，19與I

16、6的沖突就消失了，因而是 SLR(1)文法5.7(1)文法拓廣： S S SAaAb S BbBa A BSLR(1)項(xiàng)目集族：Follow(A)=a,b Follow(B)=a,b從項(xiàng)目集族中可發(fā)現(xiàn)，不存在沖突項(xiàng)。因而是 LR(1)文法習(xí)題66.16.2 改造文法。新文法 GS如下：S f L.RS f LL f LBL f BR f BRR f BB f 0B f 1文法GS的S屬性文法如下:規(guī)則語(yǔ)義規(guī)則Sf L.RS.val=L.val+R.valSf LS.val=L.valLf LiBL.val= Li.val*2+B.valLf BL.val=B.valRf BR1R.val=(B

17、.val+ R1 .val)*0.5RBR.val=B.val*0.5B0B.val=0B 1B.val=16.3題目有誤。加上T num規(guī)則。即文法為 GE:E TRR +TR/-TR/ T num只用綜合屬性翻譯方案如下：E TRR +TMR iR -TMR iR M print( + )N print( - )T num pri nt(nu m.lexval)6.4(1)文法改造如下：GS : S SS (L)S aL L,SL S給S與L配上繼承屬性 S.level L.level翻譯方案如下：(輸出每一個(gè)a的嵌套深度)S S.level=0 SS(L.level=S.level+1L

18、)Sapri nt(S.level)LL1.level=L.levelL1 ,S.level=L.levelSL S.level=L.level S(2)打印出每個(gè)a在句子中是第幾個(gè)字符的翻譯方案。指派屬性如下：S.pos是繼承屬性，表示S所代表的字符串的第一個(gè)字符的位置S.len是綜合屬性，表示S所代表的字符串的長(zhǎng)度L.pos與L.len含義同S翻譯方案如下：S f S.pos=1SS f (L.pos=S.pos+1L)S.le n=L.le n+2S f apri nt(S.pos)S.le n=1L f Li.pos=L.posL i,S.pos=L i+L.len+1SL.len=L

19、 i.len+1+S.lenL f S.pos=L.posSL.len=S.len6.5語(yǔ)法分析樹(shù)方法主要步驟：(1) 輸入串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹(shù)(2) 遍歷語(yǔ)法樹(shù)，確定依賴圖(3) 根據(jù)依賴圖，確定一種語(yǔ)義計(jì)算次序(4) 屬性計(jì)算習(xí)題77.1答：進(jìn)行語(yǔ)法分析時(shí)，當(dāng)發(fā)生歸約（或推導(dǎo)）時(shí)，自動(dòng)調(diào)用該規(guī)則所配置 的語(yǔ)義規(guī)則，自動(dòng)進(jìn)行語(yǔ)義的處理。語(yǔ)義處理的時(shí)機(jī)，調(diào)用何種語(yǔ)義規(guī) 貝由當(dāng)時(shí)所進(jìn)行的語(yǔ)法分析所決定。7.2分析：指派屬性E.left表示表達(dá)式E是否是左值表達(dá)式。若E.left為true， 表示是左值。否則是右值表達(dá)式。翻譯方案如下：行號(hào)產(chǎn)生式規(guī)則語(yǔ)義動(dòng)作1Ef E1+E2E.l ef

20、t=false2Ef (E1)E.left=E 1.left3Ef E1+if(E 1 .left)E.left=false; elseprint( Invalid Value in in creme nt ”)； 4E idE.l eft=true5E numE.l eft=false7.3(1) ab-c+*(2) ab+-cd+*ab+c+-7.4(1)行號(hào)1產(chǎn)生式規(guī)則語(yǔ)義動(dòng)作及含義1E巳？巳:E3E1.true=n ewlabel;E1.false=n ewlabel;E1.goto=n ewlabel;E.place=n ewTemp;E.code=E 1.code|gencode(

21、E 1.true,: |E 2.code|gencode(E.place, := ：E2.place) |gencode( oto :E1.goto)|gencode(E.false,: |E 3.code|gencode(E 1.place, := :E3.place) |gencode(E 1 .goto,): a:=x0? x+1:x+2;翻譯如下：(三地址代碼)if x0 goto L1goto L2L1: T i：=x+1a := T 1goto L3L2: T 2：=x+2a := T 2L3:7.5(1) S for(i=E 1；MiE2;Ni+)WS,M N W 行號(hào)產(chǎn)生式規(guī)則語(yǔ)義動(dòng)作與含義M.label=newlabel;Nabel=n ewlabel;Wabel=n ewlabel;S.code=E 1.code|gencode( i, := ：E1.place)|gencode(M.label,)|E 2.code|gencode( if：iE2.place, goto W.label )|gencode( goto :S.next)| Gencode(N.label, : )|gencode( + ：i,1, i)|gencode( goto:M.label)|S 1.code| Gencode( goto ：N.