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

1、習(xí)題第2章2-2試分別構(gòu)造產(chǎn)生下列語(yǔ)言的文法(2)anbmcp n,m,p0解一: S ABC A aA B bB C cC 解二: S aS X X bX Y Y cY (3)an#bn n0 cn#dn n0 錯(cuò)解: S aSb cSd #解: S X Y X aXb # Y cYd #(6)偶數(shù)個(gè)0和偶數(shù)個(gè)1組成的符號(hào)串的集合解: S 1A 0B A 1S 0C B 0S 1C C 0A 1B(考察0開頭的0011,0101,0110)2-3試描述由下列文法所產(chǎn)生的語(yǔ)言的特點(diǎn)(1)(10) n a b m a 0 n n,m0(4)S =* baSndc(n0)(5)a2n-1 n1 2

2、-6句子L: L: begin d; d; s; s; end的語(yǔ)法樹:L:L;begindd;Sendd2-11(1) S AB S c A bA A a B aSb B c bbaacb解:最右推導(dǎo)(下劃線為各步直接推導(dǎo)所得句型的句柄) S=AB=AaSb =Aacb=bAacb =bbAacb=bbaacba1S2A3Bb2A2b1A1a2S1 b3ca1是句子bbaacb相對(duì)于非終結(jié)符A1的直接短語(yǔ)b1a1A2的短語(yǔ)b2b1a1A3的短語(yǔ)cS1的直接短語(yǔ)a2cb3B的短語(yǔ)b2b1a1a2cb3.S2的短語(yǔ)其中,a1是句子bbaacb的句柄2-11(2) S (AS) S (b) A (

3、SaA) A (a) (b)a(a)(b)解:最右推導(dǎo)(下劃線為各步直接推導(dǎo)所得句型的句柄) S= (AS) = (A (b) ) = ( (SaA) (b) ) = ( (Sa (a) ) (b) ) = ( ( (b) a (a) ) (b) )(b1)是句子(b)a(a)(b)相對(duì)于S1的直接短語(yǔ)(a1)A1的直接短語(yǔ)(b1)a2(a1).A2的短語(yǔ)(b2)S2的直接短語(yǔ)(b1)a2(a1)(b2) .S3的短語(yǔ)其中, (b1)是句子(b)a(a)(b)的句柄)S3A2S2S1a2b1a1A1)b2()()()2-13化簡(jiǎn)文法(1)解:執(zhí)行算法2.1因?yàn)镃 c,所以Vn1=C又有A cC

4、C,所以Vn1=C,A同理S bCACd,所以Vn1=C,A,S至此Vn1不再增大,于是得到文法G1為 G1=(S,A,C, b,c,d, P1, S)其中P1由如下產(chǎn)生式組成S bCACd, A cSA cCC, C cS c再執(zhí)行算法2.2Vn2=S 因?yàn)镾 bCACd, A cSA cCC, C cS c所以Vn2=S,A,C Vt2= b,c,d至此Vn2,Vt2不再增大,于是得到化簡(jiǎn)后的文法G2為 G2=(S,A,C, b,c,d, P2, S)其中P2由如下產(chǎn)生式組成S bCACd, A cSA cCC, C cS c2-13化簡(jiǎn)文法(3)解:執(zhí)行算法2.1因?yàn)镾 ac, C d,

5、所以Vn1=S,C至此Vn1不再增大,于是得到文法G1為 G1=(S,C, a,b,c,d, P1, S)其中P1由如下產(chǎn)生式組成S ac, C bc d再執(zhí)行算法2.2Vn2=S 因?yàn)镾 ac所以Vn2=S Vt2= a,c至此Vn2,Vt2不再增大,于是得到化簡(jiǎn)后的文法G2為 G2=(S, a,c, P2, S)其中P2由如下產(chǎn)生式組成S ac2-14消去-產(chǎn)生式(2)解:執(zhí)行算法2.3可得W=A可判定不屬于L(G)執(zhí)行算法2.4改寫產(chǎn)生式集為S aAA aA aA bAc bc dAe de2-15消去無用產(chǎn)生式和單產(chǎn)生式(2)解:沒有無用產(chǎn)生式執(zhí)行算法2.6可得W(S)=S,A,B W

6、(A)=A,B W(B)=BP=S SA, S SB, S (S), S ( ), S S, S A (S), A ( ), A S, A B S, B (3)解:沒有無用產(chǎn)生式執(zhí)行算法2.6可得W(E)=E,T,F,P W(T)=T,F,P W(F)=F,P W(P)=PP=E E+T T*F PF (E) i T T*F PF (E) i F PF (E) i P (E) i第3章3-9對(duì)應(yīng)狀態(tài)矩陣畫出狀態(tài)圖,寫出相應(yīng)3型文法,描述輸入串特征()解:S bS aA A aA bB B aB bB b*aa*b(a b)*()解: S aA bB A bA aC B aB bC C aC b

