compiler-龙书-习题解答-学生.pdf

1 3.7.6 p166 3.6 节的练习 p103 Exercise 3.7.1 练习 3.6.1 NFA 确定化 NFA 确定化 + 代表终态 a) Fig. 3.26 p150 确定化 a b 0,1,3 2 4 + 2 2 + 4 4 b) Fig. 3.29 p151 确定化 a b 0 0,1 0 0,1 0,1,2 0,1 0,1,2 0,1,2 0,1,2,3 + 0,1,2,3 0,1,2 0,1,2,3 c) Fig. 3.30 p152 确定化 a b + 0,1,2,3 0,1,2,3 0,1,2,3 2 3.9.9 p186 Exercise 3.9.4 a) 补充 已知正则表达式,构造最小化自动机 a) (a|b)*a(a|b) 确定化 a b S :1 S,A S S,A :2 S,A,B S,B + S,A,B :3 S,A,B S,B + S,B :4 S,A S 确定化 a b 1 2 1 2 3 4 + 3 3 4 + 4 2 1 最小化: 0: 1,2 3,4 1: 1 2 3,4 将 1 和 2 分开的原因: 1 遇到 a 转移到1,2; 2 遇到 a 转移到3,4 2: 1 2 3 4 将 3 和 4 分开的原因: 3 遇到 a 转移到3,4; 4 遇到 a 转移到2 所以, 最小化结果与确定化结果相同 a S A B a a b b NFA 3 Chapter 4 4.2.8 p206 4.2 节的练习 p119 Exercise 4.2.1 练习 4.2.1 推导、语法树、二义、语言 答案 略 Exercise 4.2.3 练习 4.2.3 设计文法 a)* b)* 1)* 2)* a) G: S 1S | 0A | A 1S b) G: S 0S0 | 1S1 | 4.3.6 p216 4.3 节的练习 p126 Exercise 4.3.1 练习 4.3.1 提左公因子,消左递归,LL1 判别 a) b) c) 消除左递归 E TE E +TE | T FT T FT | F PF F *F | P a | b Exercise 4.3.2 练习 4.3.2 提左公因子,消左递归,LL1 判别 a) 1) 1 A S 1 0 4 4.4.6 p231 4.4 节的练习 p136 Exercise 4.4.1 练习 4.4.1 预测分析表 d) e) 4) 5) d) S S+S | SS | (S) | S* | a 消除左递归 G: S (S)B | aB B +SB | SB | *B | FIRST FOLLOW S ( a $ ) + ( a * B + ( a * $ ) + ( a * SELECT S (S)B ( S aB a B +SB + B SB ( a B *B * B $ ) + ( a * + * ( ) a $ S (S)B aB B +SB *B SB SB 5 e) S (L) | a L L,S | S 消除左递归 G: S (L) | a L SL L ,SL | FIRST FOLLOW S ( a $ , ) L ( a ) L , ) SELECT S (L) ( S a a L SL ( a L ,SL , L ) ( ) a , $ S (L) a L SL SL L ,SL Exercise 4.4.3 练习 4.4.3 First 集合、Follow 集 G: S SS+ | SS* | a FIRST FOLLOW S a $ a + * Exercise 4.4.4 练习 4.4.4 First 集合、Follow 集 b) c) f) g) 2) 3) 6) 7) b) S +SS | *SS | a FIRST FOLLOW S + * a $ + * a c) S S(S)S | FIRST FOLLOW S ( $ ( ) f) S aSbS | bSaS | 6 FIRST FOLLOW S a b $ b a g) 将文法简写为： E E o T | T T T a F | F F n F | (E) | t | f FIRST FOLLOW E n ( t f $ o ) T n ( t f $ o ) a F n ( t f $ o ) a 7 4.5.5 p240 4.5 节的练习 p141 Exercise 4.5.1 练习 4.5.1 句柄 a) 010203111213 句柄: 0311 b) 0102S1112 句柄: 02S11 Exercise 4.5.2 练习 4.5.2 句柄 a) c) 1) 3) a) S1S2S3+a+ 句柄: S2S3+ c) a1a2a3*a4+ 句柄: a1 4.6.6 p257 4.6 节的练习 p153 Exercise 4.6.1 练习 4.6.1 描述文法的活前缀 a) 1) a) S 0S1 | 01 构造识别文法所有活前缀的自动机： 活前缀的正则表达式：S | 00*S1 | 00*1 I0: S S S 0S1 S 01 I1: S S S I2: S 0 S1 S 0 1 S 0S1 S 01 0 I3: S 0S 1 S 1 I4: S 01 0 1 I5: S 0S1 S S 0 1 1 0 8 Exercise 4.6.2 练习 4.6.2 SLR 分析表 S SS+ | SS* | a G : S S (0) S SS+ (1) S SS* (2) S a (3) FIRST FOLLOW S a $ a + * + * a $ S 0 S2 1 1 S2 acc 3 2 r3 r3 r3 r3 3 S4 S5 S2 3 4 r1 r1 r1 r1 5 r2 r2 r2 r2 以上分析表不含多重定义入口，所以文法是 SLR 文法。 I0: S S S SS+ S SS* S a I1: S S S S S+ S S S* S SS+ S SS* S a S a I2: S a r3 S I3: S SS + S SS * S S S+ S S S* S SS+ S SS* S a a + I4: S SS+ r1 * I5: S SS* r2 S a r0 9 Exercise 4.6.3 练习 4.6.3 LR 分析过程 状态栈 符号栈 输入 动作 0 $ aa*a+ $ s2 02 $a a*a+ $ r3 S a 01 $S a*a+ $ s2 012 $Sa *a+ $ r3 S a 013 $SS *a+ $ s5 0135 $SS* a+ $ r2 S SS* 01 $S a+ $ s2 012 $Sa + $ r3 S a 013 $SS + $ s4 0134 $SS+ $ r1 S SS+ 01 $S $ acc 10 Exercise 4.6.5 练习 4.6.5 LL(1)判别、SLR 判别 G : S S (0) S AaAb (1) S BbBa (2) A (3) B (4) FIRST FOLLOW S a b $ A a b B a b SELECT(S AaAb) SELECT(S BbBa) = a b = 空集；所以文法是 LL(1)文法。 参考 I0: S S S AaAb S BbBa A B r3 r4 I0中存在归约-归约冲突，所以不是 SLR 文法。 I0: S S S AaAb S BbBa A B r3 r4 S I1: S S A I2: S A aAb B I3: S B bBa a I4: S Aa Ab A b I5: S Bb Ba B r3 r4 A I6: S AaA b B I7: S BbB a I8: S AaAb r1 b a I9: S BbBa r2 11 Exercise 4.6.6 练习 4.6.6 LL(1)判别、SLR 判别 G : S S (0) S SA (1) S A (2) A a (3) FIRST FOLLOW S a $ a A a $ a SELECT(S SA) SELECT(S A) = a a = a；所以文法不是 LL(1)文法。 (也可以不求 FIRST 集和 FOLLOW 集，因为文法中包含左递归,所以文法不是 LL(1)文法。) I1 中存在移进项目和归约项目，但冲突可以通过以下方式解决: 遇 a 移进，遇$归约， 所以是 SLR 文法 I0: S S S SA S A A a S I1: S S S S A A a I2: S A A I3: S a a r2 r3 A I 4: S SA r1 a 12 4.7.7 p277 4.7 节的练习 p165 Exercise 4.7.1 练习 4.7.1 LR、LALR S SS+ | SS* | a G : S S (0) S SS+ (1) S SS* (2) S a (3) FIRST FOLLOW S a $ a + * LALR 合并同心集 I0: S S , $ S SS+ , $/a S SS* , $/a S a , $/a S I1: S S , $ S S S+ , $/a S S S* , $/a S SS+ , +/*/a S SS* , +/*/a S a , +/*/a a I2: S a , $/a r3 a I4: S a , +/*/a r3 S I3: S SS + , $/a S SS * , $/a S S S+ , +/*/a S S S* , +/*/a S SS+ , +/*/a S SS* , +/*/a S a , +/*/a + I7: S SS + ,+/*/a S SS * ,+/*/a S S S+ , +/*/a S S S* , +/*/a S SS+ , +/*/a S SS* , +/*/a S a , +/*/a * I5: S SS+ , $/a r1 I6: S SS* , $/a r2 S I8: S SS+ , +/*/a r1 I9: S SS* , +/*/a r2 S a + * a 13 I37: S SS + , $/+/*/a S SS * , $/+/*/a S S S+ , +/*/a S S S* , +/*/a S SS+ , +/*/a S SS* , +/*/a S a , +/*/a I24: S a , $/+/*/a r3 I58: S SS+ , $/+/*/a r1 I69: S SS* , $/+/*/a r2 14 Exercise 4.7.5 练习 4.7.5 LR、LALR G : S S (0) S Aa (1) S bAc (2) S Bc (3) S bBa (4) A d (5) B d (6) LR 判别：以上 LR 项目集规范族中不存在冲突，所以文法是 LR 文法。 LALR 判别：合并同心集, 存在归约-归约冲突, 所以文法不是 LALR 文法。 I0: S S ,$ S Aa ,$ S bAc ,$ S Bc ,$ S bBa ,$ A d ,a B d ,c S I1: S S ,$ r0 A I