第7章作业参考-答案~.doc

《第7章作业参考-答案~.doc》由会员分享，可在线阅读，更多相关《第7章作业参考-答案~.doc（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、|第章 LR 分析1已知文法 AaAd|aAb|判断该文法是否是 SLR(1)文法，若是构造相应分析表，并对输入串 ab#给出分析过程。答案：文法：AaAd|aAb|拓广文法为 G，增加产生式 SA若产生式排序为：0 S A1 A aAd2 A aAb3 A 由产生式知：First (S ) = ,aFirst (A ) = ,aFollow(A ) = d,b,#G的 LR(0)项目集规范族及识别活前缀的 DFA 如下图所示：在 I0 中：A .aAd 和 A .aAb 为移进项目，A .为归约项目，存在移进-归约冲突，因此所给文法不是 LR(0)文法。在 I0、I2 中：Follow(A)

2、 a= d，b，# a=所以在 I0、I2 中的移进-归约冲突可以由 Follow 集解决，所以 G 是 SLR(1)文法。构造的 SLR(1)分析表如下：题目 1 的 SLR(1)分析表对输入串 ab#的分析过程|10.判断下列各题所示文法是否为类方法，若是请说明是 LR(0),SLR(1),LALR(1)或LR(1)的哪一种，并构造相应的分析表，若不是请说明理由（）S-aAd|eBd|aBr|eArA-aB-a答案：）列出扩展文法的产生式列表：(0)S-S(1)S-aAd(2)S-eBd(3)S-aBr(4)S-eAr(5)A-a(6)B-a2） 的 LR(0)项目集族及识别活前缀的 DF

3、A 如下图所示：BI0:S-.SS-.aAdS-.eBdS-.aBrS-.eArI1:S-S.I2:S-a.AdS-a.BrA-.aB-.aI3:S-e.BdS-e.ArB-.aA-.aSaeI4:S-aA.dI5:S-aB.rI6:A-a.B-a.ABaI7:S-eB.dI8:S-eA.rAaI9:S-aAd.dI10:S-aBrd.rI11:S-eBd.dI12:S-eAr.r|从上图中看出项目集 I6 中存在归约-归约冲突，所以该文法不是 LR(0)文法。下面判断是否为 SLR(1)文法：Follow(S)=#Follow(A)=d,rFollow(B)=d,r对于 I6，Follow(

4、A) Follow(B)= d,r不为 ，所以项目集 I6 中的归约-归约冲突不能消除，该文法不是 SLR(1)文法。下面判断是否为 LR(1)文法，在上面的项目集规范族中加入搜索符：从上图可以看出原来存的的归约-归约冲突已经消除，所以该文法为 LR(1)文法。但若合并同心项目集 I6 和 I13，则归约-归约冲突又会重现，因此该文法不是 LALR(1)文法。3)LR(1)分析表Action GotoState a e d r # S A B0 S2 S3 11 acc 2 S6 4 53 S13 8 74 S9 5 S10 6 R5 R6 7 S11 8 S12 BI0:S-.S,#S-.a

5、Ad,#S-.eBd,#S-.aBr,#S-.eAr,#I1:S-S.,#I2:S-a.Ad,#S-a.Br,#A-.a,dB-.a,rI3:S-e.Bd,#S-e.Ar,#B-.a,dA-.a,rSaeI4:S-aA.d,#I5:S-aB.r,#I6:A-a.,dB-a.,rABaI7:S-eB.d,#I8:S-eA.r,#AaI9:S-aAd.,#dI10:S-aBr.,#rI11:S-eBd.,#dI12:S-eAr. ,#rI13:B-a.,dA-a.,r|9 R1 10 R3 11 R2 12 R4 13 R6 R5 11.设文法 GS为：S-AS|A-aA|b（1） 证明 GS是

6、LR1文法;扩展文法 G为：（0） S-S（1） S-AS（2） S-（3） A-aA（4） A-b的 LR(1)项目集族及识别活前缀的 DFA 如下图所示：从上图中可以看出，每个项目集中均无移进-归约冲突和归约-归约冲突，所以该文法为LR(1)文法。（2） 构造它的 LR(1)分析表;Action GotoState a b # S A 0 S3 S4 R2 1 21 acc 2 S3 S4 R2 5 23 S3 S4 64 R4 R4 R4 AbabaI0:S-.S,#S-.AS,#S-.,#A-.aA,a/b/#A-.b, a/b/#I1:S-S.,#SI2:S-A.S,#S-.AS,#