7、C ab* (ab*a ba*b)(a b)*SABbabaa, bSBACaaaa, bbbb3-12將圖示NFA確定化和最小化(1)解:f (S, a)=S,A f (S,A, a)=S,A f (S,A, b)=A,B f (A,B, a)=B f (A,B, b)=A,B f (B, a)=B令q0=S,q1=S,A,q2*=A,B,q3*=B確定化: :q0,q1 q2,q3q0,q1a=q1 q1b=q2 :q0 q1 q2,q3q2,q3a=q3 q2,q3b=q2 :q0 q1 q2,q3SABaabbaq0q1q2aaba, bq0q1q2q3aaaabb3-12將圖示NFA

8、確定化和最小化(4)解:f (A, a)=B,C f (A, b)=B f (B, a)=A f (B,C, a)=A f (B,C, b)=C f (C, a)=A f (C, b)=C令q0=A,q1=B,q2*=B,C,q3*=C確定化: :q0,q1 q2,q3q0a=q2 q1a=q0 :q0 q1 q2,q3q2,q3a=q0 q2,q3b=q3 :q0 q1 q2,q3q0q1q2q3aaaabbABCaba ,baabq0q1q3abbaa3-13具有動(dòng)作的NFA確定化(2)解:q0=-Closure (S)=Sf (q0, a)=-Closure (f (S, a) =-Cl

9、osure (Z) =Z=q1*f (q0, b)=R,U=q2f (q2, a)=S,X=q3f (q2, b)=Z=q1f (q3, a)=Z=q1f (q3, b)=R,U,Y=q4f (q4, a)=S,X,U=q5f (q4, b)=Z=q1f (q5, a)=S,Z=q6*f (q5, b)=R,U,Y,Z=q7*f (q6, a)=Z=q1f (q6, b)=R,U=q2f (q7, a)=S,X,U=q5f (q7, b)=Z=q1確定化: SZq0q2q7abaRXYUaaaabbbbq3q4q5q6q1aabbbbbbaaa3-14最小化FA(2)解: :S0,S1,S2,

10、S3 S4,S5,S6S0,S1a=S5,S6 S2,S3a=S0,S3 :S0,S1 S2,S3 S4,S5,S6S0,S1b=S2S0,S1不可劃分S2a=S0 S3a=S3 :S0,S1 S2 S3 S4,S5,S6S4a=S6 S5,S6a=S3 :S0,S1 S2 S3 S4 S5,S6S5,S6b=S0,S1S5,S6不可劃分:S0,S1 S2 S3 S4 S5,S6aS0S5S2S0S3S3S4*S5S5*S33-22構(gòu)造識(shí)別正規(guī)語(yǔ)言的DFA(1)(0* 1)(1*0)*解:q0*=-Closure (S15) =S15,S14,S7,S3,S4,S0,S2,S6,S8,S9,S

11、11,S12f (q0, 0)=S1,S0,S2,S6,S8,S9,S11,S12,S13,S14,S7,S3,S4=q1*f (q0, 1)=S5,S6,S8,S9,S10,S11,S12=q2f (q1, 0)=q1f (q1, 1)=q2f (q2, 0)=S13,S14,S7,S4,S3,S0,S2,S6,S8,S9,S11,S12=q3*f (q2, 1)=S10,S9,S11,S12=q4f (q3, 0)=q1f (q3, 1)=q2f (q4, 0)=q3f (q4, 1)=q4S15S7S14aa0S3S0S1S2S4S5S6S8S9S10S11S12S13101q0q1q3

12、q2q40000011111%#include #include char buf100;char *p,*q;%a-zA-Z+ p=yytext; q=buf; while (*p) *q=toupper(*p); p+; q+; *q=0; strcpy(yytext, buf); ECHO; 040tn+ fprintf(yyout, );. ECHO;3-29%main( int argc, char* argv ) if ( argc 1 ) yyin = fopen( argv1, r );/yyin存放LEXYY的輸入源程序 else yyin = stdin; if ( arg

13、c 2 ) yyout = fopen( argv2, w );/yyout存放LEXYY的輸出程序 else yyout = stdout; yylex(); int yywrap() return 1;4-1消除文法的左遞歸(1)解一:消除文法的單產(chǎn)生式得S SA SB (S) ( ) S A SB (S) ( ) S B S S為直接左遞歸的非終結(jié)符,消除左遞歸得S (S)S ( )S SS SS AS BS A SB (S) ( ) S B S 解二:S,A都是左遞歸的非終結(jié)符(S A B) = (S A B) A B + ( (S)+( ) S+ ) 設(shè) A B * = Z = z1

