第7章作业参考答案

第７章LR分析1．已知文法A→aAd|aAb|ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。答案：文法：A→aAd|aAb|ε拓广文法为G′，增加产生式S′→A若产生式排序为：0S'→A1A→aAd2A→aAb3A→ε由产生式知：First(S')={ε,a}First(A)={ε,a}Follow(A)={d,b,#}G′的LR(0)项目集规范族及识别活前缀的DFA如下图所示：在I0中：A→.aAd和A→.aAb为移进项目，A→.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I0、I2中：Follow(A)∩{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)项目集族及识别活前缀的DFA如下图所示：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,r}Follow(B)={d,r}对于I6，Follow(A)∩Follow(B)={d,r}不为φ，所以项目集I6中的归约-归约冲突不能消除，该文法不是SLR(1)文法。下面判断是否为LR(1)文法，在上面的项目集规范族中加入搜索符：从上图可以看出原来存的的归约-归约冲突已经消除，所以该文法为LR(1)文法。但若合并同心项目集I6和I13，则归约-归约冲突又会重现，因此该文法不是LALR(1)文法。3)LR(1)分析表ActionGotoStateaedr#SAB0S2S311acc2S6453S13874S95S106R5R67S118S129R1BI0:S＇-.S,#S-.aAd,#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.,r10R311R212R413R6R511.设文法G[S]为：S-AS|εA-aA|b（1）证明G[S]是LR[1]文法;扩展文法G’为：（0）S’-S（1）S-AS（2）S-ε（3）A-aA（4）A-bＧ＇的LR(1)项目集族及识别活前缀的DFA如下图所示：从上图中可以看出，每个项目集中均无移进-归约冲突和归约-归约冲突，所以该文法为LR(1)文法。（2）构造它的LR(1)分析表;ActionGotoStateab#SA0S3S4R2121acc2S3S4R2523S3S464R4R4R45R1AbabaI0:S’-.S,#S-.AS,#S-.,#A-.aA,a/b/#A-.b,a/b/#I1:S’-S.,#SI2:S-A.S,#S-.AS,#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/#6R3R3R3（3）给出输入符号串abab#的分析过程。序号状态栈符号栈输入缓冲区动作10#abab#S3,移进203#abab#S4,移进3034#abab#R4,归约A-b4036#aAab#R3,归约A-aA502#Aab#S3,移进6023#Aab#S4,移进70234#Aab#R4,归约A-b80236#AaA#R3,归约A-aA9022#AA#R2,归约S-ε100225#AAS#R1,归约S-AS11025#AS#R1,归约S-AS1201#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如下图所示：LR(0)分析表:(a)∧(∧Sa,STI0:S’-.SS-.aS-.∧S-.(T)I1:S’-S.SI2:S-a.I4:S-(.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.,SActionGotoStatea∧（），#ST0S2S3S411acc2R1R1R1R1R1R13R2R2R2R2R2R24S2S3S4655S7S86R5R5R5R5R5R57R3R3R3R3R3R38S2S3S499R4R4R4R4R4R42)LR(1)项目集族及识别活前缀的DFA如下图所示：图中“,”为文法符号。说明：对于I4中的项目T-.T,S和T-.S，先由项目S-(.T),#推出扩展项目的搜索符为“)”，再由T-.T,S,)扩展出新的搜索符“,”，合并后的搜索符为“)/,”。LR(1)分析表:ActionGotoStatea∧（），#ST0S2S3S411acc),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:S-(T).,#)I3:S-∧.,#I6:T-S.,)/,I11:T-T,.S,)/,S-.a,)/,S-.∧,)/,S-.(T),)/,I13:T-T,S.,)/,aI7: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).,)/,2R13R24S7S8S9655S10S116R5R57R1R18R2R29S7S8S961210R311S7S8S91312S14S1113R4R414R3R3LALR(1)分析表需将上面DFA中的同心项目（同底色）的项目集合并后考虑，将状态数大的合并入状态数小的项目集中，在此不再另画图。LALR(1)分析表:ActionGotoStatea∧（），#ST0S2S3S411acc2R1R1R13R2R2R24S2S3S4655S10S116R5R510R3R3R311S2S3S41313R4R4(2)给出对输入符号串(a#和(a,a#的分析过程;1)对输入符号串(a#的分析过程用LR(0)分析表序号状态栈符号栈输入缓冲区动作10#(a#S4,移进204#(a#S2,移进3042#(a#R1,归约S-a4046#(S#R5,归约T-S5045#(T#出错用LR(1)分析表序号状态栈符号栈输入缓冲区动作10#(a#S4,移进204#(a#S7,移进3047#(a#错误用LALR(1)分析表序号状态栈符号栈输入缓冲区动作10#(a#S4,移进204#(a#S2,移进3042#(a#R1,归约S-a4046#(S#错误2)对输入符号串(a,a#的分析过程用LR(0)分析表序号状态栈符号栈输入缓冲区动作10#(a,a#S4,移进204#(a,a#S2,移进3042#(a,a#R1,归约S-a4046#(S,a#R5,归约T-S5045#(T,a#S8,移进60458#(T,a#S2,移进704582#(T,a#R1,归约S-a804589#(T,S#R4,归约T-T,S9045#(T#出错用LR(1)分析表序号状态栈符号栈输入缓冲区动作10#(a,a#S4,移进204#(a,a#S7,移进3047#(a,a#R1,归约S-a4046#(S,a#R5,归约T-S5045#(T,a#S11,移进6045(11)#(T,a#S7,移进7045(11)7#(T,a#出错用LALR(1)分析表序号状态栈符号栈输入缓冲区动作10#(a,a#S4,移进204#(a,a#S2,移进3042#(a,a#R1,归约S-a4046#(S,a#R5,归约T-S5045#(T,a#S11,移进6045(11)#(T,a#S2,移进7045(11)2#(T,a#R1,归约S-a8045(11)(13)#(T,S#出错(3)说明（1）中三种分析表发现错误的时刻和输入串的出错位置有何区别。见（2），由此二例说明，对于错误分析，LR(1)的效率最高，LALR(1)次之，LR(0)最差。补充题：G[S]文法如下，求其LR分析表1.S→AaDC2.C→Cba3.C→ba4.D→A5.D→Ba6.A→b7.B→b答：扩展文法G’为：0.S’→S1.S→AaDC2.C→Cba3.C→ba4.D→A5.D→Ba6.A→b7.B→b答:1)首先判断是否为LR(0)方法：由上图中可以看到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)文法。aabCADSaBbbAaI0:S’-.SS-.AaDCA→.bI1:S’-S.I2:S-A.aDCI3:A→b.bI4:S-Aa.DCD→.AD→.BaA→.bB→.bI7:D→B.aI5:S-AaD.CC→.CbaC→.baI6:D→A.I8:A→b.B→b.I9:S-AaDC.C→C.baI10:C→b.aI11:D→Ba.I12:C→Cb.aI13:C→Cba.I14:C→ba.3)判断是否为LR(1)文法：说明：上图中I8中C→.Cba,#/b中的搜索符#/b分二步得到，先由S-AaD.C,#得到#，再由C→.Cba,#得到b。由上图可看出原先I8,I9存在的冲突已消除，所以为LR(1)文法。LR(1)分析表：ActionGotoStateab#SABCD0S3121acc2S43R64S86755S1096R47S118R7R69S12R110S1411R512S1313R2R214R3R3aabCADSaBbbAa