1. 简介
在本篇文章中，我们将深入探讨两种在工业界和学术界广泛应用的语法解析器：LL 解析器 和 LR 解析器。我们将通过语法理论对比它们的特性，帮助你理解它们的本质差异。
LL 和 LR 是两种主流的语法分析方法，适用于不同的语法规则和解析场景。理解它们之间的区别，有助于在设计语言、构建编译器或解析器时做出更合适的技术选型。
2. 编译流程概述
LL 和 LR 解析器都属于编译过程中的语法分析阶段。一个编译器通常会通过多个抽象层次处理源代码，每个阶段都有不同的输入和输出。最终输出是为特定架构优化的机器码。
经典的编译流程如下图所示：
其中，词法分析器输出的是 token 流，而语法分析器（即解析器）则负责生成语法树。解析器实现方式、语法树构造方式以及所支持的语法规则种类，决定了 LL 和 LR 的根本差异。
3. LL 与 LR 的对比
3.1. 语法树构建方式
✅ LL 解析器采用自顶向下（Top-down）方式构建语法树。
- 从根节点开始，按前序方式逐层展开。
- 目标是找到输入字符串的最左推导（leftmost derivation）。
- 例如，对于产生式规则
{S → SS, S → a}，输入字符串为aaaa，一个可能的推导路径是：S ⇒ SS ⇒ SSS ⇒ aSS ⇒ aaS ⇒ aaaa
LL 解析器在每一步中选择一个非终结符，并尝试匹配其产生式。如果解析器只需向前看 k 个符号即可确定正确的产生式，则称为 LL(k) 解析器，常见值为 LL(1)。
❌ LL 的缺点：无法处理左递归语法规则，否则可能导致无限循环。
✅ LR 解析器采用自底向上（Bottom-up）方式构建语法树。
从叶子节点开始，逐步向上归约（reduce）直到根节点。
目标是将输入字符串归约为起始符号，或构造一个最右推导的逆过程。
例如，对于规则
{E → T, T → F, T → T * F, F → id}，输入字符串为id * id，推导过程如下：id * id ⇒ F * id ⇒ T * id ⇒ T * F ⇒ E
LR 解析器通过“移进-归约”操作完成解析，归约时识别的子串称为“句柄”（handle）。
✅ LR 的优点：支持左递归语法规则，且能处理的语法规则集比 LL 更广。
3.2. 支持的语法规则类型
LL 和 LR 解析器对语法规则有各自的要求：
LL(1) 语法规则
LL(1) 语法必须满足以下条件：
- 对于任意非终结符 A 的两个不同产生式
A → α | β：FIRST(α) ∩ FIRST(β) = ∅（无冲突）- 至多一个产生式可以推导出空串
- 若 β 推导出空串，则
FIRST(α) ∩ FOLLOW(A) = ∅
这些条件确保在解析过程中不会出现歧义。
LR(1) 语法规则
LR 语法的种类较多，常见包括：
- **SLR(1)**：最基础的 LR 解析器，能力较弱
- **LR(1)**：能力最强的 LR 解析器
- **LALR(1)**：在 LR(1) 基础上合并状态，平衡性能与能力
LR 解析器使用“状态自动机”和“项目集”来识别句柄。其核心要求是：
- 不存在“移进-归约”冲突（shift-reduce conflict）
- 不存在“归约-归约”冲突（reduce-reduce conflict）
✅ LR 的优势：能接受的语法规则集比 LL 更大，LL 是 LR 的真子集。
3.3. 各自的局限性
LL 解析器的限制
- 无法处理左递归语法规则
- 例如规则
S → SS会导致无限递归 - 递归下降解析器虽然能处理部分非 LL 规则，但效率低，最坏情况下可能指数级时间复杂度
LR 解析器的限制
- 无法处理歧义语法规则
- 但有一种特殊类型的 LR 解析器 —— 算符优先解析器（Operator-Precedence Parser） 可以处理某些算符优先文法（Operator Grammar）
- 通过定义操作符优先级解决歧义问题
4. 总结
| 特性 | LL 解析器 | LR 解析器 |
|---|---|---|
| 构建方式 | 自顶向下 | 自底向上 |
| 语法树构造 | 最左推导 | 最右推导的逆过程 |
| 支持左递归 | ❌ | ✅ |
| 支持的语法规则 | 较少（LL 是 LR 的子集） | 更多 |
| 处理歧义 | ❌ | ✅（仅限特定算符优先文法） |
| 实现难度 | 相对简单 | 相对复杂 |
| 常见类型 | LL(1) | SLR(1), LALR(1), LR(1) |
✅ LL 适合语法结构简单、可预测性强的语言解析，例如某些配置文件格式、DSL。
✅ LR 更适合复杂语言（如 C、Java）的语法解析，尤其在工业级编译器中广泛使用。
⚠️ 选择建议：
- 如果你正在设计一种新语言，且希望手动编写解析器，LL(1) 是一个不错起点。
- 如果你追求更强的表达能力，或希望支持左递归、复杂结构，建议使用 LR 系列解析器（如 LALR(1) 或 LR(1)）。
📌 术语说明：
- FIRST 集合：表示某个符号串可以推导出的第一个终结符集合
- FOLLOW 集合：表示某个非终结符后可能紧跟的终结符集合
- 句柄（Handle）：在 LR 解析中，当前可归约的子串
- 算符优先文法（Operator Grammar）：一种特殊文法，用于支持算符优先解析器处理部分歧义情况
如果你正在开发一个编译器、解释器或 DSL，LL 和 LR 是你必须掌握的基础知识。选择合适的解析器类型，将直接影响你实现语言的灵活性和效率。