第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)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 作业 参考 答案
限制150内