第57集：LR(1)和LALR(1)分析器

学习目标

• 掌握LR(1)分析器的工作原理
• 理解LR(1)项和项集的构建方法
• 掌握LALR(1)分析器的基本思想
• 了解LR(1)和LALR(1)分析表的生成过程
• 理解LALR(1)分析器的优势和局限性

1. LR(1)分析器详解

1.1 基本思想

LR(1)分析器是对SLR(1)分析器的进一步改进，它的基本思想是：在每个LR(0)项中添加一个展望符（lookahead），用于更精确地决定何时进行归约操作。展望符表示在归约后可能出现的下一个终结符。

1.2 LR(1)项

LR(1)项是一个LR(0)项加上一个展望符集合，表示为 [A → α·β, a]，其中：

• A → α·β 是一个LR(0)项
• a 是一个终结符或 $，表示展望符

1.3 LR(1)闭包运算

LR(1)闭包运算与LR(0)类似，但需要考虑展望符的传递：

算法：

function CLOSURE(I) {
    J = I
    repeat {
        for each item [A → α·Bβ, a] in J {
            for each production B → γ in G {
                for each b in FIRST(βa) {
                    if item [B → ·γ, b] not in J {
                        add [B → ·γ, b] to J
                    }
                }
            }
        }
    } until J doesn't change
    return J
}

1.4 LR(1) GOTO运算

LR(1) GOTO运算与LR(0)类似，但操作的是LR(1)项：

GOTO(I, X) = CLOSURE({ [A → αX·β, a] | [A → α·Xβ, a] ∈ I })

1.5 LR(1)项集规范族的构建

LR(1)项集规范族的构建与LR(0)类似，但使用LR(1)闭包和GOTO运算：

