1
三,SLR(1)分析表的构造
?常见程序设计语言都不是 LR(0)的,所以 LR(0)分
析表实用性较差,
?例如,典型的分程序结构,
B’ →B B →bD;Se D →D;d|d S →s;S |s 不是
LR(0)文法,
?甚至常见的简单表达式文法 G[E]也不是 LR(0)文
法,
2
B’ →B B →bD;Se D →D;d|d S →s;S |s
3
? 不过,常见的程序设计语言相应的 LR(0)分析表冲突项目
较少,可以对分析表做一定的修改,消除,移进 -归约,或
,归约 -归约,冲突,
4
SLR(1)分析表的构造（续）
? 考虑 LR(0)分析表的造表算法 规则 (2),对于 Ii中 归约项目 A→ ?·,
不管下一输入符号是谁,均进行归约, 若 Ii中同时含有 B→ ?·b?
及 C→ ?· 两类项目时,上述填表方法必然得到冲突的分析表,
? 一般地,Ii={A1→ ?·a1?1,…,Am→ ?·am?m,B1→ ?·,…,Bn→ ?·}
? 如果能根据下一输入符号 a对上述冲突加以区分,则冲突可解决,
? 当集合 FOLLOW(Bk)(1≦ k≦ n)与 {a1,a2,…,am}两两互不相交时,
则可按下述方法解决冲突,
?a?VT?{#},
IF a?{a1,a2,…,am} THEN ACTION[i,a]=sj
ELSE IF a?FOLLOW(Bj) THEN ACTION[i,a]=rBj??
ELSE ACTION[i,a]=“ERR”
5
SLR(1)分析表的构造（续）
?上述方法就是 SLR(1) (Simple LR(1))规则,按照
SLR(1)规则,只须将 LR(0)分析表的填表 规则 (2)修
改为,
(2’) 若归约项目 A→ ??属于 Ii,且 A→ ?是 P中第 j产
生式,则对于 ?a?FOLLOW(A),置 ACTION[i,a]=rj
注,其它规则不变 !
?对于给定的文法 G,若其相应的 SLR(1)分析表无冲
突项,则称 G是 SLR(1)文法,
6
G[B]的 SLR(1)分析表
?例 分程序文法 G[B]中,I8={S?s?;S,S?s?}含有
冲突,但 FOLLOW(S)={e} ≠{;},故冲突可解决,
7
四,LR(1)分析表 的构造
? 尽管 SLR(1)分析表简单实用,但还不能解决所有问题 ;
? 例如,文法 S’→S S→CbBA A→Aab|ab B→C|Db
C→a D→a 相应的 DFA见下页。
– 其中项目集 I10={S→ CbBA·,A→A ·ab}中存在, 移进 -归约,
冲突,由 FOLLOW(S)={#} ≠{a},冲突是可解决的,
– 但项目集 I8={C→a ·,D→a ·}中,FOLLOW(C)={a,b},
FOLLOW(D)={b},存在公共元素 b，不能解决此冲突,
? 还需考虑另一个条件：归约后得到的符号串应该是一个
规范句型的前缀，即当分析栈内容为 #??,输入符为 a时,
若将 ?归约为 A,则 #?Aa必须是某一规范句型的前缀,否则
这个归约就是 无效的,
8
9
LR(1)分析表 的构造（续）
? 例如,对于上述文法的规范
句型 Cbabab,分析达到格局,
I0I2I4I8 bab
# C b a
时,由于输入符
b∈ FOLLOW(C),若用 C来归
约,得到
I0I2I4I6 bab
# C b C
但 CbC不是任何规范 句型的
前缀 !因此应该用 D来归约，
得到规范 句型的 前缀 CbD,
? 因此,将 #??a? 归约成 #?Aa…
的前提条件不仅仅是要求
a∈FOLLOW(A),还必须要求 ?Aa
是 某规范句型的 前缀,
– 在原来的每个 LR(0)项目
[A????]中放置一向前搜
索符号 a,[A????,a],称
为 LR(1)项目,
– 要求每个 LR(1)项目 对相应
的活前缀是 有效的,以保
证每一步分析都能得到规
范句型的活前缀。
10
对 活前缀 有效 的 LR(1)项目
定义 LR(1)项目 [A????,a]对活前缀 ?=??有效,iff 存在
规范推导,S?? ?Ay ? ???y y?VT*,且满足条件,
(1)当 y≠ ?时,a∈ FIRST(y);
(2)当 y=?时,a=#,
? 例如,对于上例中文法 S’→S S→CbBA A→Aab|ab
B→C|Db C→a D→a,有
S ?CbBA?CbBab?CbDbab
A ? ? ? y
可知 [B→D ? b,a]
对前缀 ?=??
=CbD 有效
S??CbDbab?Cba bab
A ? ? ?=? y
可知 [D→a ?,b]
对前缀 ?=??
=Cba 有效
11
求 LR(1)项目集闭包算法
? 类似于 LR(0)分析,识别文法全部活前缀的 DFA的状态
是由 LR(1)项目集表示的,每个项目集由若干对相应的
活前缀 有效 的 LR(1)项目 组成,
? 对每个 LR(1)项目集 I,相应的闭包 CLOSURE(I)的定义为
(1) I?CLOSURE(I);
(2) 设 项目 [A?? ?B?,a] ?CLOSURE(I),并设它对活前缀
?=?? 有效,则对所有形如 B??的产生式,及每个
b?FIRST(?a),项目 [B???,b]也对 ?有效 (证明见后 ),即
将 [B???,b] =>CLOSURE(I);
(3) 重复 (2),直到 CLOSURE(I)不再增大,
12
新增项目对活前缀仍有效的证明
? 事实上,当 [A?? ?B?,a] 对 ?=?? 有效时,由定义,有,
S???Ay???B?y y?VT*
且 a?FIRST(y) ?{#}
即 S???Ay???B?a? ??VT*
无论 ?是否为 ?,可知 ?a?总能推出 终结符号串,
?a???b?’ b?FIRST(?a)
从而有规范推导, S???? B b?’ ? ?? ? b?’ 即 [B???,b]
对活前缀 ?=?? 有效,
13
GO函数及 DFA的构造方法
? 为求 GO(I,X),其中 I为 LR(1)项目集,X∈ V,类似于 LR(0)方
法,有, GO(I,X)=CLOSURE(J)
其中,J={[ A??X??,a ] | [ A???X?,a ] ?I}
? 注意,每个 LR(1)项目与其后继项目有相同的搜索符号
? 采用与 LR(0)类似的方法,可构造出 文法 G的 LR(1)项目集
族 C及状态转换图 (DFA),
14
I0,
S’ → ·S,#
S→·CbBA,#
C → ·a,b
I1,S’ →S ·,#
S
I3,C→a ·,b
a
I2,S →C·bBA,#
C
I4:S→Cb·BA,#
B→·C,a
B →·Db,a
C → ·a,a
D →·a,b
b
I5:S→CbB·A,#
A→·Aab,#/a
A →·ab,#/a
I6,B→C ·,a
B
C
I8,C→a ·,a
D →a ·,b
a
I7,B→D ·b,a
I9,B→Db ·,a
D
b
I11,A→a·b,#/a
I12,A→ab·,#/a
a
b
I10,S→CbBA·,#
A →A·ab #/a
A
I13,A→Aa·b,#/a
I14,A→Aab·,#/a
a
b
图 4-19 文法 G[S]的 LR(1)项目集及 DFA
15
LR(1)分析表 的构造
? 利用 LR(1)项目集族 C和 GO函数构造 LR(1)分析表,
(1) 对于每个项目集 Ii中的项目 [A???X?,a],并且
GO(Ii,X)=Ij,IF X∈ VT THEN ACTION(i,X)=sj ELSE
(X∈ VN) GOTO(i,X)=j;
(2) 若归约项目 [A???,a] ∈ Ii,A??是第 j产生式,则
ACTION(i,a)=rj;
(3) 若 [S’ →S ?,#] ∈ Ii,则 ACTION(i,#)=“acc”;
(4) 其它, ERROR,
? 对于一文法 G而言,若按上述方法所构造的分析表 不含
多重定义的元素,则称此分析表为 LR(1)分析表,凡具有
LR(1)分析表 的文法称为 LR(1)文法
16
状
态
ACTION GOTO a
b
# S
A
B
C
D
0
s3
1
2
1
acc
2
s4
3
r6
4
s8
5 6 7
5
s11
10
6
r4
7
s9
8
r6
r7
9
r5
10
s13
r1
11
s12
12
r3
r3
13
s14
14
r2
r2
分析表实例
17
五,LALR(1)分析简介
? 从前面的介绍可知,每个 LR(1)项目均由两部分组成,一是
LR(0)项目,称为 LR(1)项目的 核 ;一是向前搜索符号集,
? 对于移进项目,搜索符集无作用 ;对于归约项目,它指明了
在扫描到不同的符号时用不同的产生式进行归约,
? 上述原理解决了 SLR(1)分析中所不能解决的冲突,使 LR(1)
分析比 SLR(1)分析的能力有明显的提高,
? LR(1)也有缺点,分析表状态数过大,使分析的效率降低,
? 为解决二者之间的能力与效率之矛盾,LALR(1)分析是最
佳方案, LALR(1)方法的分析能力介于 LR(1)与 SLR(1)之
间,是目前最流行的分析技术,
18
LALR(1)分析简介 (续 )
?LALR(1)分析 (LookAhead-LR)是由 F.DeRemer提
出的,其基本思想就是将 LR(1)项目集中的同心集
合并,将其压缩为较小的 DFA,若压缩过程并未带
来新的冲突,则分析表可大大地简化 (状态数与
SLR(1),LR(0)的 DFA相同 ),
?核 相同的 LR(1)项目集称为同心集，合并同心集
是将其中对应的 LR(1)项目的向前搜索符号集合
并到一起。
19
?文法 G[E]
的 LR(1)
项目集,
合并前该
文法有 22
个状态。
20
21
?文法 G[E]
的
LALR(1)
项目集,
合并后只
有 12个状
态。
22
23
关于各类文法的一些结论
1,任何 LR(K),LL(K)及简单优先文法类都是无二
义性文法 ;
2,任何二义性的文法不可能是 LR(K)文法,但借助
其它方法,可对某些二义性文法建立无冲突的
LR(K)分析表 ;
3,每个 SLR(K)文法必是 LR(K)的,存在 LR(1)文法,
对任何 K,它不是 SLR(K)的,
4,各文法类之间的关系见图 4-24