14、1 z12 z13 z21 z22 z23 z31 z32 z33 則有 (S A B) = ( (S)+( ) S+ ) z11 z12 z13 z21 z22 z23 z31 z32 z33 z11 z12 z13 = + A B z11 z12 z13 z21 z22 z23 z21 z22 z23 z31 z32 z33 z31 z32 z334-4求出文法的FIRST集和FOLLOW集解:FIRST(S) = a, b, FOLLOW(S) = # FIRST(A) = a, FOLLOW(A) = FIRST(B)/ FOLLOW(S) b = b, # FIRST(B) = b,

15、 FOLLOW(B) = FOLLOW(S) = #4-7驗(yàn)證文法是否為L(zhǎng)L(1)文法(1)解:FIRST(D f D) FIRST(D f) = f 不是LL(1)文法4-8構(gòu)造與G等價(jià)的LL(1)文法G,并構(gòu)造相應(yīng)的LL(1)分析表解一:S,A為直接左遞歸的非終結(jié)符,消除左遞歸得GS AbS bSS bS A aAA aA LL(1)分析表:產(chǎn)生式FIRST集FOLLOW集S AbSa#S bSbS bS b#S A aAabA aA abA ab#SAbSbSSbSAaAAaA解二:消除左遞歸得G(S A) = (S A) b + (b a) b a 設(shè) b * = Z = z11 z1

16、2 b a z21 z22 則有 (S A) = (b a) z11 z12 z21 z22z11 z12 = + b z11 z12z21 z22 b a z21 z22 于是得到新的等價(jià)文法 Sbz11|az21 Abz12|az22 z11bz11| z12bz12 z21bz11|az21 z22bz12|az22| 刪除無用產(chǎn)生式得G S bz11|az21 z11bz11|z21bz11|az21 LL(1)分析表:產(chǎn)生式FIRST集FOLLOW集S bz11b#S az21az11bz11b#z11z21bz11b#z21az21aab#Saz21bz11z11bz11z21az

17、21bz114-16改造G為簡(jiǎn)單優(yōu)先文法G,并求出全部簡(jiǎn)單優(yōu)先關(guān)系(1)解:消去,采用分層法改寫得G VAR W : ;W , i i r n b c簡(jiǎn)單優(yōu)先矩陣:WVAR:;,ir/ n/ b/ cW=VAR=:=r/ n/ b/ c4-31構(gòu)造算符優(yōu)先矩陣,并用Floyd方式線性化解:求各非終結(jié)符號(hào)FIRSTVT集和LASTVT集FIRSTVT(P) = (, i LASTVT(P) = ), iFIRSTVT(F) = , (, i LASTVT(F) = , ), iFIRSTVT(T) = *, , (, i LASTVT(T) = *, , ), iFIRSTVT(E) = +,

18、*, , (, i LASTVT(E) = +, *, , ), i算符優(yōu)先矩陣: 線性化:+*()i#+*(=i# +*()i#0 f g111111111111111 f g224345156165112 f g325456167176113同前4-35構(gòu)造識(shí)別活前綴的DFA4-36判別是否LR(0)文法,構(gòu)造LR(0)分析表(4) 1.S A 2. A Ab 3. A a解:引入S S作為0號(hào)產(chǎn)生式,識(shí)別活前綴的DFA如下I2中有移進(jìn)-歸約沖突,不是LR(0)文法FOLLOW(S)=#b=,可用SLR(1)規(guī)則解決沖突相應(yīng)的LR(0)和SLR(1)分析表如下:狀態(tài)ACTIONGOTOab

19、#SA0s3121acc2r1s4/r1r13r3r3r34r2r2r2I0: S.SS .AA .AbA .aI1: SS.I2: S A.A A.bI3: A a.I4: A Ab.abSA狀態(tài)ACTIONGOTOab#SA0s3121acc2s4r13r3r34r2r24-38判別是否SLR(1)文法,構(gòu)造SLR(1)分析表解:(6)等價(jià)形式: 1. q1 begin q2 q3 end 2. q2 q2 d ; 3. q2 4. q3q3 ; q4 5. q3 q4 6. q4 S 7. q4 引入q1 q1作為0號(hào)產(chǎn)生式,識(shí)別活前綴的DFA如下I0: q1.q1q1 .begin q2 q3 endbeginI1: q1q1.I2:q1 begin .q2 q3 endq2 .q2 d ;q2 .I3:q1 begin q2 .q3 endq2 q2 .d ;q3 .q3 ; q4q3 .q4q4 .Sq4 .I10:q2 q2 d .;I11:q2 q2 d ;.I4:q1 begin q2 q3 .endq3 q3 .; q4I5:q3 q4.I6:q4 S.I7:q1 begin q2 q