function ITEM_SETS(G') {
    C = { CLOSURE({ [S' → ·S, $] }) }
    repeat {
        for each item set I in C {
            for each grammar symbol X {
                if GOTO(I, X) is not empty and not in C {
                    add GOTO(I, X) to C
                }
            }
        }
    } until C doesn't change
    return C
}

1.6 LR(1)分析表的生成

LR(1)分析表的生成与SLR(1)类似，但使用LR(1)项的展望符：

ACTION表生成规则：

• 对于项集 I 中的每个项 [A → α·aβ, b]，如果 GOTO(I, a) = J，则 ACTION[I, a] = sJ（移进）
• 对于项集 I 中的每个项 [A → α·, a]，如果 A 不是开始符号，则 ACTION[I, a] = rk（归约，k是产生式编号）
• 对于项集 I 中的项 [S' → S·, $]，则 ACTION[I, $] = accept（接受）

GOTO表生成规则：

• 对于每个项集 I 和非终结符 A，如果 GOTO(I, A) = J，则 GOTO[I, A] = J

1.7 LR(1)分析器的优势

LR(1)分析器的主要优势是它可以处理SLR(1)无法处理的一些冲突情况。例如，对于以下文法：

S → A | B
A → a
B → a

SLR(1)分析器会在状态中产生归约-归约冲突，因为 FOLLOW(A) = FOLLOW(B) = { $ }，当输入符号是 $ 时，无法决定是归约到 A 还是 B。而LR(1)分析器通过展望符可以区分这种情况。

1.8 示例：LR(1)项集构建

考虑以下文法：

G: S → A | B
A → a
B → a

扩展文法：

G': S' → S
S → A | B
A → a
B → a

LR(1)项集构建：

1. 初始项集 I0：

   I0 = CLOSURE({ [S' → ·S, $] })

   应用闭包运算：

   I0:
   [S' → ·S, $]
   [S → ·A, $]
   [S → ·B, $]
   [A → ·a, $]  // 因为 FIRST(A$) = {a}
   [B → ·a, $]  // 因为 FIRST(B$) = {a}

2. **计算 GOTO(I0, S)**：

   I1 = GOTO(I0, S) = CLOSURE({ [S' → S·, $] })

   I1:
   [S' → S·, $]

3. **计算 GOTO(I0, A)**：

   I2 = GOTO(I0, A) = CLOSURE({ [S → A·, $] })

   I2:
   [S → A·, $]

4. **计算 GOTO(I0, B)**：

   I3 = GOTO(I0, B) = CLOSURE({ [S → B·, $] })

   I3:
   [S → B·, $]

5. **计算 GOTO(I0, a)**：

   I4 = GOTO(I0, a) = CLOSURE({ [A → a·, $], [B → a·, $] })

   I4:
   [A → a·, $]
   [B → a·, $]

1.9 LR(1)分析表的生成

对于上面的例子，LR(1)分析表如下：

注意： 在状态4中，当输入符号是 $ 时，既可以归约 A→a，又可以归约 B→a，产生归约-归约冲突。这是因为这两个产生式的展望符都是 $。

2. LALR(1)分析器详解

2.1 基本思想

LALR(1)分析器是对LR(1)分析器的优化，它的基本思想是：将LR(1)项集中具有相同核心（即去掉展望符后的LR(0)项集）的项集合并，以减少分析表的大小，同时保持LR(1)分析器的大部分能力。

2.2 核心的概念

LR(1)项集的核心是指去掉展望符后的LR(0)项集。例如，对于LR(1)项集 { [A → α·β, a], [B → γ·δ, b] }，其核心是 { A → α·β, B → γ·δ }。

2.3 LALR(1)项集的构建

LALR(1)项集的构建步骤：

1. 构建LR(1)项集规范族
2. 合并具有相同核心的LR(1)项集：将所有具有相同核心的LR(1)项集合并为一个LALR(1)项集，合并后的项集的展望符是各个LR(1)项集展望符的并集
3. 构建LALR(1)分析表：使用合并后的项集生成分析表

2.4 LALR(1)分析表的生成

LALR(1)分析表的生成与LR(1)类似，但使用合并后的项集：

ACTION表生成规则：

• 对于项集 I 中的每个项 [A → α·aβ, b]，如果 GOTO(I, a) = J，则 ACTION[I, a] = sJ（移进）
• 对于项集 I 中的每个项 [A → α·, a]，如果 A 不是开始符号，则 ACTION[I, a] = rk（归约，k是产生式编号）
• 对于项集 I 中的项 [S' → S·, $]，则 ACTION[I, $] = accept（接受）

GOTO表生成规则：

• 对于每个项集 I 和非终结符 A，如果 GOTO(I, A) = J，则 GOTO[I, A] = J

2.5 LALR(1)分析器的优势

LALR(1)分析器的主要优势包括：

• 分析表大小适中：与SLR(1)分析表大小相当，远小于LR(1)分析表
• 分析能力强：可以处理大多数实用的上下文无关文法
• 实现相对简单：相比LR(1)分析器，实现复杂度较低
• 错误检测及时：与LR(1)分析器一样，可以在错误发生后的第一个符号处检测到错误

2.6 LALR(1)分析器的局限性

LALR(1)分析器的主要局限性是：在合并具有相同核心的LR(1)项集时，可能会引入新的归约-归约冲突，即使原来的LR(1)项集没有冲突。

2.7 示例：LALR(1)项集合并

考虑以下文法：

G: S → A
A → aB | bC
B → c | a
C → c | b

LR(1)项集：

• 项集 I1：{ [A → a·B, $], [B → ·c, $], [B → ·a, $] }
• 项集 I2：{ [A → b·C, $], [C → ·c, $], [C → ·b, $] }

这两个项集的核心不同，所以不会合并。

另一个例子：

G: S → A | B
A → a
B → b

LR(1)项集：

• 项集 I1：{ [A → a·, $] }
• 项集 I2：{ [B → b·, $] }

这两个项集的核心不同，所以不会合并。

3. LR(1)与LALR(1)的比较

3.1 分析能力

• LR(1)分析器：能力最强，可以处理几乎所有上下文无关文法
• LALR(1)分析器：能力略弱于LR(1)，但可以处理大多数实用的上下文无关文法
• SLR(1)分析器：能力较弱，只能处理部分上下文无关文法
• LR(0)分析器：能力最弱，只能处理极少数上下文无关文法

3.2 分析表大小

• LR(1)分析器：分析表最大，可能是LALR(1)的数倍
• LALR(1)分析器：分析表大小与SLR(1)相当
• SLR(1)分析器：分析表较小
• LR(0)分析器：分析表最小

3.3 实现复杂度

• LR(1)分析器：实现最复杂
• LALR(1)分析器：实现复杂度适中
• SLR(1)分析器：实现相对简单
• LR(0)分析器：实现最简单

3.4 实际应用

• LR(1)分析器：由于分析表过大，实际应用较少
• LALR(1)分析器：是实际应用的首选，被广泛用于现代编译器
• SLR(1)分析器：适用于简单语言，实现简单
• LR(0)分析器：主要用于教学，实际应用很少

4. 实战案例：构建LALR(1)分析器

4.1 文法定义

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

4.2 扩展文法

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

4.3 构建LR(1)项集规范族

由于篇幅限制，这里省略LR(1)项集的详细构建过程。构建完成后，我们会得到多个LR(1)项集，其中一些具有相同的核心。

4.4 合并具有相同核心的项集

例如，以下两个LR(1)项集具有相同的核心：

项集 I5：

[F → id·, +]
[F → id·, *]
[F → id·, )]
[F → id·, $]

**项集 I5'**：

[F → id·, +]
[F → id·, *]
[F → id·, )]
[F → id·, $]

它们的核心都是 { F → id· }，所以可以合并为一个LALR(1)项集。

4.5 构建LALR(1)分析表

合并后的LALR(1)分析表与SLR(1)分析表类似，但具有更精确的归约条件。对于上面的表达式文法，LALR(1)分析表与SLR(1)分析表相同，因为该文法是SLR(1)的。

4.6 分析示例

以输入串 id + id * id 为例，LALR(1)分析器的分析过程与SLR(1)分析器相同：

步骤：

1. 初始状态：状态栈 [0]，符号栈 [$]，输入 id + id * id $
2. ACTION[0, id] = s5（移进），状态栈 [0, 5]，符号栈 [$id]，输入 + id * id $
3. ACTION[5, +] = r6（归约 F→id），弹出状态 5，状态栈 [0]，GOTO[0, F] = 3，状态栈 [0, 3]，符号栈 [$F]，输入 + id * id $
4. ACTION[3, +] = r4（归约 T→F），弹出状态 3，状态栈 [0]，GOTO[0, T] = 2，状态栈 [0, 2]，符号栈 [$T]，输入 + id * id $
5. ACTION[2, +] = r2（归约 E→T），弹出状态 2，状态栈 [0]，GOTO[0, E] = 1，状态栈 [0, 1]，符号栈 [$E]，输入 + id * id $
6. ACTION[1, +] = s6（移进），状态栈 [0, 1, 6]，符号栈 [$E+]，输入 id * id $
7. ACTION[6, id] = s5（移进），状态栈 [0, 1, 6, 5]，符号栈 [$E+id]，输入 * id $
8. ACTION[5, *] = r6（归约 F→id），弹出状态 5，状态栈 [0, 1, 6]，GOTO[6, F] = 3，状态栈 [0, 1, 6, 3]，符号栈 [$E+F]，输入 * id $
9. ACTION[3, *] = r4（归约 T→F），弹出状态 3，状态栈 [0, 1, 6]，GOTO[6, T] = 9，状态栈 [0, 1, 6, 9]，符号栈 [$E+T]，输入 * id $
10. ACTION[9, ] = s7（移进），状态栈 [0, 1, 6, 9, 7]，符号栈 [$E+T]，输入 id $
11. ACTION[7, id] = s5（移进），状态栈 [0, 1, 6, 9, 7, 5]，符号栈 [$E+T*id]，输入 $
12. ACTION[5, $] = r6（归约 F→id），弹出状态 5，状态栈 [0, 1, 6, 9, 7]，GOTO[7, F] = 10，状态栈 [0, 1, 6, 9, 7, 10]，符号栈 [$E+T*F]，输入 $
13. ACTION[10, $] = r5（归约 T→T*F），弹出状态 7, 10，状态栈 [0, 1, 6, 9]，GOTO[6, T] = 9，状态栈 [0, 1, 6, 9]，符号栈 [$E+T]，输入 $
14. ACTION[9, $] = r3（归约 E→E+T），弹出状态 6, 9，状态栈 [0, 1]，GOTO[0, E] = 1，状态栈 [0, 1]，符号栈 [$E]，输入 $
15. ACTION[1, $] = acc（接受），分析成功

5. LALR(1)分析器的实现工具

5.1 Yacc/Bison

Yacc（Yet Another Compiler-Compiler）是一个经典的LALR(1)分析器生成工具，由Stephen C. Johnson在1975年开发。Bison是Yacc的GNU实现，是目前最常用的LALR(1)分析器生成工具之一。

特点：

• 生成LALR(1)分析器
• 支持文法规则和动作代码
• 提供错误处理机制
• 与词法分析器Flex配合使用

5.2 其他工具

• ANTLR：生成LL(*)分析器，也支持LALR(1)
• JavaCC：生成LL(k)分析器
• Happy：Haskell的LALR(1)分析器生成工具
• Ply：Python的lex/yacc实现

6. 自测题

1. LR(1)分析器与SLR(1)分析器的主要区别是什么？

2. 什么是LR(1)项？它与LR(0)项有什么不同？

3. LALR(1)分析器的基本思想是什么？它如何减少分析表的大小？

4. 比较LR(1)、LALR(1)、SLR(1)和LR(0)分析器的分析能力和分析表大小。

5. 为什么LALR(1)分析器在实际应用中被广泛使用？

7. 小结

在本集中，我们详细介绍了LR(1)和LALR(1)分析器的工作原理、项集构建和分析表生成方法。LR(1)分析器通过在每个项中添加展望符，实现了更精确的归约决策，能够处理SLR(1)无法处理的冲突情况。LALR(1)分析器通过合并具有相同核心的LR(1)项集，在保持LR(1)分析器大部分能力的同时，显著减少了分析表的大小，成为实际应用中的首选分析方法。

8. 下集预告

下一集将介绍 语法分析器的错误处理，详细讲解语法分析过程中的错误检测、错误恢复策略和错误信息生成方法，帮助我们构建更加健壮的编译器前端。

9. 参考资料

1. 《编译原理》（龙书），Alfred V. Aho 等著
2. 《编译原理教程》，蒋立源等著
3. 《编译器设计》，Alexander A. Stepanov 等著
4. LR parser - Wikipedia：https://en.wikipedia.org/wiki/LR_parser
5. Lookahead LR parser - Wikipedia：https://en.wikipedia.org/wiki/Lookahead_LR_parser
6. Yacc - Wikipedia：https://en.wikipedia.org/wiki/Yacc
7. Bison - GNU Project：https://www.gnu.org/software/bison/