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) a= d,
2、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|eAr A-a B-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 如下图所示:从上图中看
3、出项目集I6中存在归约-归约冲突,所以该文法不是LR(0)文法。下面判断是否为SLR(1)文法:Follow(S)=#Follow(A)=d,rFollow(B)=d,r对于I6,Follow(A) Follow(B)= d,r不为,所以项目集I6中的归约-归约冲突不能消除,该文法不是SLR(1)文法。下面判断是否为LR(1)文法,在上面的项目集规范族中加入搜索符:从上图可以看出原来存的的归约-归约冲突已经消除,所以该文法为LR(1)文法。但若合并同心项目集I6和I13,则归约-归约冲突又会重现,因此该文法不是LALR(1)文法。3)LR(1)分析表ActionGotoState a e d
4、r # S A B0 S2 S3 11 acc2 S6 4 53 S13 8 74 S95 S106 R5 R67 S118 S129 R110 R311 R212 R413 R6 R511.设文法GS为:S-AS|A-aA|b(1) 证明GS是LR1文法; 扩展文法G为:(1) S-S(2) S-AS(3) S-(4) A-aA(5) A-b的LR(1)项目集族及识别活前缀的DFA 如下图所示:从上图中可以看出,每个项目集中均无移进-归约冲突和归约-归约冲突,所以该文法为LR(1)文法。(2) 构造它的LR(1)分析表;ActionGotoState a b # S A 0 S3 S4 R2
5、 1 21 acc2 S3 S4 R2 5 23 S3 S4 64 R4 R4 R45 R16 R3 R3 R3(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.已知文
6、法为:S-a|(T)T-T,S|S(1) 构造它的LR(0),LALR(1),LR(1)分析表; 扩展文法G为:(1) S-S(2) S-a(3) S-(4) S-(T)(5) T-T,S(6) T-S1)LR(0)项目集族及识别活前缀的DFA 如下图所示:LR(0)分析表:ActionGotoState a ( ) , # S T 0 S2 S3 S4 11 acc2 R1 R1 R1 R1 R1 R13 R2 R2 R2 R2 R2 R24 S2 S3 S4 6 55 S7 S86 R5 R5 R5 R5 R5 R57 R3 R3 R3 R3 R3 R38 S2 S3 S4 99 R4 R
7、4 R4 R4 R4 R42) LR(1)项目集族及识别活前缀的DFA 如下图所示:图中“,”为文法符号。说明:对于I4中的项目T-.T,S和T-.S,先由项目S-(.T),#推出扩展项目的搜索符为“)”,再由T-.T,S,) 扩展出新的搜索符“,”,合并后的搜索符为“)/,”。LR(1)分析表:ActionGotoState a ( ) , # S T 0 S2 S3 S4 11 acc2 R13 R24 S7 S8 S9 6 55 S10 S116 R5 R57 R1 R18 R2 R29 S7 S8 S9 6 1210 R3 11 S7 S8 S9 1312 S14 S1113 R4 R
8、414 R3 R3LALR(1)分析表需将上面DFA中的同心项目(同底色)的项目集合并后考虑,将状态数大的合并入状态数小的项目集中,在此不再另画图。 LALR(1)分析表:ActionGotoState a ( ) , # S T 0 S2 S3 S4 11 acc2 R1 R1 R13 R2 R2 R24 S2 S3 S4 6 55 S10 S116 R5 R510 R3 R3 R3 11 S2 S3 S4 1313 R4 R4(2) 给出对输入符号串(a#和(a,a#的分析过程;1) 对输入符号串(a#的分析过程用LR(0)分析表序号状态栈符号栈输入缓冲区动作10#(a#S4,移进204#
9、(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
10、,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
11、#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)最差。补充题:GS 文法如下,求其LR分析表 1. SAaDC 2. CCba 3. Cba 4. DA 5. DBa 6. Ab 7. Bb答:扩展文法G为: 0. SS1. SAaDC 2. CCba 3. Cba 4. DA 5. DBa 6. Ab 7
12、. Bb答:1)首先判断是否为LR(0)方法:由上图中可以看到I8中存在归约-归约冲突,I9中存在移进-归约冲突,所以该文法不是LR(0)文法2)再判断是否为SLR(1)文法:Follow(S)=#Follow(A)=a,bFollow(B)=aFollow(C)=b,#Follow(D)=b2对于I8,Follow(A) Follow(B)=a,不为空,因此该文法不是SLR(1)文法。3)判断是否为LR(1)文法:说明:上图中I8中C.Cba,#/b中的搜索符#/b分二步得到,先由S-,#得到#,再由C.Cba,#得到b。由上图可看出原先I8,I9存在的冲突已消除,所以为LR(1)文法。LR(1)分析表:ActionGotoState a b # S A B C D 0 S3 1 21 acc2 S43 R64 S8 6 7 55 S10 96 R47 S118 R7 R69 S12 R110 S1411 R512 S1313 R2 R214 R3 R3
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2