第7章作业参考答案

第７章 LR 分析 1．已知文法A→aAd|aAb|ε 判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。 答案：文法：A→aAd|aAb|ε 拓广文法为G′，增加产生式S′→A 若产生式排序为： 0 S' →A 1 A →aAd 2 A →aAb 3 A →ε 由产生式知： 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|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->a 2） Ｇ＇的LR(0)项目集族及识别活前缀的DFA 如下图所示： B I0: S＇->.S S->.aAd S->.eBd S->.aBr S->.eAr I1: S＇->S. I2: S->a.Ad S->a.Br A->.a B->.a I3: S->e.Bd S->e.Ar B->.a A->.a S a e I4: S->aA.d I5: S->aB.r I6: A->a. B->a. A B a I7: S->eB.d I8: S->eA.r A a I9: S->aAd. d I10: S->aBrd. r I11: S->eBd. d I12: 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)分析表 Action Goto State a e d r # S A B 0 S2 S3 1 1 acc 2 S6 4 5 3 S13 8 7 4 S9 5 S10 6 R5 R6 7 S11 8 S12 9 R...