第82集：LR(0)分析法

学习目标

• 理解LR(0)项和项集的概念
• 掌握LR(0)项集规范族的构造方法
• 学习如何构建LR(0)自动机
• 掌握LR(0)分析表的构造方法
• 理解LR(0)分析的过程和原理
• 了解LR(0)分析的局限性和冲突处理
• 通过示例练习LR(0)分析的各个步骤

一、LR(0)项的概念

1. LR(0)项的定义

LR(0)项是对文法产生式的一种扩展表示，它在产生式的右部某个位置添加一个点（.），用于表示分析过程中的当前位置。形式上，对于产生式 A → αβ，对应的LR(0)项包括：

• A → .αβ：点在最左端，表示还没有处理产生式右部的任何符号
• A → α.β：点在中间，表示已经处理了α部分，接下来要处理β部分
• A → αβ.：点在最右端，表示已经处理了产生式右部的所有符号，此时可以进行归约

2. LR(0)项的类型

根据点的位置，LR(0)项可以分为以下几种类型：

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

3. 扩展文法

为了处理开始符号，通常需要对原文法进行扩展，添加一个新的开始符号S'和产生式S'→S，其中S是原文法的开始符号。这样做的目的是确保分析过程只有一个接受状态。

例如，对于原文法：

S → E
E → E + T | T
T → T * F | F
F → ( E ) | id

扩展后的文法为：

S' → S
S → E
E → E + T | T
T → T * F | F
F → ( E ) | id

二、LR(0)项集规范族的构造

LR(0)项集规范族是指由所有可能的LR(0)项集组成的集合，它是构建LR(0)自动机的基础。构造LR(0)项集规范族的核心是两个操作：闭包（Closure）和转移（Goto）。

1. 闭包操作（Closure）

闭包操作用于构造一个项集，它从一个初始项开始，添加所有可能的相关项。具体步骤如下：

1. 初始时，项集包含给定的初始项
2. 对于项集中的每个待约项 A → α.Bβ，将非终结符B的所有产生式 B → γ 对应的项 B → .γ 添加到项集中
3. 重复步骤2，直到项集不再变化

2. 转移操作（Goto）

转移操作用于构造从一个项集到另一个项集的转移，它根据当前处理的符号X，生成一个新的项集。具体步骤如下：

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

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

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

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

三、LR(0)自动机的构建

LR(0)自动机是一个确定有限自动机（DFA），它的状态对应于LR(0)项集，边对应于转移操作。构建LR(0)自动机的步骤如下：

1. 构造项集规范族：按照上述算法构造所有可能的LR(0)项集
2. 定义状态：每个项集对应自动机的一个状态
3. 定义边：对于每个项集I和文法符号X，如果Goto(I, X) = J，则添加一条从I到J的边，标记为X
4. 定义初始状态：初始项集I0对应自动机的初始状态
5. 定义接受状态：包含接受项 S' → S. 的项集对应自动机的接受状态

示例：构建算术表达式文法的LR(0)自动机

考虑扩展后的算术表达式文法：

S' → S
S → E
E → E + T | T
T → T * F | F
F → ( E ) | id

构造LR(0)项集规范族和自动机的过程如下：

1. 初始项集I0

初始项为 S' → .S，应用闭包操作：

• 添加 S → .E（因为S' → .S中的点后面是S，所以添加S的产生式）
• 添加 E → .E + T 和 E → .T（因为S → .E中的点后面是E，所以添加E的产生式）
• 添加 T → .T * F 和 T → .F（因为E → .T中的点后面是T，所以添加T的产生式）
• 添加 F → .( E ) 和 F → .id（因为T → .F中的点后面是F，所以添加F的产生式）

所以I0为：

S' → .S
S → .E
E → .E + T
E → .T
T → .T * F
T → .F
F → .( E )
F → .id

2. 从I0出发的转移

