深入解析 SLR、CLR 和 LALR 解析器

解析是编译器设计中的一项基础技术，它能帮助我们分析和验证编程语言的语法。解析器会将一系列标记转换为结构化的格式，通常表现为解析树。在众多的解析技术中，LR 解析器因其高效性和处理广泛语法类的能力而被广泛应用。

LR 解析器是一种自底向上的解析器，它们从叶子节点（标记）开始构建解析树，直到根节点（开始符号）。它们具有确定性，能够高效地处理上下文无关文法。LR 解析器主要包括以下三种类型：

• SLR (Simple LR) 解析器 – 最基础的 LR 解析器，使用 LR(0) 项目和 FOLLOW 集合来构造解析表。
• CLR (Canonical LR) 解析器 – 功能更强大的解析器，利用 LR(1) 项目来解决冲突并识别更广泛的文法。
• LALR (Look-Ahead LR) 解析器 – CLR 的内存优化版本，通过合并状态来减小表的大小，同时保留了大部分解析能力。

这三种解析器在复杂性、能力和效率上各不相同。

!clr-slr-lalrLR 解析器框图

自底向上解析

自底向上解析是编译器中用于分析和理解代码的一种方法。它从程序最小的部分（标记）开始，逐步构建出完整的结构（语法树）。

在自底向上解析中：

• 从左到右读取输入。
• 根据语法规则将标记组合成更大的结构。
• 持续组合这些结构，直到形成最终结果（开始符号）。

最强大的自底向上解析器是 LR 解析器（用于 C 和 Java 等编程语言）。例如：

• SLR (Simple LR) – 基础且易于实现。
• CLR (Canonical LR) – 更强大但也更复杂。
• LALR (Look-Ahead LR) – 结合了两者的优点，在能力和效率之间取得了平衡。

阅读更多关于 自底向上解析 的内容。

!parser_21

SLR(1) 解析

SLR(1) 代表简单 LR 解析。它与 LR(0) 解析相似，因为 LR(0) 解析只需要规范项目来构造解析表。LR(0) 解析器与 SLR 解析器唯一的区别在于存在移进-归约冲突的可能性，因为在 LR(0) 解析表中，我们要对所有终结符状态执行归约操作。在 LR(0) 解析中，解析器有时会在不该归约的时候错误地归约，导致移进-归约冲突。SLR(1) 通过仅允许在与产生式左部 (LHS) 的 FOLLOW 集相匹配的位置执行归约操作来解决这个问题。这意味着 SLR(1) 使用 FOLLOW 集合做出更好的决策，从而减少冲突。

构造 SLR(1) 解析表

> 1. 为 G′ 构造 LR(0) 项目集的集合。

> 2. 对于由 Ii 构造的 CFSM 的每个状态 i：

> 1. 如果 [A → α • aβ] ∈ Ii 且 GOTO(Ii, a) = Ij,

> ⇒ ACTION[i, a] ← “shift j”, ∀a ≠ $。

> 2. 如果 [A → α •] ∈ Ii, A ≠ S′,

> ⇒ ACTION[i, a] ← “reduce A → α”, ∀a ∈ FOLLOW(A)。

> 3. 如果 [S′ → S • $] ∈ Ii,

> ⇒ ACTION[i, $] ← “accept”。

> 3. 对于每个状态 i：

> – 如果 GOTO(Ii, A) = Ij,

> ⇒ GOTO[i, A] ← j。

> 4. 将 ACTION 和 GOTO 中未定义的条目设为 “error”。

> 5. 解析器的初始状态 s₀ 是 CLOSURE([S′ → •S$])。

• 如果解析表中存在多个条目，则称其为冲突。

示例：

Consider the grammar E -> T+E | T
                     T ->id
    Augmented grammar - E’ -> E
                E -> T+E | T
                T -> id

!<a href="https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2017/02/parser16.png">parser16