7、S-.,#A-.aA,a/b/#A-.b, a/b/#AI3:A-a.A,a/b/#A-.aA,a/b/#A-.b, a/b/#I4:A-b., a/b/#abI5:S-AS.,#SAI6:A-aA.,a/b/#|5 R1 6 R3 R3 R3 （3） 给出输入符号串 abab#的分析过程。序号 状态栈 符号栈 输入缓冲区 动作1 0 # abab# S3,移进2 03 #a bab# S4,移进3 034 #ab ab# R4,归约 A-b4 036 #aA ab# R3,归约 A-aA5 02 #A ab# S3,移进6 023 #Aa b# S4,移进7 0234 #Aab # R4,归

8、约 A-b8 0236 #AaA # R3,归约 A-aA9 022 #AA # R2,归约 S-10 0225 #AAS # R1,归约 S-AS11 025 #AS # R1,归约 S-AS12 01 #S # acc 成功15.已知文法为：S-a|(T)T-T,S|S(1)构造它的 LR(0)，LALR(1)，LR(1)分析表;扩展文法 G为：（0） S-S（1） S-a（2） S-（3） S-(T)（4） T-T,S（5） T-S1)LR(0)项目集族及识别活前缀的 DFA 如下图所示：(a)(Sa,STI0:S-.SS-.aS-.S-.(T)I1:S-S.SI2:S-a.I4:S-(

