编译原理习题.ppt

习题 第2章2 2试分别构造产生下列语言的文法 2 anbmcp n m p 0 解一 S ABCA aA B bB C cC 解二 S aS XX bX YY cY 3 an bn n 0 cn dn n 0 错解 S aSb cSd 解 S X YX aXb Y cYd 6 偶数个0和偶数个1组成的符号串的集合解 S 1A 0B A 1S 0CB 0S 1CC 0A 1B 考察0开头的0011 0101 0110 2 3试描述由下列文法所产生的语言的特点 1 10 nabma0n n m 0 4 S baSndc n 0 5 a2n 1 n 1 2 6句子L L begind d s s end的语法树 L L begin d d S end d 2 11 1 S ABS cA bAA aB aSbB cbbaacb解 最右推导 下划线为各步直接推导所得句型的句柄 S AB AaSb Aacb bAacb bbAacb bbaacb a1 a1是句子bbaacb相对于非终结符A1的直接短语b1a1 A2的短语b2b1a1 A3的短语c S1的直接短语a2cb3 B的短语b2b1a1a2cb3 S2的短语其中 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 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 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 2Vn2 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 aAA aA aA bAc bc dAe 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 T T F P F E i T T F P F E i F P F E i P E i 第3章3 9对应状态矩阵画出状态图 写出相应3型文法 描述输入串特征 解 S bS aAA aA bBB aB bB b aa b a b 解 S aA bBA bA aC B aB bCC aC bC ab ab a ba b a b 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 q1 a q1 q1 b q2 q0 q1 q2 q3 q2 q3 a q3 q2 q3 b 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 q0 a q2 q1 a q0 q0 q1 q2 q3 q2 q3 a q0 q2 q3 b 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 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确定化 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 S1 a S5 S6 S2 S3 a S0 S3 S0 S1 S2 S3 S4 S5 S6 S0 S1 b S2 S0 S1 不可划分 S2 a S0 S3 a S3 S0 S1 S2 S3 S4 S5 S6 S4 a S6 S5 S6 a S3 S0 S1 S2 S3 S4 S5 S6 S5 S6 b 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 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 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 includecharbuf 100 char p q a zA Z p yytext q buf while p q toupper p p q q 0 strcpy yytext buf ECHO 040 t n fprintf yyout ECHO 3 29 main intargc char argv if argc 1 yyin fopen argv 1 r yyin存放LEXYY的输入源程序elseyyin stdin if argc 2 yyout fopen argv 2 w yyout存放LEXYY的输出程序elseyyout stdout yylex intyywrap return1 4 1消除文法的左递归 1 解一 消除文法的单产生式得S SA SB S S A SB S S B S S为直接左递归的非终结符 消除左递归得S S S S S S S S AS BS A SB S S B S 解二 S A都是左递归的非终结符 SAB SAB AB S S 设AB Z z11z12z13 z21z22z23 z31z32z33则有 SAB S S z11z12z13z21z22z23z31z32z33z11z12z13 AB z11z12z13z21z22z23 z21z22z23z31z32z33 z31z32z33 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 fD 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 SA SA b ba ba设b Z z11z12baz21z22则有 SA ba z11z12z21z22z11z12 b z11z12z21z22 baz21z22于是得到新的等价文法S bz11 az21A bz12 az22z11 bz11 z12 bz12z21 bz11 az21z22 bz12 az22 删除无用产生式得G S bz11 az21z11 bz11 z21 bz11 az21LL 1 分析表 4 16改造G为简单优先文法G 并求出全部简单优先关系 1 解 消去 采用分层法改写得G VARW 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构造识别活前缀的DFA4 36判别是否LR 0 文法 构造LR 0 分析表 4 1 S A2 A Ab3 A a解 引入S S作为0号产生式 识别活前缀的DFA如下 I2中有移进 归约冲突 不是LR 0 文法FOLLOW S b 可用SLR 1 规则解决冲突相应的LR 0 和SLR 1 分析表如下 I0 S SS AA AbA a I1 S S 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 beginq2q3end2 q2 q2d 3 q2 4 q3 q3 q45 q3 q46 q4 S7 q4 引入q1 q1作为0号产生式 识别活前缀的DFA如下 I0 q1 q1q1 beginq2q3end begin I1 q1 q1 I2 q1 begin q2q3endq2 q2d q2 I3 q1 beginq2 q3endq2 q2 d q3 q3 q4q3 q4q4 Sq4 I10 q2 q2d I11 q2 q2d I4 q1 beginq2q3 endq3 q3 q4 I5 q3 q4 I6 q4 S I7 q1 beginq2q3end I8 q3 q3 q4q4 Sq4 I9 q3 q3 q4 q2 q1 d q2 q4 S q4 end S I3 I8中有移进 归约冲突FOLLOW q4 end S 可用SLR 1 规则解决 是SLR 1 文法相应的SLR 1 分析表