1
4.2.4 LR分析法
?1965年 D.Knuth提出了分析效率很高的 LR(k)分
析技术 ;
?LR分析, 自左至右扫描的自底向上的分析 ;
?在分析的每一步,只须根据分析栈中的已移进的
和已归约出的符号,并至多向前扫描 k个字符就
能确定应采取什么分析动作 (移进、归约、接受、
报错 );
?LR分析对文法要求很少,效率很高,且能及时发
现错误,是目前最广泛使用的方法 ;一般用 CFG描
述的语言均可用 LR分析法
2
LR分析综述
? 已证明的结论,
– LR(k)文法是 无二义性 文法 ;
– LR(k)文法与 LR(1)文法 等价,
? 由于常见的程序设计语言均能由 LR(1)文法产生,因此只讨论
下面的四种 LR分析器,
– LR(0)简单,分析能力最低 ;
– SLR(1)分析能力强于 LR(0);
– LR(1)分析能力最强,但分析表大 ;
– LALR(1)分析能力介于 SLR(1)与 LR(1)之间,分析表的规模
与 SLR(1)相同,是 最常用 的 LR分析方法。
3
LR分析器的逻辑结构及工作原理
? 分析器 自左至右地扫描 输入串 的
各符号，并根据当前 分析栈 的内
容及正扫描的符号按 分析表 的指
示完成相应的动作。
? 分析栈 记录了已分析的内容及当
前的状态；
? 开始时，栈内放入 #及开始状态
S0，随着分析的深入，栈内容总
是刻划了当前的状态，及分析的
,历史,。
总控程序
分析表
分
析
栈
a1 a2 … a i …a n#
Sm Xm
…
S1 X1
S0 #
内
容
状
态
4
LR分析表
a1 a2 … al
S1 ACTION[S1,a1] ACTION[S1,a2] … ACTION[S1,al]
S2 ACTION[S2,a1] ACTION[S2,a2] … ACTION[S2,al]
… … … … …
Sn ACTION[Sn,a1] ACTION[Sn,a2] … ACTION[Sn,al]
X1 X2 … Xl
S1 GOTO[S1,X1] GOTO[S1,X2] … GOTO[S1,Xl]
S2 GOTO[S2,X1] GOTO[S2,X2] … GOTO[S2,Xl]
… … … … …
Sn GOTO[Sn,X1] GOTO[Sn,X2] … GOTO[Sn,Xl]
ACTION 表（分析动作表）
GOTO表（状态转换表）
5
LR分析表实例
? 设已给文法 G[L],1,L?E,L； 2,L?E； 3,E?a； 4,E?b，产
生的语言为：单个 a,b或用逗号隔开的多个 a,b符号串
? 文法的 LR分析表 (s表示移进操作 )
a
b
,
#
0
s
s
1
acc
2
s
r2
3
r3
r3
4
r4
r4
5
s
s
6
r1
a
b
,
#
L
E
0
3
4
1
2
1
2
5
3
4
5
3
4
6
2
6
ACTION表 GOTO表
6
分析表的合并
? 可看出,GOTO表中所有关于终结符的状态转换都与
ACTION表中的移进操作对应，因此可将相应的列合并，
得到下面的分析表（关于 VN符的状态转换仍然保留）,
状态
ACTION
GOTO
a
b
,
#
L
E
0
s3
s4
1
2
1
acc
2
s5
r2
3
r3
r3
4
r4
r4
5
s3
s4
6
2
6
r1
实际的分析表往
往是稀疏的，可
采用更 紧凑的格
式 存储。
7
LR分析器的工作过程
1,分析开始时,首先将初始状
态 S0及 #压入栈 ;
2,设在分析的某一步,分析栈
和余留输入串处于格局,
S0S1S2…S m
# X1X2…X m aiai+1ai+2…a n#
用 Sm,ai查 ACTION表,并根据指示完成相应的动作,分析
动作有移进,归约,报错,接受四种,
(1)移进 sk,表明句柄尚未在栈顶形成,正期待继续移进
输入符号 ai以形成句柄,并且移入后状态转移到 Sk,故
将 ai和 Sk压入栈，格局如下,
S0S1S2…S mSk
# X1X2…X mai ai+1ai+2…a n#
8
LR分析器的工作过程（续）
(2)归约 rj：其中 rj表示按 P的第 j产生式 A?Xm-k+1Xm-k+2? Xm
进行归约 ;这表明栈顶部的符号串 Xm-k+1Xm-k+2? Xm是当
前句型的 句柄, 将栈顶符号串 Xm-k+1Xm-k+2? Xm(k个符号 )
从栈顶退出,再将 A压入栈,此时的格局为
S0S1S2…S m-k
# X1X2…X m-kA aiai+1ai+2…a n#
再以 （ Sm-k,A） 查 GOTO表,得 Sk,将 Sk压入栈,得到格局,
S0S1S2…S m-rSk
# X1X2…X m-rA aiai+1ai+2…a n#
9
LR分析器的工作过程 (续 )
(3)若 ACTION(Sm,ai)=“acc”,则表明当前输入串已被成功地
分析完毕,结束 ;
(4)若 ACTION(Sm,ai)=“ERROR”,则表明当前输入串有语法
错误,转入出错处理程序 ;
3,重复步骤 2.的工作,直到分析的某步的格局为,
S0SZ
# Z #
其中,Z为文法 的开始符号,SZ是使 ACTION(SZ,#)=“acc”
的唯一状态,
10
符号串, a,b,a”的 LR分析过程
步骤
状态
栈中符号
余留符号
分析动作
下一状态
1
0
#
a,b,a#
s3
3
2
03
#a
,b,a#
r3
GOTO[0,E]=2
3
02
#E
,b,a#
s5
5
4
025
#E,
b,a#
s4
4
5
0254
#E,b
,a#
r4
GOTO[5,E]=2
6
0252
#E,E
,a#
s5
5
7
02525
#E,E,
a#
s3
3
8
025253
#E,E,a
#
r3
GOTO[5,E]=2
9
025252
#E,E,E
#
r2
GOTO[5,L]=6
10
025256
#E,E,L
#
r1
GOTO[5,L]=6
11
0256
#E,L
#
r1
GOTO[0,L]=1
12
01
#L
#
11
LR分析器 的总控程序
parser( ){
初始化 ；
while((item=ACTION[TopStat][InpSym]))!=acc){
if(item=ERROR) error( );
if(item=sj){push(j); advance( );}
else reduce(i); /* item= ri*/
}
accept( );
}
12
二,LR（ 0） 分析表 的构造
? LR(0)分析就是 k=0时的 LR(k)分析,即在分析的每一步,
根据当前的栈顶状态确定下一步动作,
? 首先引入一些重要的概念和术语
1,规范句型的活前缀 (viable prefix)
将栈内符号与未扫描的输入串拼接起来,可得一 规范
句型,即栈内符号串总是 规范句型的前缀,且 不含句柄
右侧的符号, 原因,句柄一旦在栈顶形成,就不再移进新
符号,而是要进行归约,
把具有上述性质的符号串称为 规范句型的活前缀,两
个要点, (1)它是规范句型的前缀 ; (2)它不含句柄右侧
符号
13
规范句型的活前缀 (续 )
? 在 前面例子 中的第五行, #E,b,a#中,b是当前句型的句柄,
“?”,“E”,“E,”,“E,b”都是 规范句型的活前缀,
? LR分析过程实际上就是一个逐步产生 (并识别 )规范句
型的活前缀 的过程,在分析的每一步,栈内符号总是当
前规范句型的活前缀,且与此时栈顶符号相关联,
? 提示, 通过构造一个 识别所有活前缀的自动机,来构造分
析表,
14
LR(0)项目集
? 由于 规范句型的活前缀 不含句柄右侧符号,它与当前
句柄的关系只能是下述三种情况之一,
(1) 活前缀 包含句柄的全部符号 (句柄是其后缀 );
(2) 活前缀 只含句柄的部分符号 (其 后缀是句柄的前缀 );
(3) 活前缀 不含句柄的任何符号,
对于 (1),应用某产生式 A??归约,记为 A???;
对于 (2),应移进 (句柄的后半部分 ?2),A??1??2;
对于 (3),期望移进某产生式的右部,A???
“?”表示已经识别到某产生式中的位置，把右部添加了一
个, ?” 的产生式,称为 LR(0)项目
15
LR(0)项目集 (续 )
? 同一产生式 (设右部有 n个符号 )对应了若干 (n+1)个 LR(0)
项目,每个项目反映了 栈顶 所处的 不同状态,
? 若 A??∈ P,则对应了唯一的 LR(0)项目 A→ ?；
? 所有的 LR(0)项目是构造识别活前缀的自动机的基础。
16
LR(0)项目集举例
? 例文法 G[S],S?A | B; A?aAb | c; B?aBb | c 为识别方
便,引入新开始符 S’及产生式 S’?S,得到拓广的文法 G’,
G’的 LR(0)项目如下,
1,S’ ??S
2,S’?S ?
3,S ? ?A
4,S ?A ?
5,S ? ?B
6,S ?B ?
7,A ? ? aAb
8,A ? a?Ab
9,A ?aA?b
10,A ?aAb?
11,A ??c
12,A ?c?
⒔ B? ?aBb
⒕ B? a?Bb
⒖ B? aB?b
⒗ B? aBb?
⒘ B ? ?d
⒙ B? d?
? 上面的 LR(0)项目可用一对整数 (m,n)表示,其中,m表示第
m产生式,n表示圆点在该产生式的位置 ;
? 如项目 1.可用 (0,0)表示,项目 14.可用 (5,1)表示等等,
17
LR(0)项目集 (续 )
? 由于不同的项目反映了分析过程的不同情况,因此,我们
可根据其不同作用将其分类,
? 对于形如 A→ ??的项目,此时应进行 归约,因此称为 归约
项目,如前例中的 2,4,8,10,12,16,18(蓝色项目 )等 ;其中 2
用于最后一次归约，表明整个过程完成，称之为接受项
目。对于拓广文法 G’来说，接受项目是唯一的。
? 对于形如 A???X?的项目,( X?VT,?可以是空串 )的项目,
则有待于 移进 一个 VT符号 X到栈中,因此称为 移进项目,
如前例中的 5,7,9,13,15,17(红色项目 )等 ;
? 对于形如 A???X?的项目,( X?VN,?可以是空串 )我们
期待移进 若干符号之后并将其 归约 为 X,因此称为 待约项
目,如前例中的 1,3,6,14(绿色项目 )等,
18
识别所有规范句型全部活前缀的 DFA
? DFA的每个状态由 LR(0)项目集表示 ;
? 由状态 I构造下一状态 J的过程：（ 1）计算项目集 I的
后继项目，并将它们的集合作为 J的基本项目集；（ 2）
由基本项目集计算 J对应的项目集（求闭包）。 (3)定
义状态转移函数 GO(I,X)=J，表示 J是 I的后继状态 ;
? 一个项目集 I的闭包 CLOSURE(I)的计算如下,
1,I ?CLOSURE( I );
2,若 A→ ??X??CLOSURE(I),且 X?VN,则对任何 X-产生式
X→ ??P,有 X????CLOSURE(I);
3.重复上述过程,直到 CLOSURE(I)不再增大,
19
构造 DFA的方法
?计算项目集 J的基本项目集,
– 对于 I中 形如 A → ?X?（ X?V） 的 项目,当分析器识
别出 X后,进入下一状态 J,J中必含有全部 A → X??
项目，称它们为项目 A→ ?X?的后继项目。
– 关于 X的后继项目可能有多个,将其合并在一起构成
J的基本项目集。
?开始时初态 I0只 含有一个基本项目 S’→ ● S
20
举例 拓广的文法 G’,S’?S; S?A | B; A?aAb | c;
B?aBb | c
状态 LR（ 0）项目集 识别符号 目标状态 GO函数
I0 S’→ ?S
S→ ?A
S→ ?B
A→ ?aAb
A→ ?c
B→ ?aBb
B→ ?d
S
A
B
a
c
d
I1
I2
I3
I4
I5
I6
GO(I0,S) = I1
GO(I0,A) = I2
GO(I0,B) = I3
GO(I0,a) = I4
GO(I0,c) = I5
GO(I0,d) = I6
I1 S’→S ?
I2 S→A ?
I3 S→B ?
I5 A→c ?
I6 B→d ?
红色为基本项目
21
举例 (续 )
状态 LR（ 0）项目集 识别符号 目标状态 GO函数
I4 A→a ?Ab
B→a ?Bb
A→ ?aAb
A→ ?c
B→ ?aBb
B→ ?d
A
B
a
c
d
I7
I9
I4
I5
I6
GO(I4,A) = I7
GO(I4,B) = I9
I7 A→aA ?b b I8 GO(I7,b) = I8
I8 A→aAb ?
I9 B→aB ?b b I10 GO(I9,b) = I10
I10 B→aAb ?
拓广的文法 G’,S’?S;
S?A | B; A?aAb | c;
B?aBb | c
22
? 全部状态的集合称为文法 G[S]的 LR(0)项目集规范族,记
为 C={I0,I1,…,I 10};
? 识别文法 G[S]全部活前缀的 DFA为, M=(C,V,GO,I0,C);
其中,
状态集及终态集为项目集规范族 C;
字母表为 V=VN∪ VT∪ {S’}
23
I0,
S’→·S
S→·A
S→·B
A→·aAb
A→·c
B→·aBb
B→·d
I1,S’→S·
S
I2,S→A· A
I3,S→B·
B
I4,
A→a·Ab
A→·aAb
A→·c
B→a·Bb
B→·aBb
B→·d
a
I5,A→c·
c
c
I6,A→d·
d
d
a
I7,A→aA·b
I9,B→aB·b
I8,A→aAb·
I10,B→aBb·
B
A
b
b
图 4-16 识别 G[S]全部活前缀的 DFA
24
LR(0)分析表的构造
? 每个 项目集 代表了分析过程中的一个 状态,
且其中每个项目与分析动作相关,因此要求
每个项目集的各个项目是 相容 的,即在同一
项目集中,不应出现,
1.移进项目与归约项目并存 ;
2.多个归约项目并存,
? 若文法 G满足上述条件,不含上述冲突项目,
则称 G为 LR(0)文法,
? 只有当一文法是 LR(0)文法时,才能构造出无
冲突动作的分析表来,
25
构造 LR(0)分析表 的算法
?用序号 i表示状态 Ii,则填写 LR(0)分析表的方法
如下,
(1)对于每个项目集 Ii中形如 A→ ??X?项目,并且
GO(Ii,X)=Ij,若 X∈V T,则为移进项目，置
ACTION[i,X]=sj,若 X∈V N,待约项目，置 GOTO[i,X]=j;
(2)对于每个项目集 Ii中的归约项目 A→ ??,且 A→ ?是 P中
第 j产生式,则对于 ?a?VT?{#},置 ACTION[i,a]=rj
(3)特别地，若接受项目 S’→S ·属于 Ii,则置
ACTION[i,#]=“acc”，去掉 r0;
(4)在表中其它未填入信息的栏目中均填, ERR”,
26
ACTION
GOTO
a
b
c
d
#
S
A
B
0
s4
s5
s6
1
2
3
1
acc
2
r1
r1
r1
r1
r1
3
r2
r2
r2
r2
r2
4
s4
s5
s6
7
9
5
r4
r4
r4
r4
r4
6
r6
r6
r6
r6
r6
7
s8
8
r3
r3
r3
r3
r3
9
s10
10
r5
r5
r5
r5
r5
表 4-13 G[S]的 LR(0)分析表
