昆明理工大学编译原理课后习题(部分重点).ppt

第2章 2-2试分别构造产生下列语言的文法,(2)anbmcpn,m,p0 解一: S ABC A aA B bB C cC 解二: S aS X X bX Y Y cY (3)an#bnn0 cn#dnn0 错解: S aSb cSd # 解: S X Y X aXb # Y cYd# (6)偶数个0和偶数个1组成的符号串的集合 解: S 1A 0B A 1S0C B 0S 1C C 0A1B (考察0开头的0011,0101,0110),2-3试描述由下列文法所产生的语言的特点,(1)(10) n a b m a 0 nn,m0 (4)S =* baSndc(n0) (5)a2n-1n1,2-6句子L: L: begin d; d; s; s; end的语法树,:,L,:,L,;,;,begin,d,d,;,S,end,d,2-11,(1) S AB S c A bA A a B aSb B c bbaacb 解:最右推导(下划线为各步直接推导所得句型的句柄) S=AB=AaSb =Aacb=bAacb =bbAacb=bbaacb,a1,a1是句子bbaacb相对于非终结符A1的直接短语 b1a1A2的短语 b2b1a1A3的短语 cS1的直接短语 a2cb3B的短语 b2b1a1a2cb3S2的短语 其中,a1是句子bbaacb的句柄,2-11,(2) S (AS) S (b) A (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)的句柄,),2-13化简文法,(1)解:执行算法2.1 因为C c,所以Vn1=C 又有A cCC,所以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.2 Vn2=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 c,2-13化简文法,(3)解:执行算法2.1 因为S ac, C d,所以Vn1=S,C 至此Vn1不再增大,于是得到文法G1为 G1=(S,C, a,b,c,d, P1, S) 其中P1由如下产生式组成 S ac, C bc d 再执行算法2.2 Vn2=S 因为S ac 所以Vn2=S Vt2= a,c 至此Vn2,Vt2不再增大,于是得到化简后的文法G2为 G2=(S, a,c, P2, S) 其中P2由如下产生式组成 S ac,2-14消去-产生式,(2)解:执行算法2.3可得W=A 可判定不属于L(G) 执行算法2.4 改写产生式集为 S aAAaAa A bAcbcdAe de,2-15消去无用产生式和单产生式,(2)解:没有无用产生式 执行算法2.6可得W(S)=S,A,B W(A)=A,B W(B)=B P=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)=P P=E E+TT*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(ab)* ()解: S aA bB A bA aC B aB bC C aC bC ab*(ab*aba*b)(ab)*,S,B,A,C,a,a,a,a, b,b,b,b,3-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,q3 q0,q1a=q1 q1b=q2 :q0 q1 q2,q3 q2,q3a=q3 q2,q3b=q2 :q0 q1 q2,q3,S,A,B,a,a,b,b,a,q0,q1,q2,a,a,b,a, b,3-12将图示NFA确定化和最小化,(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,q3 q0a=q2 q1a=q0 :q0 q1 q2,q3 q2,q3a=q0 q2,q3b=q3 :q0 q1 q2,q3,q0,q1,q2,q3,a,a,a,a,b,b,b,q0,q1,q3,a,b,b,a,a,3-13具有动作的NFA确定化,(2)解:q0=-Closure (S)=S f (q0, a)=-Closure (f (S, a) =-Closure (Z) =Z=q1* f (q0, b)=R,U=q2 f (q2, a)=S,X=q3 f (q2, b)=Z=q1 f (q3, a)=Z=q1 f (q3, b)=R,U,Y=q4 f (q4, a)=S,X,U=q5 f (q4, b)=Z=q1 f (q5, a)=S,Z=q6* f (q5, b)=R,U,Y,Z=q7* f (q6, a)=Z=q1 f (q6, b)=R,U=q2 f (q7, a)=S,X,U=q5 f (q7, b)=Z=q1 确定化:,S,Z,q0,q2,q7,a,b,a,R,X,Y,U,a,a,a,a,b,b,b,b,q3,q4,q5,q6,q1,a,a,b,b,b,b,b,b,a,a,a,3-14最小化FA,(2)解: :S0,S1,S2,S3 S4,S5,S6 S0,S1a=S5,S6 S2,S3a=S0,S3 :S0,S1 S2,S3 S4,S5,S6 S0,S1b=S2 S0,S1不可划分 S2a=S0 S3a=S3 :S0,S1 S2 S3 S4,S5,S6 S4a=S6 S5,S6a=S3 :S0,S1 S2 S3 S4 S5,S6 S5,S6b=S0,S1 S5,S6不可划分 :S0,S1 S2 S3 S4 S5,S6,3-22构造识别正规语言的DFA,(1)(0*1)(1*0)* 解:q0*=-Closure (S15) =S15,S14,S7,S3,S4,S0,S2,S6,S8,S9,S11,S12 f (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=q2 f (q1, 0)=q1 f (q1, 1)=q2 f (q2, 0)=S13,S14,S7,S4,S3,S0,S2,S6,S8,S9,S11,S12=q3* f (q2, 1)=S10,S9,S11,S12=q4 f (q3, 0)=q1 f (q3, 1)=q2 f (q4, 0)=q3 f (q4, 1)=q4,S15,S7,S14,a,a,0,S3,S0,S1,S2,S4,S5,S6,S8,S9,S10,S11,S12,S13,1,0,1,q0,q1,q3,q2,q4,0,0,0,0,0,1,1,1,1,1,% #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 ( argc 2 ) yyout = fopen( argv2, “w“ );/yyout存放LEXYY的输出程序 else yyout = stdout; yylex(); int yywrap() return 1; ,4-1消除文法的左递归,(1)解一:消除文法的单产生式得 S SASB(S)( )S A SB(S)( )S B S S为直接左递归的非终结符,消除左递归得 S (S)S( )SSS S S AS BS A SB(S)( )S B S 解二:S,A都是左递归的非终结符 (S A B) = (S A B) A B + ( (S)+( ) S+ ) 设 A B * = Z = z11 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 z33,4-4求出文法的FIRST集和FOLLOW集 解:FIRST(S) = a, b, FOLLOW(S) = # FIRST(A) = a, FOLLOW(A) = FIRST(B)/ FOLLOW(S) b = b, # FIRST(B) = b, 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为直接左递归的非终结符,消除左递归得G S AbS bS S bS A aA A aA LL(1)分析表:,解二:消除左递归得G (S A) = (S A) b + (b a) b a 设 b * = Z = z11 z12 b a z21 z22 则有 (S A) = (b a) z11 z12 z21 z22 z11 z12 = + b z11 z12 z21 z22 b a z21 z22 于是得到新的等价文法 Sbz11|az21 Abz12|az22 z11bz11| z12bz12 z21bz11|az21 z22bz12|az22| 删除无用产生式得G S bz11|az21 z11bz11| z21bz11|az21 LL(1)分析表:,4-16改造G为简单优先文法G,并求出全部简单优先关系,(1)解:消去,采用分层法改写得G VAR W : ; W , i i r n b c 简单优先矩阵:,4-31构造算符优先矩阵,并用Floyd方式线性化,解:求各非终结符号FIRSTVT集和LASTVT集 FIRSTVT(P) = (, i LASTVT(P) = ), i FIRSTVT(F) = , (, i LASTVT(F) = , ), i FIRSTVT(T) = *, , (, i LASTVT(T) = *, , ), i FIRSTVT(E) = +, *, , (, i LASTVT(E) = +, *, , ), i 算符优先矩阵: 线性化:,4-35构造识别活前缀的DFA 4-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)分析表如下:,I0: S.S S .A A .Ab A .a,I1: SS.,I2: S A. A A.b,I3: A a.,I4: A Ab.,a,b,S,A,4-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.q1 q1 .begin q2 q3 end,begin,I1: q1q1.,I2:q1 begin .q2 q3 end q2 .q2 d ; q2 .,I3:q1 begin q2 .q3 end q2 q2 .d ; q3 .q3 ; q4 q3 .q4 q4 .S q4 .,I10:q2