9、.T)T-.T,ST-.SS-.aS-.S-.(T)(I7:S-(T).I3:S-.I6:T-S.,I8:T-T, .SS-.aS-.S-.(T)I9:T-T, S.aI5:S-(T.)T-T.,S|LR(0)分析表:Action GotoState a （ ） ， # S T 0 S2 S3 S4 11 acc 2 R1 R1 R1 R1 R1 R1 3 R2 R2 R2 R2 R2 R2 4 S2 S3 S4 6 55 S7 S8 6 R5 R5 R5 R5 R5 R5 7 R3 R3 R3 R3 R3 R3 8 S2 S3 S4 99 R4 R4 R4 R4 R4 R4 2) LR(1)

10、项目集族及识别活前缀的 DFA 如下图所示：图中“,”为文法符号。说明：对于 I4 中的项目 T-.T,S 和 T-.S，先由项目 S-(.T),#推出扩展项目的搜索符为“)”，再由 T-.T,S,) 扩展出新的搜索符“,”，合并后的搜索符为“)/,”。LR(1)分析表:Action GotoState a （ ） ， # S T 0 S2 S3 S4 1),a(S( (aSa,STI0:S-.S,#S-.a,#S-.,#S-.(T),#I1:S-S.,#SI2:S-a.,#I4:S-(.T),#T-.T,S,)/,T-.S,)/,S-.a,)/,S-., )/,S-.(T), )/,(I10

11、:S-(T) .,#)I3:S-.,#I6:T-S.,)/,I11:T-T, .S, )/,S-.a, )/,S-., )/,S-.(T), )/,I13:T-T, S., )/,a I7:S-a., )/,I8:S-.,)/, I9:S-(.T),)/,T-.T,S,)/,T-.S, )/,S-.a, )/,S-., )/,S-.(T), )/,I5:S-(T.),#T-T.,S,)/,I12:S-(T.), )/,T-T.,S,)/,TI14:S-(T) .,)/,|1 acc 2 R1 3 R2 4 S7 S8 S9 6 55 S10 S11 6 R5 R5 7 R1 R1 8 R2 R

12、2 9 S7 S8 S9 6 1210 R3 11 S7 S8 S9 1312 S14 S11 13 R4 R4 14 R3 R3 LALR(1)分析表需将上面 DFA 中的同心项目（同底色）的项目集合并后考虑，将状态数大的合并入状态数小的项目集中，在此不再另画图。 LALR(1)分析表:Action GotoState a （ ） ， # S T 0 S2 S3 S4 11 acc 2 R1 R1 R1 3 R2 R2 R2 4 S2 S3 S4 6 55 S10 S11 6 R5 R5 10 R3 R3 R3 11 S2 S3 S4 1313 R4 R4 (2)给出对输入符号串(a#和(a

13、,a#的分析过程;1) 对输入符号串(a#的分析过程用 LR(0)分析表序号 状态 栈 符号栈 输入缓冲区 动作1 0 # (a# S4,移进2 04 #( a# S2,移进3 042 #(a # R1,归约 S-a4 046 #(S # R5,归约 T-S5 045 #(T # 出错用 LR(1)分析表|序号 状态栈 符号栈 输入缓冲区 动作1 0 # (a# S4,移进2 04 #( a# S7,移进3 047 #(a # 错误用 LALR(1)分析表序号 状态栈 符号栈 输入缓冲区 动作1 0 # (a# S4,移进2 04 #( a# S2,移进3 042 #(a # R1,归约 S-

14、a4 046 #(S # 错误2) 对输入符号串(a,a#的分析过程用 LR(0)分析表序号 状态栈 符号栈 输入缓冲区 动作1 0 # (a,a# S4,移进2 04 #( a,a# S2,移进3 042 #(a ,a# R1,归约 S-a4 046 #(S ,a# R5,归约 T-S5 045 #(T ,a# S8,移进6 0458 #(T, a# S2,移进7 04582 #(T,a # R1,归约 S-a8 04589 #(T,S # R4,归约 T-T,S9 045 #(T # 出错用 LR(1)分析表序号 状态栈 符号栈 输入缓冲区 动作1 0 # (a,a# S4,移进2 04

15、#( a,a# S7,移进3 047 #(a ,a# R1,归约 S-a4 046 #(S ,a# R5,归约 T-S5 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-a4 046 #(S ,a# R5,归约 T-S5 045 #(T ,a# S11,移进6 045(11) #(T, a# S2,移进7 045(11)2 #(T,a # R1,

16、归约 S-a8 045(11)(13) #(T,S # 出错|(3)说明（1）中三种分析表发现错误的时刻和输入串的出错位置有何区别。见（2），由此二例说明，对于错误分析，LR(1)的效率最高，LALR(1)次之，LR(0)最差。补充题：GS 文法如下，求其 LR 分析表 1. SAaDC 2. CCba 3. Cba 4. DA5. DBa 6. Ab 7. Bb答：扩展文法 G为：0. SS1. SAaDC 2. CCba 3. Cba 4. DA5. DBa 6. Ab 7. Bb答:1)首先判断是否为 LR(0)方法：由上图中可以看到 I8 中存在归约-归约冲突，I9 中存在移进-归约冲

17、突，所以该文法不是 LR(0)文法2)再判断是否为 SLR(1)文法：Follow(S)=#Follow(A)=a,bFollow(B)=aFollow(C)=b,#Follow(D)=baabCADSaBbbAaI0:S-.SS-.AaDCA.b I1:S-S.I2:S-A.aDCI3:Ab. bI4:S-Aa.DCD.AD.BaA.bB.bI7:DB.aI5:S-AaD.CC.CbaC.baI6:DA.I8:Ab.Bb.I9:S-AaDC.CC.baI10:Cb.aI11:DBa.I12:CCb.aI13:CCba.I14:Cba.|2 对于 I8，Follow(A) Follow(B)=

18、a,不为空，因此该文法不是 SLR(1)文法。3)判断是否为 LR(1)文法：说明：上图中 I8 中 C.Cba,#/b 中的搜索符#/b 分二步得到，先由 S-AaD.C,#得到#，再由 C.Cba,#得到 b。由上图可看出原先 I8,I9 存在的冲突已消除，所以为 LR(1)文法。LR(1)分析表：Action GotoState a b # S A B C D 0 S3 1 21 acc 2 S4 3 R6 4 S8 6 7 55 S10 96 R4 7 S11 8 R7 R6 9 S12 R1 10 S14 11 R5 12 S13 13 R2 R2 14 R3 R3 aabCADSaBbbAaI0:S-.S,#S-.AaDC,#A.b,aI1:S-S.,#I2:S-A.aDC,#I3:Ab.,abI4:S-Aa.DC,#D.A,bD.Ba,bA.b,bB.b,aI7:DB.a,bI5:S-AaD.C,#C.Cba,#/bC.ba,#/bI6:DA.,bI8:Ab.,bBb.,aI9:S-AaDC.,#CC.ba,#/bI10:Cb.a,#/bI11:DBa.,bI12:CCb.a,#/bI13:CCba.,#/bI14:Cba.,#/b