第84集：LR(1)分析法

学习目标

理解LR(1)分析的基本概念和原理
掌握LR(1)项的定义和特点
学习LR(1)项集规范族的构造方法
掌握LR(1)分析表的构造方法
理解LR(1)分析如何解决SLR(1)分析的冲突
掌握LR(1)分析的过程和步骤
比较LR(1)分析与SLR(1)分析的优缺点
通过示例练习LR(1)分析的各个步骤

一、LR(1)分析的基本概念

1. LR(1)分析的定义

LR(1)分析是对SLR(1)分析的一种改进，它通过在项中添加上下文相关的展望符（lookahead）来解决SLR(1)分析中的冲突。LR(1)分析的基本思想是：

对于归约项 A → α.，只在输入符号属于特定的展望符集合时才进行归约
这个展望符集合是上下文相关的，比SLR(1)分析中使用的全局FOLLOW集更精确

LR(1)分析的名称中：

L 表示从左到右扫描输入串
R 表示构造最右推导的逆过程（最左归约）
1 表示使用一个展望符来决定归约操作

2. LR(1)分析与SLR(1)分析的区别

LR(1)分析与SLR(1)分析的主要区别在于：

SLR(1)分析：使用全局的FOLLOW集来决定归约操作，FOLLOW集是基于整个文法计算的
LR(1)分析：使用上下文相关的展望符集合来决定归约操作，展望符集合是基于当前分析上下文计算的

这种区别使得LR(1)分析能够解决SLR(1)分析中的冲突，从而扩大了适用范围。

3. LR(1)分析的优势

LR(1)分析具有以下优势：

更强的分析能力：能够解决SLR(1)分析中的冲突，处理更多的文法
更精确的归约决策：基于上下文相关的展望符，做出更精确的归约决策
无回溯：分析过程确定，不需要回溯
能处理左递归：与其他LR分析方法一样，能处理左递归文法

4. LR(1)分析的局限性

LR(1)分析的主要局限性是：

分析表大小：LR(1)分析表通常比SLR(1)分析表大得多，因为它为每个上下文都维护了不同的展望符集合
构造复杂度：LR(1)项集规范族的构造比SLR(1)更复杂，计算量更大

二、LR(1)项的概念

1. LR(1)项的定义

LR(1)项是对LR(0)项的扩展，它在LR(0)项的基础上添加了一个展望符（lookahead）。形式上，LR(1)项表示为 [A → α.β, a]，其中：

A → α.β 是LR(0)项，表示产生式的当前分析位置
a 是展望符，是一个终结符，表示在归约时期望的下一个输入符号

2. LR(1)项的含义

LR(1)项 [A → α.β, a] 的含义是：

我们希望在分析过程中看到一个由 αβ 推导出来的符号串
当我们成功分析完 αβ 后，下一个输入符号应该是 a
如果 β 是空串（即项是归约项 [A → α., a]），则当输入符号是 a 时，我们可以用产生式 A → α 进行归约

3. LR(1)项的类型

根据点的位置和展望符，LR(1)项可以分为以下几种类型：

