6.4 LR(1)和 LALR(1)分析规范 LR分析例 1文法 G 0） S`→S (1) S→aAd (2) S→bAc
(3) S→aec (4) S→bed (5) A→e
I0,S`→,S I1,S`→S,I2,S→a,Ad
S→,aAd S→a,ec
S→,bAc A→,e
S→,aec
S→,bed
I3,S→b,Ac I4,I5,
S→b,ed S→aA,d S→ae,c
A→,e A→e,
I6,I7,I8:
S→bA,c S→be,d S→aAd,
A→e,
I9,S→aec,I10,S→bAc,I11,S→bed,
ACTION GOTO
a c e b d # S A
0 S2 S3 1
1 acc
2 S5 4
3 S7 6
4 S8
5 r5 r5S9 r5 r5 r5 r5
6 S10
7 r7 r7 r7 r7 r7 S11 r7
8 r1 r1 r1 r1 r1 r1
9 r3 r3 r3 r3 r3 r3
10 r2 r2 r2 r2 r2 r2
11 r4 r4 r4 r4 r4 r4
( 0） S’→S (1) S→aAd (2) S→bAc
(3) S→aec (4) S→bed (5) A→e
非 LR(0),非 SLR(1)
I5,S→ae,c I7,S→be,d
A→e,A→e,
S’==>S==>aAd==>aed S’==>S==>bAc==>bec
S’==>S==>aec S’==>S==>bed
ae是 活前缀 be是 活前缀
aAc不是规范句型,bAd不是规范句型不作无效归约？ 信息－ 在特定的规范推导中,哪些输入符号能跟在句柄之后
G[S]:
若 S => α Aω =>α β ω r是 αβ的前缀，则称 r是 G的一个活前缀,哪个项目在什么条件下对某个活前缀有效
RRR
R R
R R R
R R
R R
* *
*
* *
例 2 G[S]:
(0) S`→ S (1) S→L=R (2) S→R
(3) L→ *R (4) L→id (5) R→L
I0,S' –>?S
S –>?L = R
S –>?R
R –>?L
L –>?id
L –>?*R
I1,S' –> S?
I2,S –> L? = R
R –> L?
I3,S –> R?
I4,L –> *?R
R –>?L
L –>?*R
L –>?id
I5,L –> id?
I6,S –> L =?R
R –>?L
L –>?*R
L –>?id
I7,L –> *R?
I8,R –> L?
I9,S –> L=R?
I2,S –> L? = R
R –> L?
考虑分析表达式 id = id时，在工作到 I2 处已经把第一个 id 归约到 L了,看到下一个输入 =
要作决策，第一个项目要设置 Action[2,=] 为
S6,即把赋值的其它部分找到,但 =也是属于
Follow(R) 的,第二个项目要用 R–>L归约,出现 shift-reduce 冲突,
若将栈顶的符号序列归约到 R,会有问题！因为不可能有规范句型以 R = … 开头 (有以 *R
=,.,开头的 规范句型 ).
SLR（ 1）的局限
follow 集包含了在任何句型中跟在 R 后的符号但没有严格地指出在一个特定的推导里哪些符号跟在
R后,所以需要扩充状态以包含更多的信息,follow
集的哪些部分 才是进到该状态最恰当的归约依据,
处在状态 2时，试图构建句子有两条路：
1.S?L = R 或
2.S? R? L,
如下一符号是 =,那就不能用第二个选择，必须用第一个,即移进,只有下一个符号是 #时才能归约,尽管 = 属于 Follow(R),那是因为一个 R 可以出现在别的上下文中，在现在这个特定的情况，它不合适,因为在用 S? R? L推导句子时,= 不能跟在 R后,
.
讨论例 2后有以下结果：
不是 LR(0)文法
∵ I2 S→L,=R R→L,中存在移进 /
归约冲突
SLR能否 解决 I2中的冲突
∴ FOLLOW（ R） ={#,=}与 {=}交不为空 不是 SLR（ 1）文法
如 早 有 信息 告知,若用 R→L 归约 则形成 R=… 而 R=不是活前缀,
SLR（ 1）的局限在 SLR 分析中,若项目集 Ik含有项目 A→?.
,那么在相应的状态下,只要当前输入符号 a?follow(A) 集,就确定采用 A→?进行归约,但在某些情况下,当状态 k呈现于栈顶时,栈内的串所构成的活前缀未必允许把?归约为 A,.因为可能没有一个规范句型含有前缀?Aa.即在这种情况下,用 A
→?归约未必有效,
.所以需要扩充状态以包含更多的信息,follow 集的哪些部分才是进到该状态最恰当的归约依据,
重新定义项目,
LR（ 1）方法若 A,B I
则 B?, I
（ B 是一产生式）
把 FIRST（?）中的符号作为用 B 归约的搜索符,向前搜索符,
LR（ 1）项目 ( 配置）的一般形式
– [ A,?,a ]
a 称作该 项目 ( 配置） 的向前搜索符（ lookahead ）
向前搜索符（ lookahead ）只对圆点在最后的项目起作用
A –>,a
.意味着处在栈中是的相应状态，但 只有当下一个输入符是 a时才能进行归约,a 是一个终结符，或是输入结束标记 #
有多个 向前搜索符，比如 a,b,c时，可写作 A –> u?,
a/b/c
LR(0)项目对某个活前缀有效定义项目 A→ β 1.β 2对活前缀 r=αβ1是有效的,如果存在一个规范推导 S => α Aω =>αβ1β 2 ω
若项目 A→ α,Bβ 对活前缀 r=?α 是有效的且 B→?是一个产生式,则项目 B→,?对 r=?α 也是有效的,
因为由假定,存在一个规范推导
S =>? Aω =>?α Bβω
设 βω =>?ω,则对 B→?有 规范推导
S =>? Aω=>?α Bβω=>?α B? ω =>?αω
于是项目 B→,?对 r=?α 也是有效的
R
*
R
*
R
*
R
*
R
*
LR(1)项目对某个活前缀有效定义一个 LR(1)项目 [A→ α,β,a]对活前缀 r=?α 是有效的,如果存在一个规范推导 S =>? Aω
=>? α β ω
其中或 ω的第一个符号为 a,或 ω=?而 a为 #
若 LR(1)项目 [A→ α,Bβ,a]对活前缀 r=?α 是有效的且 B→?是一个产生式,则项目 [B→,?,b]
对 r=?α 也是有效的,其中 b或者是从 β 推出的第一个终结符,或者 β =>?而 b=a,两者结合在一起,即,b? FIRST(β a)
R
*
*
构造 LR(1)项目集 规范族和 G0函数
closure(I)按如下方式构造
(1) I的任何项目属 closure(I)；
(2)若 [A→ β 1,Bβ 2,a]∈ closure(I),B→ δ 是一产生式，那么对于 FIRST(β 2a)中的每个终结符 b，如果 [B→,δ,b]不在
closure(I)中，则把它加进去；
(3)重复（ 1）（ 2），直至 closure(I)不再增大。
GO函数：
若 I是一个项目集,X是一个文法符号
GO(I,X)= closure(J)
其中 J={ 任何形如 [A→ α X,β,a]的项目 ∣ [A→ α,Xβ,a]∈I}
LR(I)项目规范族 C的构造算法类同 LR(0)的，只是初始时：
C={ closure({[S’→,S,#]})};
例 1的 LR(1)项目集规范族
I0,S`→,S,# I5,S →ae,c,#
S →,aAd,# A →e,,d
S →,bAc,# I6,S →bA,c,#
S →,aec,# I7,S →be,d,#
S →,bed,# A →e,,c
I1,S`→S,,# I8,S →aAd,,#
I2,S →a,Ad,# I9,S →aec,,#
S →a,ec,# I10,S →bAc,,#
A →,e,d I11,S →bed,,#
I3,S →b,Ac,#
S →b,ed,#
A→,e,c
I4,S→aA,d,#
规范的 LR(1)分析表的构造假定 LR(1)项目集规范族 C={I0,I1,……,In},令每个项目集 Ik的下标 k 为分析器的一个状态,G’的 LR（ 1） 分析表含有状态 0,1,……,n。
1.令那个含有项目 [S’→,S,#]的 Ik的下标 k为状态 0（ 初态 ）,ACTION表和 GOTO表可按如下方法构造
2.若项目 [A→ α,,b]属于 Ik,那么 置 ACTION[k,b]为,用产生式 A→ α 进行规约,,简记为,rj”;(假定 A→ α 为文法 G’的第 j个产生式 )
3.若项目 [A→ α,aβ,b]属于 Ik且 GO (Ik,a)= Ij,则置 ACTION[k,a]为,把状态 j和符号 a移进栈,,简记为,sj”;
4.若项目 [S’→S,,#]属于 Ik,则置 ACTION[k,#]为,接受,,简记为,acc”;
5.若 GO (Ik,A)= Ij,A为非终结符,则置 GOTO(k,A)=j;
分析表中凡不能用规则 1至 5填入信息的空白格均置上,出错标志,。
按上述算法构造的含有 ACTION和 GOTO两部分的分析表,如果每个入口不含多重定义,则称它为文法 G的一张 规范的 LR(1)分析 表 。 具有 规范的 LR(1)
表的文法 G称为一个 LR（ 1） 文法 。
LR(1) 文法满足下面两个条件
1.如果一个项目集里有项目 [A –> u?xv,a],
x是终结符，那就不会有项目 [B –> u?,x]
2.项目集里所有归约项目 的向前搜索符不相交，即不能同时含有项目
[A –> u?,a] 和 [B –> v?,a]
LR（ K）分析
LR（ K）项目
– [ A,?,a1 a2 …… a K ]
a1 a2 …… a K 向前搜索符串移进项目 [ A,a?,a1 a2 …… a K ]
待约项目 [ A,B?,a1 a2 …… a K ]
归约项目 [ A.,a1 a2 …… a K ]
LR(1)比 SLR（ 1）能力强例 2
(0) S`→ S
(1)S→L=R
(2)S→R
(3)L→ *R
(4)L→id
(5)R→L
不能用 SLR（ 1） 技术解决,但能用 LR（ 1）
I1:S’?S?,#
I5:L?i?,=/#
I7:L?*R?,=/#
I8:R?L?,=/#
I9:S?L=R?,#
I3:S?R?,#
I12:L?i?,# I10:R?L?,#
I13:L?*R?,#
I0:S’S,#
SL=R,#
SR,#
L*R,=/#
Li,=/#
RL,# I4,L? *?R,=/#
RL,=/#
Li,=/#
L*R,=/#
I6:S?L=?R,#
RL,#
L*R,#
Li,#
I11:L?*?R,#
RL,#
L*R,#
Li,#
I2:S?L?=R,#
R? L?,#
s
R
=
L
R
i i
*
i
i
R
L
L
R L
*
*
*
例 2的 LR(1)项目集及转换函数每个 SLR（ 1）文法都是 LR（ 1）的，一个 SLR
（ 1）文法的规范 LR分析器比其 SLR（ 1）分析器的状态要多。
例 G(S):S? BB B?aB B?b
I0:S’?.S S?.BB B?.aB B?.b
I1:S’?S.
I2:S?B.B B?.aB B?.b
I3:B?a.B B?.aB B?.b
I4:B?aB,
I5,B?b.
I6,S?BB.
I0:S’S,#
SBB,#
BaB,a/b
Bb,a/b
I1:S’?S?,#
I2:S?B?B,#
BaB,#
Bb,#
I5:S?BB?,#
I6:B?a?B,#
BaB,#
Bb,# I
3:B?a?B,a/b
BaB,a/b
Bb,a/b
I4:B?b?,a/b
I7:B?b?,#
I9:B?aB?,#
I8:B?aB?,a/b
s
B B
a
b
b
b
B
B
a
a
a
LR(1)项目集规范族和转换函数
b
LALR—在 SLR（ 1）和 LR（ 1）间寻找折衷办法
（状态数目，分析能力）
LALR (lookahead LR)
合并 LR（ 1） 项目集规范族的 同心集 I36 I47
I89（除搜索符外两个集合是相同的）,
I3:B?a?B,a/b
BaB,a/b
Bb,a/b
I6:B?a?B,#
BaB,#
Bb,#
I4:B?b?,a/b
I7:B?b?,#
I8:B?aB?,a/b
I9:B?aB?,#
构造 LALR(1)分析表,
方法 1--“brute-force”
1.构造文法 G的规范 LR(1) 状态,
2.合并同心集的状态,
3.新 LALR(1) 状态的 GO函数是合并的同心集状态的 GO函数的并,
4,LALR(1)分析表 的 ACTION 和 GOTO 登录方法与 LR(1)分析表一样,
经上述步骤构造的表若不存在冲突，则称它为 G的 LALR(1)分析表。
存在这种分析表的文法称为 LALR（ 1）文法。
ACTION GOTO
a b # S B
状态
0 S3 S4 1 2
1 acc
2 S6 S7 5
3 S3 S4 8
4 r3 r3
5 r1
6 S6 S7 9
7 r3
8 r2 r2
9 r2
LR(1)分析表
0 S3,6 S4,7 1 2
1 acc
2 S3,6 S4,7 5
3,6 S3,6 S4,7
8,9
4,7 r3 r3 r3
5 r1
8,9 r2 r2 r2
a b # S B
ACTION GOTO状态
LALR(1)分析表对 输入串 ab#用 LR(1)分析的过程
1 0 # ab# S3
2 03 #a b# S4
3 034 #ab # 出错步骤 状态栈 符号栈 输入串 ACTION GOTO
对输入串 ab#用 LALR(1)分析的过程
1 0 # ab# S3,6
2 0(3,6) #a b# S4,7
3 0(3,6)(4,7) #ab # r3 (8,9)
4 0(3,6)(8,9) #aB # r2 2
5 02 #B # 出错步骤 状态栈 符号栈 输入串 ACTION GOTO
讨论,
LR（ 1）项目集不存在动作冲突，合并同心集后会不会产生新的冲突（移进 -归约，
归约 -归约）
不会产生新的移进 -归约冲突（讨论见讲义）
会产生新的归约 -归约冲突
LR（ 1）项目集不存在动作冲突，合并同心集后会不会产生新的冲突（移进 -归约，
归约 -归约）
例
S' –> S
S –> aBc | bCc | aCd | bBd
B –> e
C –> e
LR(1) 项目集规范族,
I0,S' –>?S,#
S –>?aBc,#
S –>?bCc,#
S –>?aCd,#
S –>?bBd,#
I1,S' –> S?,#
I2,S –> a?Bc,#
S –> a?Cd,#
B –>?e,c
C –>?e,d
I3,S –> b?Cc,#
S –> b?Bd,#
C –>?e,c
B –>?e,d
I4,S –> aB?c,#
I5,S –> aC?d,#
I6,B –> e?,c
C –> e?,d
I7,S –> bC?c,#
I8,S –> bB?d,#
I9,B –> e?,d
C –> e?,c
I10,S –> aBc?,#
I11,S –> aCd?,#
I12,S –> bCc?,#
I13,S –> bBd?,#
I69,C –> e?,c/d
B –> e?,d/c
练习题
1.下列文法是 LR（ 0）吗？是 SLR（ 1）吗？
a)E –> E + T | T
T –> (E) | id | id[E]
b) S –> Ab | ABc
A –> aA | a
B –> b
2.为下列文法构造 LR（ 1）分析表，并分析串 baab.
0) S' –> S
1) S –> XX
2) X –> aX
3) X –> b
3.讲义 7.7练习 题 16,题 18
(3) S→aec (4) S→bed (5) A→e
I0,S`→,S I1,S`→S,I2,S→a,Ad
S→,aAd S→a,ec
S→,bAc A→,e
S→,aec
S→,bed
I3,S→b,Ac I4,I5,
S→b,ed S→aA,d S→ae,c
A→,e A→e,
I6,I7,I8:
S→bA,c S→be,d S→aAd,
A→e,
I9,S→aec,I10,S→bAc,I11,S→bed,
ACTION GOTO
a c e b d # S A
0 S2 S3 1
1 acc
2 S5 4
3 S7 6
4 S8
5 r5 r5S9 r5 r5 r5 r5
6 S10
7 r7 r7 r7 r7 r7 S11 r7
8 r1 r1 r1 r1 r1 r1
9 r3 r3 r3 r3 r3 r3
10 r2 r2 r2 r2 r2 r2
11 r4 r4 r4 r4 r4 r4
( 0） S’→S (1) S→aAd (2) S→bAc
(3) S→aec (4) S→bed (5) A→e
非 LR(0),非 SLR(1)
I5,S→ae,c I7,S→be,d
A→e,A→e,
S’==>S==>aAd==>aed S’==>S==>bAc==>bec
S’==>S==>aec S’==>S==>bed
ae是 活前缀 be是 活前缀
aAc不是规范句型,bAd不是规范句型不作无效归约？ 信息－ 在特定的规范推导中,哪些输入符号能跟在句柄之后
G[S]:
若 S => α Aω =>α β ω r是 αβ的前缀，则称 r是 G的一个活前缀,哪个项目在什么条件下对某个活前缀有效
RRR
R R
R R R
R R
R R
* *
*
* *
例 2 G[S]:
(0) S`→ S (1) S→L=R (2) S→R
(3) L→ *R (4) L→id (5) R→L
I0,S' –>?S
S –>?L = R
S –>?R
R –>?L
L –>?id
L –>?*R
I1,S' –> S?
I2,S –> L? = R
R –> L?
I3,S –> R?
I4,L –> *?R
R –>?L
L –>?*R
L –>?id
I5,L –> id?
I6,S –> L =?R
R –>?L
L –>?*R
L –>?id
I7,L –> *R?
I8,R –> L?
I9,S –> L=R?
I2,S –> L? = R
R –> L?
考虑分析表达式 id = id时，在工作到 I2 处已经把第一个 id 归约到 L了,看到下一个输入 =
要作决策，第一个项目要设置 Action[2,=] 为
S6,即把赋值的其它部分找到,但 =也是属于
Follow(R) 的,第二个项目要用 R–>L归约,出现 shift-reduce 冲突,
若将栈顶的符号序列归约到 R,会有问题！因为不可能有规范句型以 R = … 开头 (有以 *R
=,.,开头的 规范句型 ).
SLR（ 1）的局限
follow 集包含了在任何句型中跟在 R 后的符号但没有严格地指出在一个特定的推导里哪些符号跟在
R后,所以需要扩充状态以包含更多的信息,follow
集的哪些部分 才是进到该状态最恰当的归约依据,
处在状态 2时，试图构建句子有两条路：
1.S?L = R 或
2.S? R? L,
如下一符号是 =,那就不能用第二个选择，必须用第一个,即移进,只有下一个符号是 #时才能归约,尽管 = 属于 Follow(R),那是因为一个 R 可以出现在别的上下文中，在现在这个特定的情况，它不合适,因为在用 S? R? L推导句子时,= 不能跟在 R后,
.
讨论例 2后有以下结果：
不是 LR(0)文法
∵ I2 S→L,=R R→L,中存在移进 /
归约冲突
SLR能否 解决 I2中的冲突
∴ FOLLOW（ R） ={#,=}与 {=}交不为空 不是 SLR（ 1）文法
如 早 有 信息 告知,若用 R→L 归约 则形成 R=… 而 R=不是活前缀,
SLR（ 1）的局限在 SLR 分析中,若项目集 Ik含有项目 A→?.
,那么在相应的状态下,只要当前输入符号 a?follow(A) 集,就确定采用 A→?进行归约,但在某些情况下,当状态 k呈现于栈顶时,栈内的串所构成的活前缀未必允许把?归约为 A,.因为可能没有一个规范句型含有前缀?Aa.即在这种情况下,用 A
→?归约未必有效,
.所以需要扩充状态以包含更多的信息,follow 集的哪些部分才是进到该状态最恰当的归约依据,
重新定义项目,
LR（ 1）方法若 A,B I
则 B?, I
（ B 是一产生式）
把 FIRST（?）中的符号作为用 B 归约的搜索符,向前搜索符,
LR（ 1）项目 ( 配置）的一般形式
– [ A,?,a ]
a 称作该 项目 ( 配置） 的向前搜索符（ lookahead ）
向前搜索符（ lookahead ）只对圆点在最后的项目起作用
A –>,a
.意味着处在栈中是的相应状态，但 只有当下一个输入符是 a时才能进行归约,a 是一个终结符，或是输入结束标记 #
有多个 向前搜索符，比如 a,b,c时，可写作 A –> u?,
a/b/c
LR(0)项目对某个活前缀有效定义项目 A→ β 1.β 2对活前缀 r=αβ1是有效的,如果存在一个规范推导 S => α Aω =>αβ1β 2 ω
若项目 A→ α,Bβ 对活前缀 r=?α 是有效的且 B→?是一个产生式,则项目 B→,?对 r=?α 也是有效的,
因为由假定,存在一个规范推导
S =>? Aω =>?α Bβω
设 βω =>?ω,则对 B→?有 规范推导
S =>? Aω=>?α Bβω=>?α B? ω =>?αω
于是项目 B→,?对 r=?α 也是有效的
R
*
R
*
R
*
R
*
R
*
LR(1)项目对某个活前缀有效定义一个 LR(1)项目 [A→ α,β,a]对活前缀 r=?α 是有效的,如果存在一个规范推导 S =>? Aω
=>? α β ω
其中或 ω的第一个符号为 a,或 ω=?而 a为 #
若 LR(1)项目 [A→ α,Bβ,a]对活前缀 r=?α 是有效的且 B→?是一个产生式,则项目 [B→,?,b]
对 r=?α 也是有效的,其中 b或者是从 β 推出的第一个终结符,或者 β =>?而 b=a,两者结合在一起,即,b? FIRST(β a)
R
*
*
构造 LR(1)项目集 规范族和 G0函数
closure(I)按如下方式构造
(1) I的任何项目属 closure(I)；
(2)若 [A→ β 1,Bβ 2,a]∈ closure(I),B→ δ 是一产生式，那么对于 FIRST(β 2a)中的每个终结符 b，如果 [B→,δ,b]不在
closure(I)中，则把它加进去；
(3)重复（ 1）（ 2），直至 closure(I)不再增大。
GO函数：
若 I是一个项目集,X是一个文法符号
GO(I,X)= closure(J)
其中 J={ 任何形如 [A→ α X,β,a]的项目 ∣ [A→ α,Xβ,a]∈I}
LR(I)项目规范族 C的构造算法类同 LR(0)的，只是初始时：
C={ closure({[S’→,S,#]})};
例 1的 LR(1)项目集规范族
I0,S`→,S,# I5,S →ae,c,#
S →,aAd,# A →e,,d
S →,bAc,# I6,S →bA,c,#
S →,aec,# I7,S →be,d,#
S →,bed,# A →e,,c
I1,S`→S,,# I8,S →aAd,,#
I2,S →a,Ad,# I9,S →aec,,#
S →a,ec,# I10,S →bAc,,#
A →,e,d I11,S →bed,,#
I3,S →b,Ac,#
S →b,ed,#
A→,e,c
I4,S→aA,d,#
规范的 LR(1)分析表的构造假定 LR(1)项目集规范族 C={I0,I1,……,In},令每个项目集 Ik的下标 k 为分析器的一个状态,G’的 LR（ 1） 分析表含有状态 0,1,……,n。
1.令那个含有项目 [S’→,S,#]的 Ik的下标 k为状态 0（ 初态 ）,ACTION表和 GOTO表可按如下方法构造
2.若项目 [A→ α,,b]属于 Ik,那么 置 ACTION[k,b]为,用产生式 A→ α 进行规约,,简记为,rj”;(假定 A→ α 为文法 G’的第 j个产生式 )
3.若项目 [A→ α,aβ,b]属于 Ik且 GO (Ik,a)= Ij,则置 ACTION[k,a]为,把状态 j和符号 a移进栈,,简记为,sj”;
4.若项目 [S’→S,,#]属于 Ik,则置 ACTION[k,#]为,接受,,简记为,acc”;
5.若 GO (Ik,A)= Ij,A为非终结符,则置 GOTO(k,A)=j;
分析表中凡不能用规则 1至 5填入信息的空白格均置上,出错标志,。
按上述算法构造的含有 ACTION和 GOTO两部分的分析表,如果每个入口不含多重定义,则称它为文法 G的一张 规范的 LR(1)分析 表 。 具有 规范的 LR(1)
表的文法 G称为一个 LR（ 1） 文法 。
LR(1) 文法满足下面两个条件
1.如果一个项目集里有项目 [A –> u?xv,a],
x是终结符，那就不会有项目 [B –> u?,x]
2.项目集里所有归约项目 的向前搜索符不相交，即不能同时含有项目
[A –> u?,a] 和 [B –> v?,a]
LR（ K）分析
LR（ K）项目
– [ A,?,a1 a2 …… a K ]
a1 a2 …… a K 向前搜索符串移进项目 [ A,a?,a1 a2 …… a K ]
待约项目 [ A,B?,a1 a2 …… a K ]
归约项目 [ A.,a1 a2 …… a K ]
LR(1)比 SLR（ 1）能力强例 2
(0) S`→ S
(1)S→L=R
(2)S→R
(3)L→ *R
(4)L→id
(5)R→L
不能用 SLR（ 1） 技术解决,但能用 LR（ 1）
I1:S’?S?,#
I5:L?i?,=/#
I7:L?*R?,=/#
I8:R?L?,=/#
I9:S?L=R?,#
I3:S?R?,#
I12:L?i?,# I10:R?L?,#
I13:L?*R?,#
I0:S’S,#
SL=R,#
SR,#
L*R,=/#
Li,=/#
RL,# I4,L? *?R,=/#
RL,=/#
Li,=/#
L*R,=/#
I6:S?L=?R,#
RL,#
L*R,#
Li,#
I11:L?*?R,#
RL,#
L*R,#
Li,#
I2:S?L?=R,#
R? L?,#
s
R
=
L
R
i i
*
i
i
R
L
L
R L
*
*
*
例 2的 LR(1)项目集及转换函数每个 SLR（ 1）文法都是 LR（ 1）的，一个 SLR
（ 1）文法的规范 LR分析器比其 SLR（ 1）分析器的状态要多。
例 G(S):S? BB B?aB B?b
I0:S’?.S S?.BB B?.aB B?.b
I1:S’?S.
I2:S?B.B B?.aB B?.b
I3:B?a.B B?.aB B?.b
I4:B?aB,
I5,B?b.
I6,S?BB.
I0:S’S,#
SBB,#
BaB,a/b
Bb,a/b
I1:S’?S?,#
I2:S?B?B,#
BaB,#
Bb,#
I5:S?BB?,#
I6:B?a?B,#
BaB,#
Bb,# I
3:B?a?B,a/b
BaB,a/b
Bb,a/b
I4:B?b?,a/b
I7:B?b?,#
I9:B?aB?,#
I8:B?aB?,a/b
s
B B
a
b
b
b
B
B
a
a
a
LR(1)项目集规范族和转换函数
b
LALR—在 SLR（ 1）和 LR（ 1）间寻找折衷办法
（状态数目，分析能力）
LALR (lookahead LR)
合并 LR（ 1） 项目集规范族的 同心集 I36 I47
I89（除搜索符外两个集合是相同的）,
I3:B?a?B,a/b
BaB,a/b
Bb,a/b
I6:B?a?B,#
BaB,#
Bb,#
I4:B?b?,a/b
I7:B?b?,#
I8:B?aB?,a/b
I9:B?aB?,#
构造 LALR(1)分析表,
方法 1--“brute-force”
1.构造文法 G的规范 LR(1) 状态,
2.合并同心集的状态,
3.新 LALR(1) 状态的 GO函数是合并的同心集状态的 GO函数的并,
4,LALR(1)分析表 的 ACTION 和 GOTO 登录方法与 LR(1)分析表一样,
经上述步骤构造的表若不存在冲突，则称它为 G的 LALR(1)分析表。
存在这种分析表的文法称为 LALR（ 1）文法。
ACTION GOTO
a b # S B
状态
0 S3 S4 1 2
1 acc
2 S6 S7 5
3 S3 S4 8
4 r3 r3
5 r1
6 S6 S7 9
7 r3
8 r2 r2
9 r2
LR(1)分析表
0 S3,6 S4,7 1 2
1 acc
2 S3,6 S4,7 5
3,6 S3,6 S4,7
8,9
4,7 r3 r3 r3
5 r1
8,9 r2 r2 r2
a b # S B
ACTION GOTO状态
LALR(1)分析表对 输入串 ab#用 LR(1)分析的过程
1 0 # ab# S3
2 03 #a b# S4
3 034 #ab # 出错步骤 状态栈 符号栈 输入串 ACTION GOTO
对输入串 ab#用 LALR(1)分析的过程
1 0 # ab# S3,6
2 0(3,6) #a b# S4,7
3 0(3,6)(4,7) #ab # r3 (8,9)
4 0(3,6)(8,9) #aB # r2 2
5 02 #B # 出错步骤 状态栈 符号栈 输入串 ACTION GOTO
讨论,
LR（ 1）项目集不存在动作冲突，合并同心集后会不会产生新的冲突（移进 -归约，
归约 -归约）
不会产生新的移进 -归约冲突（讨论见讲义）
会产生新的归约 -归约冲突
LR（ 1）项目集不存在动作冲突，合并同心集后会不会产生新的冲突（移进 -归约，
归约 -归约）
例
S' –> S
S –> aBc | bCc | aCd | bBd
B –> e
C –> e
LR(1) 项目集规范族,
I0,S' –>?S,#
S –>?aBc,#
S –>?bCc,#
S –>?aCd,#
S –>?bBd,#
I1,S' –> S?,#
I2,S –> a?Bc,#
S –> a?Cd,#
B –>?e,c
C –>?e,d
I3,S –> b?Cc,#
S –> b?Bd,#
C –>?e,c
B –>?e,d
I4,S –> aB?c,#
I5,S –> aC?d,#
I6,B –> e?,c
C –> e?,d
I7,S –> bC?c,#
I8,S –> bB?d,#
I9,B –> e?,d
C –> e?,c
I10,S –> aBc?,#
I11,S –> aCd?,#
I12,S –> bCc?,#
I13,S –> bBd?,#
I69,C –> e?,c/d
B –> e?,d/c
练习题
1.下列文法是 LR（ 0）吗？是 SLR（ 1）吗？
a)E –> E + T | T
T –> (E) | id | id[E]
b) S –> Ab | ABc
A –> aA | a
B –> b
2.为下列文法构造 LR（ 1）分析表，并分析串 baab.
0) S' –> S
1) S –> XX
2) X –> aX
3) X –> b
3.讲义 7.7练习 题 16,题 18
