第７章 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 如下图所示： S d I0: I1: I4: I9: A S＇->.S S＇->S. S->aA.d S->aAd. S->.aAd B a I2: I5: I10: S->.eBd r S->a.Ad S->aB.r S->aBrd. S->.aBr S->a.Br S->.eAr I6: a A->.a e A->a. B->.a B->a. I3: a S->e.Bd d S->e.Ar I7: B I11: B->.a S->eB.d S->eBd. A A->.a r I8: I12: S->eA.r S->eAr.
从上图中看出项目集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)文法，在上面的项目集规范族中加入搜索符： S I0: d I1: I4: I9: S＇->.S,# S＇->S.,# A S->aA.d,# S->aAd.,# S->.aAd,# B S->.eBd,# a I2: I5: I10: r S->.aBr,# S->a.Ad,# S->aB.r,# S->aBr.,# S->.eAr,# S->a.Br,# I6: a A->.a,d e A->a.,d B->.a,r B->a.,r I3: S->e.Bd,# d I11: I7: S->e.Ar,# B S->eBd.,# S->eB.d,# B->.a,d A A->.a,r r I12: I8: a S->eAr. ,# S->eA.r,# I13: B->a.,d A->a.,r 从上图可以看出原来存的的归约-归约冲突已经消除，所以该文法为LR(1)文法。 但若合并同心项目集I6和I13，则归约-归约冲突又会重现，因此该文法不是LALR(1)文法。 3)LR(1)分析表 State 0 1 2 3 4 5 6 7 8 9 Action a e d r # S2 S3 acc S6 S13 S9 S10 R5 R6 S11 S12 R1 Goto S A B 1 4 5 8 7 10 11 12 13 R3 R2 R4 R6 R5
11.设文法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 如下图所示： S I0: I1:
A S’->.S,# S’->S.,#
S->.AS,#
I2: S->.,# A
A->.aA,a/b/# S->A.S,#
S I5: A->.b, a/b/# S->.AS,#
S->AS.,# S->.,# a b A->.aA,a/b/#
A->.b, a/b/# I4: b A->b., a/b/# a
I3: b A I6: A->a.A,a/b/# A->aA.,a/b/# A->.aA,a/b/#
a A->.b, a/b/#
从上图中可以看出，每个项目集中均无移进-归约冲突和归约-归约冲突，所以该文法为LR(1)文法。
（2） 构造它的LR(1)分析表;
State 0 1 2 3 4 5 Action a b # S3 S4 R2 acc S3 S4 R2 S3 S4 R4 R4 R4 R1 Goto S A 1 2 5 2 6 6 R3 R3 R3 （3） 给出输入符号串abab#的分析过程。 序号 状态栈 符号栈 输入缓冲区 动作 1 0 # abab# S3,移进 2 03 #a bab# S4,移进 3 034 #ab ab# R4,归约 A->b 4 036 #aA ab# R3,归约 A->aA 5 02 #A ab# S3,移进 6 023 #Aa b# S4,移进 7 0234 #Aab # R4,归约 A->b 8 0236 #AaA # R3,归约 A->aA 9 022 #AA # R2,归约 S->ε 10 0225 #AAS # R1,归约 S->AS 11 025 #AS # R1,归约 S->AS 12 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->S
1)LR(0)项目集族及识别活前缀的DFA 如下图所示： S I0: I1: S’->.S S’->S. S->.a a I2: S->.∧ S->a. S->.(T) a a ( ( ∧ I3: I8: ∧ S->∧. T->T, .S I4: ∧ ( S->.a S->(.T) S->.∧ T->.T,S I5: T , S->.(T) T->.S S->(T.) S S->.a T->T.,S S->.∧ I9: ) S->.(T) LR(0)分析表: T->T, S. I7: S S->(T). I6: T->S.,