编译原理习题答案

1、习题第2章2-2试分别构造产生下列语言的文法(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 错解: S aSb cSd #解: S X Y X aXb # Y cYd #(6)偶数个0和偶数个1组成的符号串的集合解: S 1A 0B A 1S 0C B 0S 1C C 0A 1B(考察0开头的0011,0101,0110)2-3试描述由下列文法所产生的语言的特点(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的语法树:L:L;begindd;Sendd2-11(1) S AB S c A bA A a B aSb B c bbaacb解:最右推导(下划线为各步直接推导所得句型的句柄) S=AB=AaSb =Aacb=bAacb =bbAacb=bbaacba1S2A3Bb2A2b1A1a2S1 b3ca1是句子bbaacb相对于非终结符A1的直接短语b1a1A2的短语b2b1a1A3的短语cS1的直接短语a2cb3B的短语b2b1a1a2cb3.S2的短语其中,a1是句子bbaacb的句柄2-11(2) S (AS) S (b) A (

3、SaA) A (a) (b)a(a)(b)解:最右推导(下划线为各步直接推导所得句型的句柄) S= (AS) = (A (b) ) = ( (SaA) (b) ) = ( (Sa (a) ) (b) ) = ( ( (b) a (a) ) (b) )(b1)是句子(b)a(a)(b)相对于S1的直接短语(a1)A1的直接短语(b1)a2(a1).A2的短语(b2)S2的直接短语(b1)a2(a1)(b2) .S3的短语其中, (b1)是句子(b)a(a)(b)的句柄)S3A2S2S1a2b1a1A1)b2()()()2-13化简文法(1)解:执行算法2.1因为C 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由如下产生式组成S bCACd, A cSA cCC, C cS c再执行算法2.2Vn2=S 因为S bCACd, A cSA cCC, C cS c所以Vn2=S,A,C Vt2= b,c,d至此Vn2,Vt2不再增大,于是得到化简后的文法G2为 G2=(S,A,C, b,c,d, P2, S)其中P2由如下产生式组成S bCACd, A cSA cCC, C cS c2-13化简文法(3)解:执行算法2.1因为S ac, C d,

5、所以Vn1=S,C至此Vn1不再增大,于是得到文法G1为 G1=(S,C, a,b,c,d, P1, S)其中P1由如下产生式组成S ac, C bc d再执行算法2.2Vn2=S 因为S ac所以Vn2=S Vt2= a,c至此Vn2,Vt2不再增大,于是得到化简后的文法G2为 G2=(S, a,c, P2, S)其中P2由如下产生式组成S ac2-14消去-产生式(2)解:执行算法2.3可得W=A可判定不属于L(G)执行算法2.4改写产生式集为S aAA aA aA bAc bc dAe de2-15消去无用产生式和单产生式(2)解:没有无用产生式执行算法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)解:没有无用产生式执行算法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对应状态矩阵画出状态图,写出相应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具有动作的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构造识别正规语言的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)解一:消除文法的单产生式得S SA SB (S) ( ) S A SB (S) ( ) S B S S为直接左递归的非终结符,消除左递归得S (S)S ( )S SS SS AS BS A SB (S) ( ) S B S 解二:S,A都是左递归的非终结符(S A B) = (S A B) A B + ( (S)+( ) S+ ) 设 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验证文法是否为LL(1)文法(1)解:FIRST(D f D) FIRST(D f) = f 不是LL(1)文法4-8构造与G等价的LL(1)文法G,并构造相应的LL(1)分析表解一:S,A为直接左递归的非终结符,消除左递归得GS AbS bSS bS A aAA aA LL(1)分析表:产生式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 设 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 于是得到新的等价文法 Sbz11|az21 Abz12|az22 z11bz11| z12bz12 z21bz11|az21 z22bz12|az22| 删除无用产生式得G S bz11|az21 z11bz11|z21bz11|az21 LL(1)分析表:产生式FIRST集FOLLOW集S bz11b#S az21az11bz11b#z11z21bz11b#z21az21aab#Saz21bz11z11bz11z21az

17、21bz114-16改造G为简单优先文法G,并求出全部简单优先关系(1)解:消去,采用分层法改写得G VAR W : ;W , i i r n b c简单优先矩阵:WVAR:;,ir/ n/ b/ cW=VAR=:=r/ n/ b/ c4-31构造算符优先矩阵,并用Floyd方式线性化解:求各非终结符号FIRSTVT集和LASTVT集FIRSTVT(P) = (, i LASTVT(P) = ), iFIRSTVT(F) = , (, i LASTVT(F) = , ), iFIRSTVT(T) = *, , (, i LASTVT(T) = *, , ), iFIRSTVT(E) = +,

18、*, , (, i LASTVT(E) = +, *, , ), i算符优先矩阵: 线性化:+*()i#+*(=i# +*()i#0 f g111111111111111 f g224345156165112 f g325456167176113同前4-35构造识别活前缀的DFA4-36判别是否LR(0)文法,构造LR(0)分析表(4) 1.S A 2. A Ab 3. A a解:引入S S作为0号产生式,识别活前缀的DFA如下I2中有移进-归约冲突,不是LR(0)文法FOLLOW(S)=#b=,可用SLR(1)规则解决冲突相应的LR(0)和SLR(1)分析表如下:状态ACTIONGOTOab

19、#SA0s3121acc2r1s4/r1r13r3r3r34r2r2r2I0: S.SS .AA .AbA .aI1: SS.I2: S A.A A.bI3: A a.I4: A Ab.abSA状态ACTIONGOTOab#SA0s3121acc2s4r13r3r34r2r24-38判别是否SLR(1)文法,构造SLR(1)分析表解:(6)等价形式: 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号产生式,识别活前缀的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