移进项：点后面是终结符，如 [A → α.aβ, b]，此时需要移进终结符a
归约项：点在产生式右部的末尾，如 [A → α., a]，此时当输入符号是a时，可以用产生式A→α进行归约
待约项：点后面是非终结符，如 [A → α.Bβ, a]，此时需要处理非终结符B的产生式
接受项：归约项的一种特殊情况，产生式左部是开始符号，如 [S' → S., $]，此时分析成功

4. LR(1)项的等价性

两个LR(1)项 [A → α.β, a] 和 [A → α.β, b] 如果它们的LR(0)部分相同，仅展望符不同，则它们是同心项（core-identical items）。同心项可以在一定条件下合并，这是LALR(1)分析的基础。

三、LR(1)项集规范族的构造

1. LR(1)项的闭包操作

LR(1)项的闭包操作是构造LR(1)项集的核心操作，它比LR(0)项的闭包操作更复杂，因为需要考虑展望符。具体步骤如下：

初始时，项集包含给定的初始LR(1)项
对于项集中的每个待约项 [A → α.Bβ, a]，以及文法中每个B的产生式 B → γ，计算FIRST(βa)，并为每个终结符b∈FIRST(βa)，将项 [B → .γ, b] 添加到项集中
重复步骤2，直到项集不再变化

2. LR(1)项的转移操作

LR(1)项的转移操作与LR(0)项的转移操作类似，但需要保持展望符。具体步骤如下：

对于当前项集中的每个项，如果点后面的符号是X，即 [A → α.Xβ, a]，则将点向右移动一位，得到新项 [A → αX.β, a]
对这些新项应用闭包操作，得到新的项集

3. 构造LR(1)项集规范族的算法

构造LR(1)项集规范族的算法如下：

对扩展文法，构造初始项集I0，它是初始LR(1)项 [S' → .S, $] 的闭包
对每个项集I和每个文法符号X，如果Goto(I, X)存在且不在项集规范族中，则将其添加到项集规范族中
重复步骤2，直到项集规范族不再变化

4. LR(1)项集规范族的示例

考虑以下简单文法：

S → A
A → aAb | ε

扩展后的文法为：

S' → S
S → A
A → aAb | ε

构造LR(1)项集规范族的过程如下：

1. 初始项集I0

初始LR(1)项为 [S' → .S, $]，应用闭包操作：

添加 [S → .A, $]（因为S' → .S中的点后面是S，所以添加S的产生式，展望符保持$）
添加 [A → .aAb, $] 和 [A → .ε, $]（因为S → .A中的点后面是A，所以添加A的产生式，计算FIRST($)={$}，所以展望符是$）

所以I0为：

[S' → .S, $]
[S → .A, $]
[A → .aAb, $]
[A → .ε, $]

2. 从I0出发的转移

Goto(I0, S) = I1：包含项 [S' → S., $]（接受项）
Goto(I0, A) = I2：包含项 [S → A., $]
Goto(I0, a) = I3：包含项 [A → a.Ab, $]，应用闭包操作后添加 [A → .aAb, b] 和 [A → .ε, b]（因为A → a.Ab中的点后面是A，计算FIRST(b$)={b}，所以展望符是b）

3. 继续构造其他项集

按照同样的方法，可以构造出所有的LR(1)项集。

四、LR(1)分析表的构造

1. LR(1)分析表的构造规则

LR(1)分析表的构造规则与SLR(1)分析表类似，但使用LR(1)项集和展望符来决定归约操作：

移进表（Action表）构造：

对于状态i中的每个移进项 [A → α.aβ, b]，如果Goto(i, a) = j，则Action[i][a] = shift j
对于状态i中的每个归约项 [A → α., a]，Action[i][a] = reduce A→α
对于接受项 [S' → S., $]，Action[i][$] = accept

goto表构造：

对于每个状态i和非终结符A，如果Goto(i, A) = j，则Goto[i][A] = j

2. LR(1)分析表的冲突

由于LR(1)分析使用上下文相关的展望符，因此它能够解决SLR(1)分析中的大多数冲突。但在某些情况下，LR(1)分析仍然可能存在冲突：

移进-归约冲突：当状态i中存在移进项 [A → α.aβ, b] 和归约项 [B → γ., a] 时，会产生移进-归约冲突
归约-归约冲突：当状态i中存在多个归约项 [A → α., a] 和 [B → β., a] 时，会产生归约-归约冲突

这些冲突的存在意味着LR(1)分析也有其局限性，但它的能力已经大大超过了SLR(1)分析。

3. LR(1)分析表的示例

以下是上述简单文法的LR(1)分析表：

状态	Action			Goto
	a	b	$	S	A
0	s3	r3	r3	1	2
1			acc
2			r2
3	s3	r3			4
4		s5
5		r1	r1

其中：

s3表示移进到状态3
r3表示用产生式3（A→ε）进行归约
acc表示接受
空格表示错误

五、LR(1)分析的过程

1. LR(1)分析的基本步骤

LR(1)分析的过程与SLR(1)分析的过程类似，具体步骤如下：

初始化：
- 分析栈中压入初始状态0和结束符$
- 输入指针指向输入串的第一个符号
分析循环：
重复以下步骤，直到分析完成：
- 获取当前状态：栈顶的状态为当前状态s
- 获取当前输入符号：输入指针指向的符号为当前输入符号a
- 查找分析表：查找Action[s][a]的值
- 执行操作：
  - 移进（shift j）：将输入符号a和状态j压入栈，输入指针向前移动一位
  - 归约（reduce A→α）：
    - 从栈中弹出2*|α|个元素（|α|是产生式右部的长度，每个符号对应一个状态）
    - 此时栈顶的状态为t
    - 查找Goto[t][A] = k，将非终结符A和状态k压入栈
    - 输出归约信息
  - 接受（accept）：分析成功，结束分析
  - 错误（error）：分析失败，报告错误

2. LR(1)分析的示例

示例：简单文法的LR(1)分析

考虑以下简单文法：

S' → S
S → A
A → aAb | ε

1. 构造LR(1)项集规范族

按照上述方法，构造LR(1)项集规范族，得到项集I0到I5。

2. 构造LR(1)分析表

根据LR(1)项集规范族，构造LR(1)分析表（如上所示）。

3. 分析输入串 `aabb`

分析过程如下：

步骤	分析栈	剩余输入	Action	Goto	说明
1	0	aabb $	s3		移进a，进入状态3
2	0 a 3	abb $	s3		移进a，进入状态3
3	0 a 3 a 3	bb $	r3	4	用A→ε归约，Goto(3,A)=4
4	0 a 3 A 4	bb $	s5		移进b，进入状态5
5	0 a 3 A 4 b 5	b $	r1	4	用A→aAb归约，Goto(3,A)=4
6	0 a 3 A 4	b $	s5		移进b，进入状态5
7	0 a 3 A 4 b 5	$	r1	2	用A→aAb归约，Goto(0,A)=2
8	0 A 2	$	r2	1	用S→A归约，Goto(0,S)=1
9	0 S 1	$	acc		接受

3. LR(1)分析解决SLR(1)冲突的示例

考虑以下文法，它在SLR(1)分析中会产生冲突：

S → L | R
L → * R
R → id

扩展后的文法为：

S' → S
S → L | R
L → * R
R → id

1. SLR(1)分析的冲突

计算FOLLOW集：

FOLLOW(S) = {$}
FOLLOW(L) = {$}
FOLLOW(R) = {$}（从L→*R，β=ε，所以FOLLOW(R)包含FOLLOW(L)={$}）

构造SLR(1)分析表时，在状态包含项 L → *.R 和 R → .id 时，对于输入符号id，会产生移进-归约冲突：

移进：移进id，进入状态包含 R → id.
归约：用R→id归约（因为id∈FOLLOW(R)={$}？不，FOLLOW(R)={$}，所以不会产生冲突。这里可能需要一个更好的例子。

让我们考虑另一个例子，SLR(1)分析确实会产生冲突的文法：

S → A | B
A → a
B → a

这个文法是二义性的，SLR(1)分析和LR(1)分析都会产生归约-归约冲突。

六、LR(1)分析与SLR(1)分析的比较

1. 能力比较

LR(1)分析的能力更强：LR(1)分析通过使用上下文相关的展望符，能够解决SLR(1)分析中的冲突，处理更多的文法
SLR(1)分析的局限性：SLR(1)分析使用全局的FOLLOW集，可能包含一些在当前上下文中不可能出现的符号，导致无法解决某些冲突

2. 分析表大小比较

LR(1)分析表：通常比SLR(1)分析表大得多，因为它为每个上下文都维护了不同的展望符集合
SLR(1)分析表：相对较小，因为它使用全局的FOLLOW集

3. 构造复杂度比较

LR(1)分析的构造：更复杂，需要计算LR(1)项集规范族，计算量更大
SLR(1)分析的构造：相对简单，基于LR(0)项集规范族和FOLLOW集

4. 应用场景比较

LR(1)分析：适用于需要处理复杂文法的场景，但由于分析表较大，实际应用中较少直接使用
SLR(1)分析：适用于简单文法，实现简单，分析表较小
LALR(1)分析：结合了LR(1)分析的能力和SLR(1)分析的表大小优势，是实际编译器中最常用的LR分析方法

七、LR(1)分析的改进：LALR(1)分析

1. LALR(1)分析的基本思想

LALR(1)（Look-Ahead LR(1)）分析是LR(1)分析的一种优化，它通过合并LR(1)项集中的同心项集来减少分析表的大小，同时保持LR(1)分析的能力。

2. LALR(1)分析的构造步骤

LALR(1)分析的构造步骤如下：

构造LR(1)项集规范族：按照LR(1)分析的方法构造LR(1)项集规范族
合并同心项集：将具有相同LR(0)部分的LR(1)项集合并为一个项集
构造LALR(1)分析表：基于合并后的项集构造分析表

3. LALR(1)分析的优势

LALR(1)分析具有以下优势：

分析能力：接近LR(1)分析，能够处理大多数实际编程语言的文法
分析表大小：与SLR(1)分析表大小相近，适合实际应用
实现复杂度：比LR(1)分析低，比SLR(1)分析高

4. LALR(1)分析的应用

LALR(1)分析是实际编译器中最常用的LR分析方法之一，许多编译器构造工具（如Yacc/Bison）都使用LALR(1)分析。

八、LR(1)分析的实践练习

练习：构造LR(1)项集规范族

考虑以下简单文法：

S → A
A → aA | b

扩展文法，添加新的开始符号S'
构造LR(1)项集规范族
构造LR(1)分析表
分析输入串 aab 的过程

解决方案：

扩展文法：
```
S' → S
S → A
A → aA | b
```
构造LR(1)项集规范族：
- I0: [S'→.S, $], [S→.A, $], [A→.aA, $], [A→.b, $]
- I1: [S'→S., $]
- I2: [S→A., $]
- I3: [A→a.A, $], [A→.aA, $], [A→.b, $]
- I4: [A→b., $]
- I5: [A→aA., $]
构造LR(1)分析表：

状态 Action Goto

a b $ S A

0 s3 s4 1 2

1 acc

2 r2

3 s3 s4 5

4 r3

5 r1

**分析输入串 aab**：

步骤	分析栈	剩余输入	Action	Goto	说明
1	0	aab $	s3		移进a，进入状态3
2	0 a 3	ab $	s3		移进a，进入状态3
3	0 a 3 a 3	b $	s4		移进b，进入状态4
4	0 a 3 a 3 b 4	$	r3	5	用A→b归约，Goto(3,A)=5
5	0 a 3 a 3 A 5	$	r1	5	用A→aA归约，Goto(3,A)=5
6	0 a 3 A 5	$	r1	2	用A→aA归约，Goto(0,A)=2
7	0 A 2	$	r2	1	用S→A归约，Goto(0,S)=1
8	0 S 1	$	acc		接受

九、自测问题

选择题：LR(1)项是对LR(0)项的扩展，它添加了什么？
A. 产生式编号
B. 展望符
C. 优先级
D. 结合性
选择题：构造LR(1)项集规范族的两个核心操作是：
A. 闭包和转移
B. 推导和归约
C. 移进和归约
D. 合并和分裂
简答题：简述LR(1)分析表的构造规则。
简答题：解释LR(1)分析如何解决SLR(1)分析的冲突。
实践题：对于文法 S→A | B, A→aA | ε, B→bB | ε，构造LR(1)分析表，并分析输入串 aab 的过程。

十、小结

本集详细介绍了LR(1)分析方法，包括：

LR(1)分析的基本概念：对SLR(1)分析的改进，通过使用上下文相关的展望符解决冲突
LR(1)项的概念：在LR(0)项的基础上添加展望符，表示归约时期望的下一个输入符号
LR(1)项集规范族的构造：通过闭包和转移操作构造所有可能的LR(1)项集
LR(1)分析表的构造：基于LR(1)项集规范族构造分析表
LR(1)分析的过程：利用分析表指导移进和归约操作
LR(1)分析与SLR(1)分析的比较：LR(1)分析具有更强的能力，但分析表更大
LALR(1)分析的基本思想：通过合并同心项集，结合LR(1)分析的能力和SLR(1)分析的表大小优势

LR(1)分析是LR分析家族中能力最强的一种，它通过引入上下文相关的展望符，解决了SLR(1)分析中的冲突，扩大了LR分析的适用范围。虽然LR(1)分析的分析表较大，但它为后续的LALR(1)分析奠定了基础，而LALR(1)分析是实际编译器中最常用的LR分析方法之一。

十一、下集预告

下一集我们将学习LALR(1)分析方法，它是LR(1)分析的一种优化，通过合并同心项集来减少分析表的大小，同时保持LR(1)分析的能力。LALR(1)分析是实际编译器中最常用的LR分析方法之一，如Yacc/Bison等工具都使用LALR(1)分析。

参考资料

《编译原理》（龙书）- Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
《现代编译原理》（虎书）- Andrew W. Appel
《编译器设计》- Keith D. Cooper, Linda Torczon
LR(1)分析算法的历史与发展
Yacc/Bison用户手册

通过本集的学习，你应该对LR(1)分析方法有了全面的了解。LR(1)分析通过引入上下文相关的展望符，解决了SLR(1)分析中的冲突，是LR分析家族中能力最强的一种。虽然LR(1)分析的分析表较大，但它为后续的LALR(1)分析奠定了基础，而LALR(1)分析是实际编译器中最常用的LR分析方法之一。在后续的学习中，我们将深入探讨LALR(1)分析方法的具体实现和应用。

第84集：LR(1)分析法

学习目标

一、LR(1)分析的基本概念

1. LR(1)分析的定义

2. LR(1)分析与SLR(1)分析的区别

3. LR(1)分析的优势

4. LR(1)分析的局限性

二、LR(1)项的概念

1. LR(1)项的定义

2. LR(1)项的含义

3. LR(1)项的类型

4. LR(1)项的等价性

三、LR(1)项集规范族的构造

1. LR(1)项的闭包操作

2. LR(1)项的转移操作

3. 构造LR(1)项集规范族的算法

4. LR(1)项集规范族的示例

1. 初始项集I0

2. 从I0出发的转移

3. 继续构造其他项集

四、LR(1)分析表的构造

1. LR(1)分析表的构造规则

移进表（Action表）构造：

goto表构造：

2. LR(1)分析表的冲突

3. LR(1)分析表的示例

五、LR(1)分析的过程

1. LR(1)分析的基本步骤

2. LR(1)分析的示例

示例：简单文法的LR(1)分析

1. 构造LR(1)项集规范族

2. 构造LR(1)分析表

3. 分析输入串 aabb

3. LR(1)分析解决SLR(1)冲突的示例

1. SLR(1)分析的冲突

六、LR(1)分析与SLR(1)分析的比较

1. 能力比较

2. 分析表大小比较

3. 构造复杂度比较

4. 应用场景比较

七、LR(1)分析的改进：LALR(1)分析

1. LALR(1)分析的基本思想

2. LALR(1)分析的构造步骤

3. LALR(1)分析的优势

4. LALR(1)分析的应用

八、LR(1)分析的实践练习

练习：构造LR(1)项集规范族

解决方案：

九、自测问题

十、小结

十一、下集预告

参考资料

3. 分析输入串 `aabb`