第7章作业参考答案(2)

State 0 1 2 3 4 5 6 7 8 9 Action a ∧ （ ） ， # S2 S3 S4 acc R1 R1 R1 R1 R1 R1 R2 R2 R2 R2 R2 R2 S2 S3 S4 S7 S8 R5 R5 R5 R5 R5 R5 R3 R3 R3 R3 R3 R3 S2 S3 S4 R4 R4 R4 R4 R4 R4 Goto S T 1 6 5 9

2) LR(1)项目集族及识别活前缀的DFA 如下图所示： S I1: I0: S’->S.,# S’->.S,# S->.a,# a I2: S->.∧,# I10: S->a.,# S->.(T),# S->(T) .,# I3: ∧ ( ) S->∧.,# I11: I4: T->T, .S, )/, S , I13: S->(.T),# I5: T S->.a, )/, T->T, S., )/, T->.T,S,)/, S->(T.),# S->.∧, )/, T->.S,)/, T->T.,S,)/, ∧ S->.(T), )/, S->.a,)/, a ( S->.∧, )/, ∧ I8: S->.(T), )/, S->∧.,)/, ∧ I9: , I12: S->(.T),)/, a S->(T.), )/, I7: S T->.T,S,)/, T->T.,S,)/, a T S->a., )/, I6: T->.S, )/, ( T->S.,)/, ) S->.a, )/, S S->.∧, )/, I14: S->.(T), )/, ( S->(T) .,)/, 图中“,”为文法符号。 说明：对于I4中的项目T->.T,S和T->.S，先由项目S->(.T),#推出扩展项目的搜索符为“)”，再由T->.T,S,) 扩展出新的搜索符“,”，合并后的搜索符为“)/,”。 LR(1)分析表: Action State a ∧ （ ） ， # 0 S2 S3 S4 1 acc Goto S T 1 2 3 4 5 6 7 8 9 10 11 12 13 14 R1 R2 S7 S8 S9 S10 S11 R5 R5 R1 R1 R2 R2 S7 S8 S9 R3 S7 S8 S9 S14 S11 R4 R4 R3 R3 6 5 6 12 13

LALR(1)分析表需将上面DFA中的同心项目（同底色）的项目集合并后考虑，将状态数大的合并入状态数小的项目集中，在此不再另画图。 LALR(1)分析表:

State 0 1 2 3 4 5 6 10 11 13 Action a ∧ （ ） ， # S2 S3 S4 acc R1 R1 R1 R2 R2 R2 S2 S3 S4 S10 S11 R5 R5 R3 R3 R3 S2 S3 S4 R4 R4 Goto S T 1 6 5 13 (2) 给出对输入符号串(a#和(a,a#的分析过程; 1) 对输入符号串(a#的分析过程 用LR(0)分析表

状态

符号栈 输入缓冲区 序号

栈

动作 S4,移进 S2,移进 R1,归约 S->a R5,归约 T->S

出错

1 2 3 4 5 0 04 042 046 045 # #( #(a #(S #(T (a# a# # # #

用LR(1)分析表

序号 状态栈 符号栈 输入缓冲区

动作

1 2 3 0 04 047 # #( #(a (a# a# # S4,移进 S7,移进 错误

用LALR(1)分析表

序号 状态栈 符号栈 输入缓冲区

1 2 3 4 0 04 042 046 # #( #(a #(S (a# a# # #

动作 S4,移进 S2,移进 R1,归约 S->a

错误

2) 对输入符号串(a,a#的分析过程 用LR(0)分析表

序号 状态栈 符号栈 输入缓冲区

1 0 # (a,a# 2 04 #( a,a# 3 042 #(a ,a# 4 046 #(S ,a# 5 045 #(T ,a# 6 0458 #(T, a# 7 04582 #(T,a # 8 04589 #(T,S # 9 045 #(T # 用LR(1)分析表

符号栈 输入缓冲区 序号 状态栈 动作

1 0 # (a,a# S4,移进 2 04 #( a,a# S7,移进 3 047 #(a ,a# R1,归约 S->a 4 046 #(S ,a# R5,归约 T->S 5 045 #(T ,a# S11,移进 6 045(11) #(T, a# S7,移进 7 045(11)7 #(T,a # 出错 用LALR(1)分析表

符号栈 输入缓冲区 序号 状态栈 动作

1 0 # (a,a# S4,移进 2 04 #( a,a# S2,移进 3 042 #(a ,a# R1,归约 S->a 4 046 #(S ,a# R5,归约 T->S 5 045 #(T ,a# S11,移进 6 045(11) #(T, a# S2,移进 7 045(11)2 #(T,a # R1,归约 S->a 8 045(11)(13) #(T,S # 出错

(3) 说明（1）中三种分析表发现错误的时刻和输入串的出错位置有何区别。

动作 S4,移进 S2,移进 R1,归约 S->a R5,归约 T->S S8,移进 S2,移进 R1,归约 S->a R4,归约 T->T,S

出错

见（2），由此二例说明，对于错误分析，LR(1)的效率最高，LALR(1)次之，LR(0)最差。

补充题：G[S] 文法如下，求其LR分析表 1. S→AaDC 2. C→Cba 3. C→ba 4. D→A 5. D→Ba 6. A→b

7. B→b

答：扩展文法G’为： 0. S’→S

1. S→AaDC 2. C→Cba 3. C→ba 4. D→A 5. D→Ba 6. A→b

7. B→b

答:1)首先判断是否为LR(0)方法： a I10: S I0: I1: I4: I5: b C→b.a S’->.S S’->S. S->Aa.DC S->AaD.C D S->.AaDC D→.A C→.Cba A I9: I2: a C A→.b C→.ba D→.Ba S->AaDC. S->A.aDC A→.b A C→C.ba I6: B→.b b D→A. b b B I3: I12: A→b. I7: I8: C→Cb.a D→B.a A→b. a B→b. a I13: I11: C→Cba. D→Ba. 由上图中可以看到I8中存在归约-归约冲突，I9中存在移进-归约冲突，所以该文法不是LR(0)文法

2)再判断是否为SLR(1)文法：

Follow(S)={#} Follow(A)={a,b} Follow(B)={a} Follow(C)={b,#} Follow(D)={b}

2对于I8，Follow(A) ∩Follow(B)={a},不为空，因此该文法不是SLR(1)文法。

I14: C→ba. 3)判断是否为LR(1)文法：

I0: S I1: S’->S.,# S’->.S,# S->.AaDC,# A→.b,a A b I3: A→b.,a I2: a S->A.aDC,# I4: S->Aa.DC,# D D→.A,b D→.Ba,b A→.b,b A B→.b,a B I7: D→B.a,b a b I5: b S->AaD.C,# C→.Cba,#/b C C→.ba,#/b I6: D→A.,b I8: A→b.,b B→b.,a I10: C→b.a,#/b I9: S->AaDC.,# C→C.ba,#/b b I12: C→Cb.a,#/b a a I14: C→ba.,#/b I13: I11: C→Cba.,#/b 说明：上图中I8中C→.Cba,#/b中的搜索符D→Ba.,b #/b分二步得到，先由S->AaD.C,#得到#，再由C→.Cba,#得到b。

由上图可看出原先I8,I9存在的冲突已消除，所以为LR(1)文法。 LR(1)分析表： State 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Action a b # S3 acc S4 R6 S8 S10 R4 S11 R7 R6 S12 R1 S14 R5 S13 R2 R2 R3 R3 Goto S A B C D 1 2 6 7 5 9

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第7章作业参考答案(2)在线全文阅读。