• Goto(I0, S) = I1：包含项 S' → S.（接受项）
• Goto(I0, E) = I2：包含项 S → E.、E → E.+ T
• Goto(I0, T) = I3：包含项 E → T.
• Goto(I0, F) = I4：包含项 T → F.
• Goto(I0, () = I5：包含项 F → (. E )，应用闭包后添加E的产生式
• Goto(I0, id) = I6：包含项 F → id.

3. 继续构造其他项集

按照同样的方法，可以构造出所有的项集和转移，最终得到LR(0)自动机。

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

LR(0)分析表是指导LR(0)分析器操作的核心数据结构，它由两部分组成：

• 移进表（Action表）：对于每个状态和终结符，指定是移进还是归约
• ** goto表**：对于每个状态和非终结符，指定转移到的下一个状态

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

构造LR(0)分析表的规则如下：

移进表（Action表）构造：

• 对于状态i中的每个移进项 A → α.aβ，如果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(0)分析表的冲突

由于LR(0)分析不考虑展望符（lookahead），因此在构造分析表时可能会出现冲突：

• 移进-归约冲突：同一个状态和终结符既可以移进又可以归约
• 归约-归约冲突：同一个状态和终结符可以用多个产生式进行归约

这些冲突的存在限制了LR(0)分析的适用范围，只能处理部分简单的文法。

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

以下是上述算术表达式文法的LR(0)分析表的一部分：

其中：

• s6表示移进到状态6
• r2表示用产生式2（E → T）进行归约
• acc表示接受
• 空格表示错误

五、LR(0)分析的过程

LR(0)分析的过程是一个利用分析表指导移进和归约操作的过程，具体步骤如下：

1. 初始化

• 分析栈中压入初始状态0和结束符$
• 输入指针指向输入串的第一个符号

2. 分析循环

重复以下步骤，直到分析完成：

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

3. 示例：LR(0)分析过程

对于输入串 id + id * id，使用上述算术表达式文法的LR(0)分析表，分析过程如下：

六、LR(0)分析的局限性

LR(0)分析虽然是LR分析的基础，但它有明显的局限性：

1. 冲突问题

由于LR(0)分析不考虑展望符，因此容易产生移进-归约冲突和归约-归约冲突。例如，对于以下文法：

S → A
A → aAb | ε

在状态包含项 A → aAb. 和 A → . 时，会产生归约-归约冲突。

2. 适用范围有限

LR(0)分析只能处理部分简单的文法，对于大多数实际编程语言的文法，LR(0)分析都会产生冲突。这导致LR(0)分析在实际应用中很少直接使用，而是作为更高级LR分析方法（如SLR(1)、LR(1)和LALR(1)）的基础。

3. 错误处理能力弱

LR(0)分析的错误处理能力较弱，当遇到错误时，只能简单地报告错误，而无法提供更具体的错误信息和恢复策略。

七、LR(0)分析的改进方向

为了克服LR(0)分析的局限性，后续发展了多种改进的LR分析方法：

1. SLR(1)分析

SLR(1)（Simple LR(1)）分析通过使用FOLLOW集来解决部分冲突：

• 对于归约项 A → α.，只在输入符号属于FOLLOW(A)时才进行归约
• 这样可以减少归约操作的次数，从而解决部分移进-归约冲突

2. LR(1)分析

LR(1)分析通过在项中添加展望符（lookahead）来解决冲突：

• LR(1)项的形式为 [A → α.β, a]，其中a是展望符
• 展望符表示在归约时期望的下一个输入符号
• 这样可以更精确地决定何时进行归约，从而解决更多冲突

3. LALR(1)分析

LALR(1)（Look-Ahead LR(1)）分析是LR(1)分析的一种优化：

• 通过合并LR(1)项集中的同心项集，减少分析表的大小
• 在保持LR(1)分析能力的同时，降低了空间复杂度
• 是实际编译器中最常用的LR分析方法之一

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

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

考虑以下简单文法：

S → A
A → aA | b

1. 扩展文法，添加新的开始符号S'
2. 构造初始项集I0
3. 计算所有可能的转移和项集
4. 构建LR(0)自动机
5. 构造LR(0)分析表
6. 分析输入串 aab 的过程

解决方案：

1. 扩展文法：

   S' → S
   S → A
   A → aA | b

2. 初始项集I0：

   S' → .S
   S → .A
   A → .aA
   A → .b

3. 转移和项集：

   • Goto(I0, S) = I1：S' → S.
   • Goto(I0, A) = I2：S → A.
   • Goto(I0, a) = I3：A → a.A, A → .aA, A → .b
   • Goto(I0, b) = I4：A → b.
   • Goto(I3, A) = I5：A → aA.
   • Goto(I3, a) = I3：（自循环）
   • Goto(I3, b) = I4：

4. LR(0)分析表：

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

5. **分析输入串 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(0)分析的总结

1. LR(0)分析的优点

• 理论基础：LR(0)分析是所有LR分析方法的基础，理解LR(0)分析对于学习其他LR分析方法至关重要
• 表驱动：LR(0)分析采用表驱动的方式，分析过程高效且确定
• 无回溯：LR(0)分析不需要回溯，分析过程是线性的
• 构造方法简单：LR(0)项集和分析表的构造方法相对简单，易于理解

2. LR(0)分析的缺点

• 冲突问题：容易产生移进-归约冲突和归约-归约冲突
• 适用范围有限：只能处理部分简单的文法，无法处理大多数实际编程语言的文法
• 错误处理能力弱：错误处理能力有限，错误信息不够具体

3. LR(0)分析的学习价值

虽然LR(0)分析在实际应用中很少直接使用，但它具有重要的学习价值：

• 帮助理解LR分析的基本原理和思想
• 为学习更高级的LR分析方法（如SLR(1)、LR(1)和LALR(1)）打下基础
• 培养对语法分析过程的深入理解
• 锻炼形式化方法的思维能力

十、自测问题

1. 选择题：LR(0)项是对文法产生式的扩展表示，它添加了一个点（.）用于表示：
   A. 产生式的优先级
   B. 分析过程中的当前位置
   C. 产生式的可选部分
   D. 产生式的结束位置

2. 选择题：构造LR(0)项集规范族的两个核心操作是：
   A. 闭包和转移
   B. 推导和归约
   C. 移进和归约
   D. 合并和分裂

3. 简答题：简述LR(0)分析表的构造规则。

4. 简答题：解释LR(0)分析中的移进-归约冲突和归约-归约冲突。

5. 实践题：对于文法 S → A | B, A → aA | ε, B → bB | ε，构造LR(0)项集规范族和分析表，并分析输入串 aab 的过程。

十一、小结

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

1. LR(0)项的概念：对产生式的扩展表示，用于表示分析过程中的当前位置
2. LR(0)项集规范族的构造：通过闭包和转移操作构造所有可能的项集
3. LR(0)自动机的构建：将项集作为状态，转移作为边，构建确定有限自动机
4. LR(0)分析表的构造：根据项集和转移构造移进表和goto表
5. LR(0)分析的过程：利用分析表指导移进和归约操作
6. LR(0)分析的局限性：容易产生冲突，适用范围有限
7. LR(0)分析的改进方向：SLR(1)、LR(1)和LALR(1)分析

LR(0)分析虽然在实际应用中很少直接使用，但它是LR分析方法的基础，理解LR(0)分析对于学习更高级的LR分析方法至关重要。通过学习LR(0)分析，我们可以更深入地理解自底向上分析的原理和过程，为后续学习更复杂的语法分析方法打下坚实的基础。

十二、下集预告

下一集我们将学习SLR(1)分析方法，它是对LR(0)分析的改进，通过使用FOLLOW集来解决部分冲突。SLR(1)分析具有更强的分析能力，能处理更多的文法，同时保持了LR(0)分析的简单性。

参考资料

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

通过本集的学习，你应该对LR(0)分析方法有了全面的了解。LR(0)分析是LR分析家族的基础，虽然它有一定的局限性，但它的思想和方法为后续更高级的LR分析方法奠定了基础。在后续的学习中，我们将逐步深入学习SLR(1)、LR(1)和LALR(1)等更高级的LR分析方法，这些方法在实际编译器中得到了广泛的应用。