第55集：LR分析器简介
学习目标
- 理解LR分析器的基本原理和工作过程
- 掌握移进-归约分析的基本概念
- 了解LR分析器的分类（LR(0)、SLR(1)、LR(1)、LALR(1)）
- 理解项集和项集规范族的概念
- 了解LR分析表的构建方法
1. LR分析器概述
1.1 基本原理
LR分析器是一种自底向上的语法分析方法，它的基本原理是：
- 从左到右扫描输入符号串
- 构建最右推导的逆过程（最左归约）
- 使用栈来记录分析状态和已分析的符号
- 通过分析表来决定每一步是移进还是归约
1.2 与LL分析器的比较
LL分析器（自顶向下）：
- 从开始符号开始，构建最左推导
- 每一步需要向前看k个符号来决定使用哪个产生式
- 对文法有严格要求（LL(k)）
- 实现相对简单
LR分析器（自底向上）：
- 从输入符号串开始，构建最左归约
- 每一步根据当前状态和输入符号决定操作
- 对文法要求较宽松，可以处理更多类型的文法
- 实现相对复杂，但更强大
1.3 优势
LR分析器的主要优势包括：
- 强大的分析能力：可以处理几乎所有实用的上下文无关文法
- 高效的分析速度：线性时间复杂度，与输入长度成正比
- 准确的错误定位：可以在错误发生后的第一个符号处检测到错误
- 统一的分析方法：适用于各种类型的编程语言
2. 移进-归约分析
2.1 基本概念
移进-归约分析是LR分析器的核心技术，它的基本操作包括：
- 移进（Shift）：将当前输入符号压入栈，并读取下一个输入符号
- 归约（Reduce）：根据当前栈顶的内容，选择合适的产生式进行归约，将栈顶的符号串替换为产生式的左部非终结符
- 接受（Accept）：当输入串处理完毕且栈中只剩开始符号时，分析成功
- 报错（Error）：当无法进行移进或归约操作时，分析失败
2.2 归约过程
归约过程是最右推导的逆过程，例如：
最右推导：
E ⇒ E + T ⇒ E + F ⇒ E + num最左归约：
E + num ⇒ E + F ⇒ E + T ⇒ E2.3 句柄
句柄是句型中的一个子串，它与某个产生式的右部匹配，并且在归约过程中被替换为该产生式的左部非终结符。
例如，对于句型 E + num，句柄是 num，可以归约为 F。
3. LR分析器的组成
3.1 组成部分
LR分析器由以下四部分组成：
- 输入缓冲区：存储待分析的词法单元序列，以结束符 $ 结尾
- 分析栈：存储状态和文法符号，状态用于决定下一步操作
- 分析表：二维表，根据当前状态和输入符号决定下一步操作
- 控制程序：执行分析表指定的操作
3.2 分析栈的结构
分析栈分为两部分：
- 状态栈：存储分析状态
- 符号栈：存储已分析的文法符号
初始时，状态栈包含初始状态 0，符号栈包含开始符 $。
3.3 分析表的结构
分析表由两部分组成：
- ACTION表：指定当前状态和输入符号时的操作（移进、归约、接受、报错）
- GOTO表：指定归约后应转移到的新状态
4. LR分析器的工作过程
4.1 工作步骤
- 初始化：将初始状态 0 压入状态栈，将 $ 压入符号栈，输入指针指向第一个输入符号
- 循环处理：重复以下步骤直到分析完成：
- 设当前状态为 s（状态栈顶元素），当前输入符号为 a
- 查看 ACTION[s, a]：
- 如果是移进操作 s'，则将 s' 压入状态栈，将 a 压入符号栈，输入指针后移
- 如果是归约操作 A→β，则弹出状态栈中 |β| 个元素，设新的栈顶状态为 s''，将 GOTO[s'', A] 压入状态栈，将 A 压入符号栈
- 如果是接受操作，则分析成功
- 如果是报错，则分析失败
4.2 示例分析
以文法 E → E + T | T, T → T * F | F, F → ( E ) | id 为例，分析输入串 id + id * id：
步骤：
- 初始状态：状态栈 [0]，符号栈 [$]，输入
id + id * id $ - ACTION[0, id] = s5（移进），状态栈 [0, 5]，符号栈 [$id]，输入
+ id * id $ - ACTION[5, +] = r6（归约 F→id），弹出状态 5，状态栈 [0]，GOTO[0, F] = 3，状态栈 [0, 3]，符号栈 [$F]，输入
+ id * id $ - ACTION[3, +] = r4（归约 T→F），弹出状态 3，状态栈 [0]，GOTO[0, T] = 2，状态栈 [0, 2]，符号栈 [$T]，输入
+ id * id $ - ACTION[2, +] = r2（归约 E→T），弹出状态 2，状态栈 [0]，GOTO[0, E] = 1，状态栈 [0, 1]，符号栈 [$E]，输入
+ id * id $ - ACTION[1, +] = s6（移进），状态栈 [0, 1, 6]，符号栈 [$E+]，输入
id * id $ - ACTION[6, id] = s5（移进），状态栈 [0, 1, 6, 5]，符号栈 [$E+id]，输入
* id $ - ACTION[5, *] = r6（归约 F→id），弹出状态 5，状态栈 [0, 1, 6]，GOTO[6, F] = 3，状态栈 [0, 1, 6, 3]，符号栈 [$E+F]，输入
* id $ - ACTION[3, *] = r4（归约 T→F），弹出状态 3，状态栈 [0, 1, 6]，GOTO[6, T] = 9，状态栈 [0, 1, 6, 9]，符号栈 [$E+T]，输入
* id $ - ACTION[9, ] = s7（移进），状态栈 [0, 1, 6, 9, 7]，符号栈 [$E+T]，输入
id $ - ACTION[7, id] = s5（移进），状态栈 [0, 1, 6, 9, 7, 5]，符号栈 [$E+T*id]，输入
$ - ACTION[5, $] = r6（归约 F→id），弹出状态 5，状态栈 [0, 1, 6, 9, 7]，GOTO[7, F] = 10，状态栈 [0, 1, 6, 9, 7, 10]，符号栈 [$E+T*F]，输入
$ - ACTION[10, $] = r5（归约 T→T*F），弹出状态 7, 10，状态栈 [0, 1, 6, 9]，GOTO[6, T] = 9，状态栈 [0, 1, 6, 9]，符号栈 [$E+T]，输入
$ - ACTION[9, $] = r3（归约 E→E+T），弹出状态 6, 9，状态栈 [0, 1]，GOTO[0, E] = 1，状态栈 [0, 1]，符号栈 [$E]，输入
$ - ACTION[1, $] = accept（接受），分析成功
5. LR分析器的分类
5.1 LR(0)分析器
- 基本思想：不需要向前看符号，只根据当前状态决定操作
- 优点：分析表小，实现简单
- 缺点：能力弱，许多实用文法不是LR(0)的
- 适用场景：仅适用于简单文法
5.2 SLR(1)分析器（简单LR分析器）
- 基本思想：在LR(0)的基础上，使用FOLLOW集来解决冲突
- 优点：分析表小，实现相对简单
- 缺点：能力有限，某些文法仍会有冲突
- 适用场景：适用于大多数程序设计语言的文法
5.3 LR(1)分析器
- 基本思想：使用向前看符号来解决冲突，每个项都包含一个展望符
- 优点：能力强，可以处理几乎所有上下文无关文法
- 缺点：分析表大，实现复杂
- 适用场景：适用于复杂文法，需要强大分析能力的场合
5.4 LALR(1)分析器（向前看LR分析器）
- 基本思想：将LR(1)中具有相同核心的项集合并，减少分析表大小
- 优点：分析表大小与SLR相当，能力接近LR(1)
- 缺点：可能会引入一些归约-归约冲突
- 适用场景：适用于大多数现代编译器，是实际应用的首选
5.5 比较
| 分析器类型 | 能力 | 分析表大小 | 实现复杂度 | 实际应用 |
|---|---|---|---|---|
| LR(0) | 弱 | 小 | 低 | 很少 |
| SLR(1) | 中 | 小 | 低 | 较少 |
| LR(1) | 强 | 大 | 高 | 较少 |
| LALR(1) | 强 | 小 | 中 | 广泛 |
6. 项和项集
6.1 LR(0)项
LR(0)项是一个产生式加上一个点，表示分析过程中的一个状态。例如：
A → ·α：表示等待分析 αA → α·：表示 α 已经分析完成，可以归约
6.2 扩展文法
为了处理开始符号，通常需要将文法扩展，添加一个新的开始符号 S'，并添加产生式 S' → S，其中 S 是原文法的开始符号。
6.3 项集和项集规范族
- 项集：是一组LR(0)项的集合，表示分析过程中的一个状态
- 项集规范族：是由所有可能的项集组成的集合，构成一个有限自动机
6.4 闭包运算
闭包运算是构建项集的核心操作，它的作用是：
- 对于项集中的每个项
A → α·Bβ，将所有B → ·γ形式的项添加到项集中 - 重复这个过程直到项集不再变化
6.5 GOTO运算
GOTO运算是从一个项集转移到另一个项集的操作，它的定义是：
GOTO(I, X) = CLOSURE({ A → αX·β | A → α·Xβ ∈ I })
其中，I 是一个项集，X 是一个文法符号，CLOSURE 是闭包运算。
7. LR分析表的构建
7.1 LR(0)分析表的构建
- 构建项集规范族：使用闭包和GOTO运算构建所有可能的项集
- 构建ACTION表：
- 对于项集 I 中的每个项
A → α·aβ，如果 GOTO(I, a) = J，则 ACTION[I, a] = sJ（移进） - 对于项集 I 中的每个项
A → α·，如果 A 不是开始符号，则对于所有输入符号 a，ACTION[I, a] = rk（归约，k是产生式编号） - 对于项集 I 中的项
S' → S·，则 ACTION[I, $] = accept（接受）
- 对于项集 I 中的每个项
- 构建GOTO表：
- 对于每个项集 I 和非终结符 A，如果 GOTO(I, A) = J，则 GOTO[I, A] = J
7.2 SLR(1)分析表的构建
SLR(1)分析表的构建与LR(0)类似，但在处理归约操作时使用FOLLOW集：
- 对于项集 I 中的每个项
A → α·，如果 A 不是开始符号，则对于所有 a ∈ FOLLOW(A)，ACTION[I, a] = rk（归约）
7.3 LR(1)分析表的构建
LR(1)分析表的构建更复杂，需要考虑向前看符号：
- 构建LR(1)项：每个项都包含一个展望符，形式为
[A → α·β, a] - 构建项集规范族：使用LR(1)闭包和GOTO运算
- 构建分析表：根据LR(1)项集构建ACTION和GOTO表
7.4 LALR(1)分析表的构建
LALR(1)分析表的构建步骤：
- 构建LR(1)项集规范族
- 合并具有相同核心的项集：核心是项中去掉展望符后的部分
- 构建分析表：根据合并后的项集构建ACTION和GOTO表
8. 冲突处理
8.1 移进-归约冲突
移进-归约冲突是指在某个状态下，既可以移进当前输入符号，又可以归约某个产生式。
解决方法：
- LR(0)：无法解决，文法不是LR(0)的
- SLR(1)：如果输入符号不在归约产生式左部的FOLLOW集中，则选择移进
- LR(1)：如果输入符号不是归约项的展望符，则选择移进
- LALR(1)：与LR(1)类似
8.2 归约-归约冲突
归约-归约冲突是指在某个状态下，可以归约多个不同的产生式。
解决方法：
- LR(0)：无法解决，文法不是LR(0)的
- SLR(1)：如果输入符号只在一个产生式左部的FOLLOW集中，则选择该产生式
- LR(1)：如果输入符号只在一个归约项的展望符集中，则选择该产生式
- LALR(1)：与LR(1)类似，但可能会引入新的冲突
9. 自测题
LR分析器的基本原理是什么？它与LL分析器有什么区别？
移进-归约分析的基本操作有哪些？
LR分析器有哪些分类？它们的特点是什么？
什么是项和项集？它们在LR分析中的作用是什么？
解释LR分析表的结构和构建方法。
10. 小结
在本集中，我们介绍了LR分析器的基本原理、分类和工作过程。LR分析器是一种强大的自底向上语法分析方法，它通过移进-归约操作来构建最左归约，具有分析能力强、速度快、错误定位准确等优点。LR分析器分为LR(0)、SLR(1)、LR(1)和LALR(1)等类型，其中LALR(1)是实际应用中最常用的。我们还介绍了项集、项集规范族、分析表等核心概念，为后续学习LR分析器的具体实现做了准备。
11. 下集预告
下一集将介绍 LR(0)和SLR(1)分析器，详细讲解它们的项集构建、分析表生成和工作过程，通过具体的例子展示如何使用这些分析器进行语法分析。
12. 参考资料
- 《编译原理》（龙书），Alfred V. Aho 等著
- 《编译原理教程》，蒋立源等著
- 《编译器设计》，Alexander A. Stepanov 等著
- LR parser - Wikipedia：https://en.wikipedia.org/wiki/LR_parser
- Shift-reduce parser - Wikipedia：https://en.wikipedia.org/wiki/Shift-reduce_parser