1、作业参考答案解析第7章LR分析1.已知文法AaAd aAb e判断该文法是否是SLR(l)文法，若是构造相应分析表，并对输入串ab#给出分析过程。 答案：文法：AaAd aAb w拓广文法为G,增加产生式S，-*A若产生式排序为：0 S -A1A aAd2A aAb3A - w由产生式知：First (S ) = e, aFirst (A ) = w, aFol low (A ) = d, b, #Gf的LR(0)项目集规范族及识别活前缀的DFA如下图所示：在I。中：A -aAd和A -.aAb为移进项目，A 一为归约项目，存在移进-归约冲突，因 此所给文法不是LR(O)文法。在 I。、L 中
2、：Fol low (A) A a= d, b, # n a = 4)所以在I。、I：中的移进-归约冲突可以由Follow集解决，所以G是SLR(l)文法。构造的SLR(l)分析表如下：题目1的SLR分析表状态(State)ActionGotoadbA0S2r3r3r311acc2S2r3r3r333S4S54rlrlrl5r2r2r2对输入串ab#的分析过程状态栈(state stack)文法符号栈剩余输入串(input left)动作(action)Dabf#移进h b5归约Avp 2 3#aAb#移:递b 2 3 5(laAb归纟勺A -*aAbhtt成功10.判断下列各题所示文法是否为L
3、 R类方法，若是请说明是LR(0),SLR，LALR( 1)或LR 的哪一种，并构造相应的分析表，若不是谙说明理由.(3 ) S-aAd eBd aBr eArA-aB-a答案：1)列岀扩展文法G的产生式列表：(O)S -s(1)S-aAd(2)S-eBd(3)S-aBr(4)S-eAr(5)A-a(6)B-a2)G的LR(O)项目集族及识别活前缀的DFA如下图所示：从上图中看出项目集16中存在归约-归约冲突，所以该文法不是LR(O)文法。下面判断是否为SLR(l)文法：Follow(S) = #Follow(A) = d, rFollow(B) = d, r对于16, Follow (A)
4、A Follow (B)= d, r不为d 所以项目集16中的归约-归约冲突不能 消除，该文法不是SLR(l)文法。下面判断是否为1R)文法，在上面的项目集规范族中加入搜索符：但若合并同心项目集16和113,则归约-归约冲突又会重现，因此该文法不是LALR(l)文法。3)LRG)分析表ActionGotoStatea e d r #SAB0S2 S311acc2S64 53S138 74S95S106R5 R67Sil8S129R110R311R212R113R6 R511.设文法GS为：S-AS eA-aA:b(1)证明GS是LR1文法;扩展文法G为：(0)S -S(1)S-AS(2)S-e
5、(3)A-aA(4)A-bG，的LR项目集族及识別活前缀的DFA如下图所示:S10:S -#A11:S -S，#S-.#A12:A- aA, a/b/#才川 J?A-b, a/b/#S-. AS, #1as-., #bA-. aA, a/b/#14:A- b,a/b/#A-b. , a/b/#b 1，aS15:S-AS., #b13:A-a. A, a/b/ttA-. aA, a/b/#b, a/b/#16:A-aA., a/b/#从上图中可以看出，每个项目集中均无移进-归约冲突和归约-归约冲突，所以该文法为LR(1) 文法。(2)构造它的LR(1)分析表;ActionGotoStatea b
6、 r；S A0S3 S4 R21 21acc2S3 S4 R25 23S3 S464R1 R1 R15R16 | R3 R3 R3 | (3) 给出输入符号串abab#的分析过程。序号状态栈符号栈输入缓冲区动作10#abab#S3,移进203beb#S4,移进3034ab#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#Rl,归约 S-AS1201#S#acc成
7、功15.已知文法为：S-a A (T)T-T, S | S(1)构造它的LR(0), LALR(l), LR分析表; 扩展文法G为：(0)S -s(1)S-a(2)S-A(3)S- (T)(4)T-T, S(5)T-Sl)LR(O)项目集族及识别活前缀的DFA如下图所示:ActionGotoStateaA()9S T0S2S3S411acc2R1R1R1R1R1R13R2R2R2R2R2R24S2S3S46 55S7S86R5R5R5R5R5R57R3R3R3R3R3R38S2S3S499R4R4R4R4R4R12) LR项目集族及识别活前缀的DFA如下图所示:图中为文法符号。说明：对于14中
8、的项目T-.T,S和T-.S,先由项目S-X.T),#推出扩展项目的搜索符为 )”，再由T-. T, S,)扩展出新的搜索符“，”，合并后的搜索符为”。LR分析表:ActionGotoStatea A ( ) , #S T0S2 S3 S411acc2R13R24S7 S8 S96 55S10 S116R5 R57R1 R18R2 R29S7 S8 S96 1210R311S7 S8 S91312S14 S1113R4 R414R3 R3LALR(l)分析表需将上面DFA中的同心项目(同底色)的项目集合并后考虑，将状态数大的 合并入状态数小的项目集中，在此不再另画图。LALR(l)分析表:Ac
9、tionGotoStateaA()9#S T0S2S3S411acc2R1R1R13R2R2R24S2S3S46 55S10Sil6R5R510R3R3R311S2S3S41313R4R4(2)给出对输入符号串(a#和6甜的分析过程;1)对输入符号串(a#的分析过程 用LR(O)分析表序号状态 栈符号栈输入缓冲区动作10#S4,移进204#(S2,移进3042#(a#R1,归约 S-a4046#(SR5,归约 T-S5045#(T出错用LR分析表序号状态栈符号栈输入缓冲区动作10#(a#S4,移进204#(a#S7,移进3047#(a#错误用LALR( 1)分析表序号状态栈符号栈输入缓冲区动作
10、10(a#S4,移进204#(a#S2,移进3042#(a#R1,归约 S-a4046#(S#错误2)对输入符号串(务胡的分析过程 用LR(O)分析表序号状态栈符号栈输入缓冲区动作10(a, a#S4,移进204#(a, a#S2,移进3042#(a,a#Rl,归约 S-a4046#(S,a#R5,归约 T-S5045#(T,a#s&移进60458#(T,a#S2,移进704582#Rl,归约 S-a804589#(T,S#R4,归约 T-T, S9045#(T#出错用LR(1)分析表序号状态栈符号栈输入缓冲区动作10(a, a#S4,移进204#(a, a#S7,移进3047Rl,归约 S-
11、a4046#(SR5,归约 T-S5045#(TSil,移进6045(11)#(T,a#S7,移进7045(11)7#(T,a#出错用LALR( 1)分析表序号状态栈符号栈输入缓冲区动作10#(a, a#S4,移进204#(a, a#S2,移进3042d#Rl,归约 S-a4046#(SR5,归约 T-S5045#(TSil,移进6045(11)#(T,a#S2,移进7045(11)2#Rl,归约 S-a8045(11) (13)#(T,S#出错说明(1)中三种分析表发现错误的时刻和输入串的岀错位置有何区别“ 见(2),由此二例说明，对于错误分析，LR(1)的效率最髙，LALR(l)次之，LR
12、(O)最差。 补充题：GS文法如下，求其LR分析表1.S-AaDC2.C*Cba3 C-*ba4.D-A5.D-*Ba6 A-*b7. B-b答：扩展文法G为：0. S -s1.S-AaDC2.C-*Cbe3 C-*ba4.D-A5.D-*Ba6 A-*b7. B-b答：1)首先判断是否为LR(0)方法：由上图中可以看到18中存在归约-归约冲突，19中存在移进-归约冲突，所以该文法不是LR(0)文法2)再判断是否为SLR(l)文法：Follow (S) = #Follow(A) = a, bFollow (B) = aFollow(C) = b, #Follow (D) = b2对于18, Follow (A) nFollow(B) = a,不为空,因此该文法不是SLR(l)文法。3)判断是否为LR文法:由上图可看出原先I& 19存在的冲突已消除，所以为LR(1)文法。LR分析表：ActionGotoStateb b #S A B C D0S31 21acc2SI3R64SS6 7 55S10967Sil8R7 R69S12 R110S1411R512S1313R2 R214R3 R3
