LR分析

LR 分析概述

什么是 LR 分析

LR 分析（LR Parsing）是一种强大的自底向上语法分析方法。

LR 的含义：

• L（Left-to-right）：从左到右扫描输入
• R（Rightmost derivation in reverse）：构造最右推导的逆序（规范归约）
• (k)：向前看 $k$ 个输入符号（通常 $k=0$ 或 $k=1$）

LR 分析是最右推导的逆过程，也就是规范归约。

LR 分析的基本思想

自底向上分析

从输入串（叶节点）出发，逐步归约（Reduce）到文法的开始符号（根节点）。

核心问题：

1. 何时归约？（识别句柄）
2. 用哪个产生式归约？

句柄（Handle）

句柄是句型中最左边的直接短语，也就是下一步应该归约的部分。

回顾：如果有推导 $S\Rightarrow^\alpha A\delta\Rightarrow\alpha\beta\delta$，其中 $A\rightarrow\beta$，则 $\beta$ 是句型 $\alpha\beta\delta$ 相对于产生式 $A\rightarrow\beta$ 的*句柄。

移进-归约分析

LR 分析使用移进-归约技术：

• 移进（Shift）：将输入符号压入栈
• 归约（Reduce）：将栈顶的符号串（句柄）按某个产生式归约为非终结符
• 接受（Accept）：归约到开始符号且输入读完
• 报错（Error）：发现语法错误

LR 分析器的结构

LR 分析器由以下部分组成：

┌─────────────┐
│   输入缓冲区   │ a₁ a₂ a₃ ... aₙ $
└──────┬──────┘
       │
       ↓
┌─────────────────────────────────┐
│        LR 分析程序               │
│    (驱动程序 + ACTION/GOTO表)    │
└─────────┬───────────────────────┘
          │
          ↓
    ┌─────────┐
    │  符号栈  │ s₀ X₁ s₁ X₂ s₂ ... Xₘ sₘ
    └─────────┘

组成部分

1. 输入缓冲区：存储待分析的输入串（以 $ 结束）
2. 符号栈：存储文法符号和状态，格式为 s₀ X₁ s₁ X₂ s₂ ... Xₘ sₘ
   • $X_i$：文法符号（终结符或非终结符）
   • $s_i$：状态
3. LR 分析表：包含两部分
   • ACTION 表：$\text{ACTION}[s, a]$ 指示在状态 $s$ 看到输入符号 $a$ 时的动作
   • GOTO 表：$\text{GOTO}[s, A]$ 指示归约后的状态转移

ACTION 表的动作类型

动作	表示	含义
移进 $s$	$s_n$	将输入符号和状态 $s_n$ 压入栈
归约 $r$	$r_n$	用第 $n$ 个产生式归约
接受	$\text{acc}$	分析成功，接受输入
报错	空（或error）	语法错误

LR 分析算法

输入：输入串 $w$，LR 分析表
输出：$w$ 的规范归约序列（最右推导的逆序）或错误信息

初始化：
    栈 = [s₀]  // s₀ 是初始状态
    输入指针 ip 指向 w 的第一个符号

repeat:
    s = 栈顶状态
    a = ip 指向的符号
    
    根据 ACTION[s, a] 执行动作：
    
    case sₙ (移进):
        将 a 和 sₙ 压入栈
        ip++
    
    case rₙ (归约):
        设第 n 个产生式为 A → β
        从栈顶弹出 |β| 个符号对（共 2|β| 个元素）
        设弹出后栈顶状态为 t
        查找 GOTO[t, A] = s'
        将 A 和 s' 压入栈
        输出: 用 A → β 归约
    
    case acc (接受):
        输出: 分析成功
        return
    
    case error (错误):
        输出: 语法错误
        调用错误处理程序
        return

until false

分析示例

文法：
$$
\begin{aligned}
(1)\ S &\rightarrow E \
(2)\ E &\rightarrow E + T \
(3)\ E &\rightarrow T \
(4)\ T &\rightarrow T * F \
(5)\ T &\rightarrow F \
(6)\ F &\rightarrow (E) \
(7)\ F &\rightarrow \text{id}
\end{aligned}
$$

输入：id + id * id

分析过程（假设已有 LR 分析表）：

步骤	栈	输入	动作
1	0	id+id*id$	s5（移进）
2	0 id 5	+id*id$	r7（用 F→id 归约）
3	0 F 3	+id*id$	r5（用 T→F 归约）
4	0 T 2	+id*id$	r3（用 E→T 归约）
5	0 E 1	+id*id$	s6（移进）
6	0 E 1 + 6	id*id$	s5（移进）
7	0 E 1 + 6 id 5	*id$	r7（用 F→id 归约）
8	0 E 1 + 6 F 3	*id$	r5（用 T→F 归约）
9	0 E 1 + 6 T 9	*id$	s7（移进）
10	0 E 1 + 6 T 9 * 7	id$	s5（移进）
11	0 E 1 + 6 T 9 * 7 id 5	$	r7（用 F→id 归约）
12	0 E 1 + 6 T 9 * 7 F 10	$	r4（用 T→T*F 归约）
13	0 E 1 + 6 T 9	$	r2（用 E→E+T 归约）
14	0 E 1	$	acc（接受）

LR 文法的分类

根据分析能力的不同，LR 分析分为几类：

类型	全称	特点	分析能力
LR(0)	LR(0) 分析	不需要向前看，能力最弱	最弱
SLR(1)	Simple LR(1)	向前看 1 个符号，使用 FOLLOW 集	较弱
LR(1)	Canonical LR(1)	向前看 1 个符号，完整的 LR(1) 项目	最强
LALR(1)	Look-Ahead LR(1)	LR(1) 的简化版，状态数较少	较强

关系：
$$
\text{LR}(0)\subset\text{SLR}(1)\subset\text{LALR}(1)\subset\text{LR}(1)\subset\text{上下文无关文法}
$$

实践中：

• LR(0)：理论基础，实际很少用
• SLR(1)：简单，但能力有限
• LALR(1)：最常用，Yacc/Bison 使用的方法
• LR(1)：能力最强，但状态数太多（可达数千个）

---

LR(0) 分析

LR(0) 是最基础的 LR 分析方法，它不需要向前看输入符号。

LR(0) 项目（Item）

定义

LR(0) 项目是在产生式右部的某个位置添加一个点 ·，表示当前的分析进度。

对于产生式 $A\rightarrow XYZ$，有 4 个 LR(0) 项目：

1. $A\rightarrow\cdot XYZ$（还没开始匹配）
2. $A\rightarrow X\cdot YZ$（已匹配 $X$）
3. $A\rightarrow XY\cdot Z$（已匹配 $XY$）
4. $A\rightarrow XYZ\cdot$（全部匹配完成，可以归约）

项目的分类

1. 移进项目：$A\rightarrow\alpha\cdot a\beta$（点后面是终结符 $a$）

   • 表示期望看到 $a$，准备移进

2. 归约项目：$A\rightarrow\alpha\cdot$（点在最右边）

   • 表示已匹配完整个右部，可以归约为 $A$

3. 待约项目：$A\rightarrow\alpha\cdot B\beta$（点后面是非终结符 $B$）

   • 表示期望推导出 $B$，需要考察 $B$ 的产生式

4. 初始项目：$S’\rightarrow\cdot S$（增广文法的初始项目）

增广文法（Augmented Grammar）

为了处理接受状态，我们引入增广文法。

原文法：开始符号为 $S$

增广文法：引入新的开始符号 $S’$，添加产生式：
$$
S’\rightarrow S
$$

作用：当归约到 $S’\rightarrow S\cdot$ 且输入为 $ 时，表示接受。

项目集闭包（Closure）

定义

对于项目集 $I$，其闭包 $\text{CLOSURE}(I)$ 是通过不断添加新项目得到的：

初始：$\text{CLOSURE}(I)=I$

迭代规则：对于 $\text{CLOSURE}(I)$ 中的每个项目 $A\rightarrow\alpha\cdot B\beta$（点后面是非终结符 $B$）：

• 对于 $B$ 的每个产生式 $B\rightarrow\gamma$
• 将项目 $B\rightarrow\cdot\gamma$ 加入 $\text{CLOSURE}(I)$（如果还不存在）

重复，直到不再有新项目加入。

算法

def CLOSURE(I):
    J = I.copy()
    repeat:
        for each 项目 A → α·Bβ in J:
            if B 是非终结符:
                for each 产生式 B → γ:
                    if B → ·γ not in J:
                        J.add(B → ·γ)
    until J 不再变化
    return J

示例

文法（增广）：
$$
\begin{aligned}
S’ &\rightarrow E \
E &\rightarrow E + T\ |\ T \
T &\rightarrow T * F\ |\ F \
F &\rightarrow (E)\ |\ \text{id}
\end{aligned}
$$

计算 $\text{CLOSURE}({S’\rightarrow\cdot E})$：

步骤 1：初始项目集 ${S’\rightarrow\cdot E}$

步骤 2：$S’\rightarrow\cdot E$ 点后是 $E$，添加 $E$ 的产生式：

• $E\rightarrow\cdot E + T$
• $E\rightarrow\cdot T$

步骤 3：$E\rightarrow\cdot E + T$ 点后是 $E$（已有）；$E\rightarrow\cdot T$ 点后是 $T$，添加 $T$ 的产生式：

• $T\rightarrow\cdot T * F$
• $T\rightarrow\cdot F$

步骤 4：继续，添加 $F$ 的产生式：

• $F\rightarrow\cdot(E)$
• $F\rightarrow\cdot\text{id}$

结果：
$$
\text{CLOSURE}({S’\rightarrow\cdot E})=\left{
\begin{aligned}
&S’\rightarrow\cdot E \
&E\rightarrow\cdot E + T \
&E\rightarrow\cdot T \
&T\rightarrow\cdot T * F \
&T\rightarrow\cdot F \
&F\rightarrow\cdot(E) \
&F\rightarrow\cdot\text{id}
\end{aligned}
\right}
$$

---

转移函数（GOTO）

定义

$\text{GOTO}(I, X)$ 表示从项目集 $I$ 出发，看到符号 $X$（终结符或非终结符）后转移到的新项目集。

算法：

def GOTO(I, X):
    J = {}
    for each 项目 A → α·Xβ in I:
        将项目 A → αX·β 加入 J
    return CLOSURE(J)

直观理解：

1. 从 $I$ 中找出所有点后面是 $X$ 的项目
2. 将这些项目的点向右移动一位（越过 $X$）
3. 对结果求闭包

示例

继续前面的例子，设：
$$
I_0=\text{CLOSURE}({S’\rightarrow\cdot E})=\left{
\begin{aligned}
&S’\rightarrow\cdot E \
&E\rightarrow\cdot E + T \
&E\rightarrow\cdot T \
&T\rightarrow\cdot T * F \
&T\rightarrow\cdot F \
&F\rightarrow\cdot(E) \
&F\rightarrow\cdot\text{id}
\end{aligned}
\right}
$$

计算 $\text{GOTO}(I_0, \text{id})$：

步骤 1：找出点后面是 id 的项目：

• $F\rightarrow\cdot\text{id}$

步骤 2：点向右移动：

• $F\rightarrow\text{id}\cdot$

步骤 3：求闭包（这里没有非终结符在点后，闭包就是自己）：
$$
\text{GOTO}(I_0, \text{id})={F\rightarrow\text{id}\cdot}
$$

---

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

项目集规范族（Canonical Collection of LR(0) Items）是所有可能的项目集的集合，对应 LR(0) 自动机的状态集。

构造算法

def构造LR0项目集规范族(G'):
    C = {CLOSURE({S' → ·S})}  // 初始项目集
    
    repeat:
        for each 项目集 I in C:
            for each 文法符号 X (终结符或非终结符):
                J = GOTO(I, X)
                if J 非空 and J not in C:
                    C.add(J)
    until C 不再变化
    
    return C

示例

文法（增广）：
$$
\begin{aligned}
(0)\ S’ &\rightarrow S \
(1)\ S &\rightarrow (S)S \
(2)\ S &\rightarrow\varepsilon
\end{aligned}
$$

构造过程：

$I_0$：
$$
\begin{aligned}
&S’\rightarrow\cdot S \
&S\rightarrow\cdot(S)S \
&S\rightarrow\cdot\varepsilon
\end{aligned}
$$

$I_1=\text{GOTO}(I_0, S)$：
$$
S’\rightarrow S\cdot
$$

$I_2=\text{GOTO}(I_0, ()$：
$$
\begin{aligned}
&S\rightarrow(\cdot S)S \
&S\rightarrow\cdot(S)S \
&S\rightarrow\cdot\varepsilon
\end{aligned}
$$

$I_3=\text{GOTO}(I_2, S)$：
$$
S\rightarrow(S\cdot)S
$$

$I_4=\text{GOTO}(I_3, ))$：
$$
\begin{aligned}
&S\rightarrow(S)\cdot S \
&S\rightarrow\cdot(S)S \
&S\rightarrow\cdot\varepsilon
\end{aligned}
$$

$I_5=\text{GOTO}(I_4, S)$：
$$
S\rightarrow(S)S\cdot
$$

$I_2=\text{GOTO}(I_4, ()$（已有，形成循环）

最终项目集规范族：${I_0, I_1, I_2, I_3, I_4, I_5}$

---

识别活前缀的有限自动机

活前缀（Viable Prefix）

活前缀是可能出现在移进-归约分析器的栈中的符号串前缀，即还有可能继续归约的前缀。

形式化定义：符号串 $\alpha$ 是活前缀，当且仅当存在最右句型：
$$
S\Rightarrow^*_{rm}\alpha\beta w
$$
其中 $\alpha$ 是栈的内容，$w$ 是剩余输入。

LR(0) 自动机

LR(0) 项目集规范族构成一个有限自动机：

• 状态：项目集 $I_0, I_1, …, I_n$
• 初始状态：$I_0=\text{CLOSURE}({S’\rightarrow\cdot S})$
• 转移函数：$\text{GOTO}(I, X)$
• 作用：识别活前缀

当分析器的栈内容对应某个活前缀时，自动机处于相应的状态。

---

可归前缀和归约

可归前缀（Reducible Prefix）

如果活前缀 $\alpha$ 对应的项目集中包含归约项目 $A\rightarrow\beta\cdot$，则 $\alpha$ 是可归前缀，可以用产生式 $A\rightarrow\beta$ 进行归约。

LR(0) 文法的定义

文法 $G$ 是 LR(0) 文法，当且仅当对于项目集规范族中的每个项目集 $I$：

1. 如果 $I$ 包含归约项目 $A\rightarrow\alpha\cdot$，则 $I$ 不能包含其他项目（除了 $S’\rightarrow S\cdot$）
2. $I$ 中最多只有一个归约项目

通俗理解：在任何状态下，归约动作是唯一确定的，不需要向前看输入。

LR(0) 冲突

如果某个项目集 $I$ 同时包含：

1. 移进-归约冲突：既有移进项目 $A\rightarrow\alpha\cdot a\beta$，又有归约项目 $B\rightarrow\gamma\cdot$
2. 归约-归约冲突：有两个或多个归约项目 $A\rightarrow\alpha\cdot$ 和 $B\rightarrow\beta\cdot$

则该文法不是 LR(0) 文法。

示例：非 LR(0) 文法

文法：
$$
\begin{aligned}
S’ &\rightarrow S \
S &\rightarrow aA\ |\ bB \
A &\rightarrow aA\ |\ a \
B &\rightarrow bB\ |\ b
\end{aligned}
$$

某个项目集可能包含：
$$
\begin{aligned}
&A\rightarrow a\cdot A \
&A\rightarrow a\cdot
\end{aligned}
$$

这是移进-归约冲突：

• $A\rightarrow a\cdot A$：建议移进（期望看到 $A$）
• $A\rightarrow a\cdot$：建议归约

文法不是 LR(0)，需要使用 SLR(1) 或更强的分析方法。

---

LR(0) 分析表的构造

虽然大多数文法不是 LR(0)，但了解 LR(0) 分析表的构造有助于理解后续方法。

构造步骤

1. 构造增广文法 $G’$
2. 构造项目集规范族 $C={I_0, I_1, …, I_n}$
3. 构造 ACTION 和 GOTO 表：

对于每个项目集 $I_i$：

ACTION 表：

• 如果 $I_i$ 包含 $A\rightarrow\alpha\cdot a\beta$（$a$ 是终结符）且 $\text{GOTO}(I_i, a)=I_j$：

  • $\text{ACTION}[i, a]=s_j$（移进到状态 $j$）

• 如果 $I_i$ 包含 $A\rightarrow\alpha\cdot$（$A\neq S’$）：

  • 对于所有终结符 $a$（包括 $）：$\text{ACTION}[i, a]=r_k$（用第 $k$ 个产生式归约）

• 如果 $I_i$ 包含 $S’\rightarrow S\cdot$：

  • $\text{ACTION}[i, $]=\text{acc}$（接受）

GOTO 表：

• 如果 $\text{GOTO}(I_i, A)=I_j$（$A$ 是非终结符）：
  • $\text{GOTO}[i, A]=j$

冲突处理：如果同一个表项有多个动作，说明文法不是 LR(0)。

---

SLR(1) 分析

SLR(1)（Simple LR(1)）是 LR(0) 的改进版，通过向前看一个符号并使用 FOLLOW 集来解决部分冲突。

SLR(1) 的改进思想

LR(0) 在归约时，对所有输入符号都执行归约，这过于”激进”。

SLR(1) 的改进：归约项目 $A\rightarrow\alpha\cdot$ 只在下一个输入符号 $\in$ FOLLOW(A) 时才归约。

原因：如果 $A$ 能归约，那么归约后 $A$ 后面跟的符号必定在 $\text{FOLLOW}(A)$ 中。

SLR(1) 分析表的构造

构造步骤与 LR(0) 类似，只是归约项目的处理不同：

ACTION 表：

• 移进项目：同 LR(0)

• 归约项目 $A\rightarrow\alpha\cdot$（$A\neq S’$）：

  • 只对 $\text{FOLLOW}(A)$ 中的符号：$\text{ACTION}[i, a]=r_k$
  • （而不是对所有终结符）

• 接受：同 LR(0)

GOTO 表：同 LR(0)

示例

文法：
$$
\begin{aligned}
(0)\ S’ &\rightarrow S \
(1)\ S &\rightarrow aA \
(2)\ A &\rightarrow aA \
(3)\ A &\rightarrow a
\end{aligned}
$$

FOLLOW 集：

• $\text{FOLLOW}(S)={$}$
• $\text{FOLLOW}(A)={$}$

某个项目集（例如 $I_3$）：
$$
\begin{aligned}
&A\rightarrow a\cdot A \
&A\rightarrow a\cdot \
&A\rightarrow\cdot aA \
&A\rightarrow\cdot a
\end{aligned}
$$

LR(0) 冲突：

• $A\rightarrow a\cdot A$：移进（看到 $a$）
• $A\rightarrow a\cdot$：归约

SLR(1) 解决：

• $\text{ACTION}[3, a]=s_3$（移进）
• $\text{ACTION}[3, $]=r_3$（归约，因为 $$\in\text{FOLLOW}(A)$）

结果：没有冲突，文法是 SLR(1)。

---

SLR(1) 文法的定义

文法 $G$ 是 SLR(1) 文法，当且仅当对于构造的 SLR(1) 分析表，没有冲突（每个表项最多一个动作）。

SLR(1) 的局限性

SLR(1) 使用的是全局的 FOLLOW 集，而不考虑当前的具体分析上下文。

示例（SLR(1) 无法处理）：

文法：
$$
\begin{aligned}
S’ &\rightarrow S \
S &\rightarrow L = R\ |\ R \
L &\rightarrow * R\ |\ \text{id} \
R &\rightarrow L
\end{aligned}
$$

某个项目集：
$$
\begin{aligned}
&S\rightarrow L\cdot = R \
&R\rightarrow L\cdot
\end{aligned}
$$

• $\text{FOLLOW}(R)={$, =}$（因为 $S\rightarrow L = R$）
• 冲突：看到 = 时，既可以移进（$S\rightarrow L\cdot = R$），又可以归约（$R\rightarrow L\cdot$ 且 $=\in\text{FOLLOW}(R)$）

SLR(1) 无法解决，需要使用 LR(1)。

---

LR(1) 分析

LR(1)（Canonical LR(1)）是最强大的 LR 分析方法，它使用更精确的向前看信息。

LR(1) 项目

定义

LR(1) 项目的形式为：
$$
[A\rightarrow\alpha\cdot\beta,\ a]
$$

其中：

• $A\rightarrow\alpha\cdot\beta$：LR(0) 项目
• $a$：向前看符号（Lookahead Symbol），$a\in V_T\cup{$}$

含义：

• 当前已匹配 $\alpha$，期望匹配 $\beta$
• 如果 $\beta=\varepsilon$（归约项目），则只有当下一个输入符号是 $a$ 时才归约

与 LR(0) 的区别

• LR(0) 项目：$A\rightarrow\alpha\cdot\beta$（没有向前看信息）
• LR(1) 项目：$[A\rightarrow\alpha\cdot\beta,\ a]$（携带向前看符号 $a$）

优势：向前看符号是局部的、上下文相关的，比 SLR(1) 的全局 FOLLOW 集更精确。

---

LR(1) 项目集族的构造

闭包运算

对于 LR(1) 项目集 $I$，其闭包 $\text{CLOSURE}(I)$ 的构造：

初始：$\text{CLOSURE}(I)=I$

迭代规则：对于 $\text{CLOSURE}(I)$ 中的每个项目 $[A\rightarrow\alpha\cdot B\beta,\ a]$（点后是非终结符 $B$）：

• 对于 $B$ 的每个产生式 $B\rightarrow\gamma$
• 对于 $\text{FIRST}(\beta a)$ 中的每个终结符 $b$
• 将项目 $[B\rightarrow\cdot\gamma,\ b]$ 加入 $\text{CLOSURE}(I)$（如果还不存在）

关键：向前看符号 $b$ 来自 $\text{FIRST}(\beta a)$，这是根据当前上下文计算的。

算法

def CLOSURE(I):
    J = I.copy()
    repeat:
        for each 项目 [A → α·Bβ, a] in J:
            if B 是非终结符:
                for each 产生式 B → γ:
                    for each b in FIRST(βa):
                        if [B → ·γ, b] not in J:
                            J.add([B → ·γ, b])
    until J 不再变化
    return J

转移函数

$\text{GOTO}(I, X)$ 的定义类似 LR(0)，但操作的是 LR(1) 项目：

def GOTO(I, X):
    J = {}
    for each 项目 [A → α·Xβ, a] in I:
        将 [A → αX·β, a] 加入 J
    return CLOSURE(J)

项目集规范族的构造

def构造LR1项目集规范族(G'):
    C = {CLOSURE({[S' → ·S, $]})}
    
    repeat:
        for each 项目集 I in C:
            for each 文法符号 X:
                J = GOTO(I, X)
                if J 非空 and J not in C:
                    C.add(J)
    until C 不再变化
    
    return C

示例

文法：
$$
\begin{aligned}
(0)\ S’ &\rightarrow S \
(1)\ S &\rightarrow L = R\ |\ R \
(3)\ L &\rightarrow * R\ |\ \text{id} \
(5)\ R &\rightarrow L
\end{aligned}
$$

$I_0$：
$$
\begin{aligned}
&[S’\rightarrow\cdot S,\ $] \
&[S\rightarrow\cdot L = R,\ $] \
&[S\rightarrow\cdot R,\ $] \
&[L\rightarrow\cdot * R,\ =] \
&[L\rightarrow\cdot\text{id},\ =] \
&[R\rightarrow\cdot L,\ $] \
&[L\rightarrow\cdot * R,\ $] \
&[L\rightarrow\cdot\text{id},\ $]
\end{aligned}
$$

注意：

• $[L\rightarrow\cdot * R,\ =]$：因为 $S\rightarrow L\cdot = R$，所以 $L$ 后面跟 =
• $[L\rightarrow\cdot * R,\ $]$：因为 $S\rightarrow R$ 和 $R\rightarrow L$，所以 $L$ 后面跟 $

关键项目集（解决了 SLR(1) 的冲突）：
$$
I_2=\text{GOTO}(I_0, L)=\left{
\begin{aligned}
&[S\rightarrow L\cdot = R,\ $] \
&[R\rightarrow L\cdot,\ $]
\end{aligned}
\right}
$$

SLR(1) 的冲突：

• $\text{FOLLOW}(R)={$, =}$
• 看到 = 时，移进和归约都可能

LR(1) 的解决：

• $[S\rightarrow L\cdot = R,\ $]$：看到 = 移进
• $[R\rightarrow L\cdot,\ $]$：只有看到 $ 才归约

结果：没有冲突！

---

LR(1) 分析表的构造

ACTION 表：

对于项目集 $I_i$：

1. 如果 $[A\rightarrow\alpha\cdot a\beta,\ b]\in I_i$（$a$ 是终结符）且 $\text{GOTO}(I_i, a)=I_j$：

   • $\text{ACTION}[i, a]=s_j$

2. 如果 $[A\rightarrow\alpha\cdot,\ a]\in I_i$（$A\neq S’$）：

   • $\text{ACTION}[i, a]=r_k$（只对向前看符号 $a$）

3. 如果 $[S’\rightarrow S\cdot,\ $]\in I_i$：

   • $\text{ACTION}[i, $]=\text{acc}$

GOTO 表：同 LR(0)

LR(1) 文法的定义

文法 $G$ 是 LR(1) 文法，当且仅当构造的 LR(1) 分析表没有冲突。

定理：LR(1) 分析能识别所有确定性上下文无关语言。

---

LR(1) 的问题

问题：LR(1) 项目集规范族的规模非常大。

• 一个 LR(0) 项目可能对应多个 LR(1) 项目（向前看符号不同）
• 项目集数量可能是 LR(0) 的 10 倍甚至更多
• 分析表巨大，占用大量内存

解决方案：LALR(1) 分析（压缩 LR(1) 状态）

---

LALR(1) 分析

LALR(1)（Look-Ahead LR(1)）是 LR(1) 和 SLR(1) 的折中方案：

• 分析能力：强于 SLR(1)，弱于 LR(1)
• 状态数：与 LR(0) 相同（远少于 LR(1)）

LALR(1) 的基本思想

核心思想：将 LR(1) 项目集中核心相同的项目集合并。

核心（Core）

LR(1) 项目 $[A\rightarrow\alpha\cdot\beta,\ a]$ 的核心是 $A\rightarrow\alpha\cdot\beta$（去掉向前看符号）。

两个 LR(1) 项目集的核心相同，当且仅当它们包含的项目去掉向前看符号后完全相同。

合并规则

如果两个 LR(1) 项目集 $I_i$ 和 $I_j$ 的核心相同，则合并为一个 LALR(1) 项目集：

方法：对于核心相同的项目，合并向前看符号。

例如：

• $I_i={[A\rightarrow\alpha\cdot\beta,\ a],\ [B\rightarrow\gamma\cdot\delta,\ c]}$
• $I_j={[A\rightarrow\alpha\cdot\beta,\ b],\ [B\rightarrow\gamma\cdot\delta,\ d]}$

合并后：

• $I_{ij}={[A\rightarrow\alpha\cdot\beta,\ {a, b}],\ [B\rightarrow\gamma\cdot\delta,\ {c, d}]}$

LALR(1) 构造方法

方法 1：从 LR(1) 项目集族合并

1. 构造完整的 LR(1) 项目集族
2. 合并核心相同的项目集
3. 构造 LALR(1) 分析表

方法 2：直接构造（效率更高）

1. 构造 LR(0) 项目集族
2. 为每个项目添加向前看符号（传播和自发生成）
3. 构造 LALR(1) 分析表

---

LALR(1) 分析表的构造

ACTION 表：与 LR(1) 类似，但使用合并后的向前看符号集合

对于项目集 $I_i$：

1. 如果 $[A\rightarrow\alpha\cdot a\beta,\ S]\in I_i$（$S$ 是向前看符号集）且 $\text{GOTO}(I_i, a)=I_j$：

   • $\text{ACTION}[i, a]=s_j$

2. 如果 $[A\rightarrow\alpha\cdot,\ S]\in I_i$（$A\neq S’$）：

   • 对于 $S$ 中的每个符号 $a$：$\text{ACTION}[i, a]=r_k$

3. 如果 $[S’\rightarrow S\cdot,\ {$}]\in I_i$：

   • $\text{ACTION}[i, $]=\text{acc}$

GOTO 表：同 LR(0)

---

LALR(1) 的特点

优点

1. 状态数少：与 LR(0)/SLR(1) 相同，远少于 LR(1)
2. 分析能力强：强于 SLR(1)，能处理绝大多数实际文法
3. 广泛使用：Yacc、Bison 等工具采用 LALR(1)

缺点

1. 可能引入新的归约-归约冲突：合并项目集时，可能使原本不冲突的变成冲突

   • LR(1) 无冲突 $\not\Rightarrow$ LALR(1) 无冲突
   • 但实践中很少遇到

2. 错误检测延迟：可能在错误位置后才检测到错误（但不影响正确性）

LALR(1) vs LR(1) vs SLR(1)

特性	SLR(1)	LALR(1)	LR(1)
状态数	$n$	$n$	$10n$（约）
分析能力	较弱	较强	最强
构造复杂度	简单	中等	复杂
实际应用	教学	工业标准	理论研究

---

示例：LALR(1) 处理的文法

前面 LR(1) 的例子：
$$
\begin{aligned}
S’ &\rightarrow S \
S &\rightarrow L = R\ |\ R \
L &\rightarrow * R\ |\ \text{id} \
R &\rightarrow L
\end{aligned}
$$

LR(1) 项目集（部分）：
$$
I_2={[S\rightarrow L\cdot = R,\ $],\ [R\rightarrow L\cdot,\ $]}
$$
$$
I_7={[R\rightarrow L\cdot,\ =]}
$$

$I_2$ 和 $I_7$ 的核心相同（都是 ${S\rightarrow L\cdot = R,\ R\rightarrow L\cdot}$）

LALR(1) 合并：
$$
I_{2,7}={[S\rightarrow L\cdot = R,\ {$, =}],\ [R\rightarrow L\cdot,\ {$, =}]}
$$

检查冲突：

• 看到 =：移进（$S\rightarrow L\cdot = R$）
• 看到 =：归约（$R\rightarrow L\cdot,\ =\in{$, =}$）

冲突！ 合并引入了移进-归约冲突。

结论：该文法是 LR(1)，但不是 LALR(1)。

（注：这个例子是特意构造的，实际中很少遇到这种情况）

---

二义性文法在 LR 分析中的应用

某些二义性文法虽然理论上不是 LR 文法，但通过优先级和结合性规则可以转化为等价的 LR 分析器。

二义性表达式文法

典型的二义性文法：
$$
\begin{aligned}
E &\rightarrow E + E \
E &\rightarrow E * E \
E &\rightarrow (E) \
E &\rightarrow\text{id}
\end{aligned}
$$

问题：$\text{id} + \text{id} * \text{id}$ 有两棵不同的语法树。

冲突示例

某个 LR(1) 项目集：
$$
\begin{aligned}
&[E\rightarrow E\cdot + E,\ *] \
&[E\rightarrow E + E\cdot,\ *] \
&[E\rightarrow E\cdot * E,\ $]
\end{aligned}
$$

移进-归约冲突：看到 * 时，

• 移进：继续 $E\rightarrow E\cdot * E$
• 归约：完成 $E\rightarrow E + E\cdot$

如何选择？ 取决于 * 的优先级和结合性。

---

优先级和结合性规则

优先级（Precedence）

运算符的优先级决定冲突时的选择：

运算符	优先级
*	高
+	低

规则：

• 如果当前运算符优先级高于栈顶运算符：移进
• 如果当前运算符优先级低于栈顶运算符：归约

结合性（Associativity）

同优先级运算符的结合性：

• 左结合（Left Associative）：$a + b + c = (a + b) + c$

  • 遇到相同运算符时：归约

• 右结合（Right Associative）：$a = b = c = a = (b = c)$（赋值）

  • 遇到相同运算符时：移进

Yacc/Bison 中的声明

在 Yacc/Bison 中，使用 %left、%right、%nonassoc 声明：

%left '+' '-'      // + 和 - 左结合，优先级相同
%left '*' '/'      // * 和 / 左结合，优先级高于 + -
%right '='         // = 右结合
%nonassoc UMINUS   // 一元负号，不可结合

顺序：后声明的优先级更高。

---

消解冲突的规则

对于移进-归约冲突：

1. 根据优先级：

   • 当前输入符号优先级 > 栈顶产生式优先级：移进
   • 当前输入符号优先级 < 栈顶产生式优先级：归约

2. 根据结合性（优先级相同时）：

   • 左结合：归约
   • 右结合：移进
   • 不可结合：报错

对于归约-归约冲突：

• 无法通过优先级和结合性解决
• 必须改写文法

---

示例：使用优先级解决冲突

二义性文法 + 优先级声明：

%left '+'
%left '*'

%%
E : E '+' E
  | E '*' E
  | '(' E ')'
  | ID
  ;

冲突解决：

栈内容	输入	冲突	优先级比较	决策
E + E	*	移进/归约	* > +	移进
E * E	+	移进/归约	+ < *	归约
E + E	+	移进/归约	+ = +，左结合	归约

结果：正确处理优先级和结合性。

---

悬挂 else 问题

文法：
$$
\begin{aligned}
S &\rightarrow\text{if}\ E\ \text{then}\ S \
S &\rightarrow\text{if}\ E\ \text{then}\ S\ \text{else}\ S \
S &\rightarrow\text{other}
\end{aligned}
$$

冲突：

if E1 then if E2 then S1 else S2

某个项目集：
$$
\begin{aligned}
&[S\rightarrow\text{if}\ E\ \text{then}\ S\cdot,\ \text{else}] \
&[S\rightarrow\text{if}\ E\ \text{then}\ S\cdot\text{else}\ S,\ $]
\end{aligned}
$$

移进-归约冲突：看到 else，

• 归约：完成第一个 if
• 移进：else 匹配第二个 if

解决：优先移进（else 匹配最近的 if）

Yacc/Bison 默认：移进优先。

---

LR 分析的错误处理

错误检测

LR 分析器在以下情况检测到错误：

• ACTION 表为空：$\text{ACTION}[s, a]$ 没有定义
• 即当前状态和输入符号的组合非法

LR 分析器能在第一时间检测到错误（不会延迟）。

错误恢复策略

1. 应急恢复（Panic Mode）

策略：丢弃栈中的状态，直到找到可以继续的状态。

方法：

1. 扫描栈，找到一个包含同步非终结符（如 stmt、expr）的状态
2. 丢弃输入符号，直到找到后继符号（如 ;、}）
3. 继续分析

2. 短语层恢复

策略：根据当前状态和输入符号，局部修改（插入、删除、替换）。

实现：在 ACTION 表中，为空项填入错误处理动作：

• 插入缺失的符号
• 删除多余的符号
• 给出有用的错误提示

3. 错误产生式

策略：在文法中添加错误产生式，识别常见错误。

示例：

stmt : IF '(' expr ')' stmt
     | IF '(' expr stmt    // 错误：缺少 ')'
       { yyerror("缺少 ')'"); }
     ;

---

LR 分析器生成工具

Yacc/Bison

Yacc（Yet Another Compiler Compiler）和 Bison（GNU 版本的 Yacc）是经典的 LR 分析器生成工具。

输入文件结构

%{
    /* C 声明：头文件、全局变量 */
    #include <stdio.h>
%}

/* Bison 声明：终结符、非终结符、优先级 */
%token NUMBER
%left '+' '-'
%left '*' '/'

%%
/* 文法规则 */
expr : expr '+' expr  { $$ = $1 + $3; }
     | expr '*' expr  { $$ = $1 * $3; }
     | NUMBER         { $$ = $1; }
     ;
%%

/* C 代码：辅助函数 */
int main() {
    yyparse();
    return 0;
}

编译和运行

bison -d calculator.y   # 生成 calculator.tab.c 和 calculator.tab.h
flex scanner.l          # 生成 lex.yy.c（词法分析器）
gcc calculator.tab.c lex.yy.c -o calculator
./calculator

---

总结与实践建议

LR 分析的核心知识

1. 基本概念：

   • 自底向上、最右推导的逆、句柄、移进-归约
   • 项目、项目集、闭包、GOTO 函数

2. LR(0) 分析：

   • LR(0) 项目和项目集规范族
   • 活前缀、可归前缀
   • 识别活前缀的有限自动机

3. SLR(1) 分析：

   • 使用 FOLLOW 集改进 LR(0)
   • SLR(1) 分析表构造

4. LR(1) 分析：

   • LR(1) 项目（带向前看符号）
   • 最强大的 LR 分析
   • 状态数多的问题

5. LALR(1) 分析：

   • 合并核心相同的项目集
   • 工业标准（Yacc/Bison）
   • LR(1) 和 SLR(1) 的折中

6. 二义性文法：

   • 优先级和结合性规则
   • 在实际编译器中的应用

各种 LR 方法的对比

方法	分析能力	状态数	构造难度	实际应用
LR(0)	最弱	$n$	简单	教学
SLR(1)	较弱	$n$	简单	教学
LALR(1)	较强	$n$	中等	工业标准
LR(1)	最强	$10n$	复杂	理论研究

LL vs LR

特性	LL(1)	LR(1)
分析方向	自顶向下	自底向上
推导方式	最左推导	最右推导的逆
适用文法	LL(1) 文法（较窄）	LR(1) 文法（较广）
实现方式	递归下降（易手工）	表驱动（依赖工具）
左递归	不能处理	可以处理
错误处理	较容易	较困难
典型工具	ANTLR（LL(k)）	Yacc/Bison（LALR(1)）

学习建议

1. 理解项目和项目集：

   • 手工构造小文法的 LR(0)/LR(1) 项目集规范族
   • 画出自动机状态转换图

2. 练习分析表构造：

   • 为简单文法构造 SLR(1)、LR(1)、LALR(1) 分析表
   • 识别和解决冲突

3. 使用工具：

   • 学习 Bison/Yacc，为简单语言编写分析器
   • 理解工具生成的冲突报告

4. 对比 LL 和 LR：

   • 理解各自的优缺点和适用场景
   • 知道何时选择哪种方法

5. 阅读实际代码：

   • GCC、LLVM 等编译器的语法分析器
   • 开源项目中的 Yacc/Bison 文件

---

本章小结：

LR 分析是自底向上语法分析的核心方法，特别是 LALR(1) 是现代编译器工具（Yacc、Bison）的理论基础。通过：

• 项目和项目集：跟踪分析进度
• 闭包和 GOTO：构造 LR 自动机
• ACTION 和 GOTO 表：驱动移进-归约过程
• 优先级和结合性：处理二义性文法

我们可以为大多数实际编程语言构造高效的语法分析器。虽然 LR 分析的理论较为复杂，但工具的成熟使得实践中使用 LR 分析变得非常简单——只需编写文法规则和语义动作，Bison 会自动生成完整的分析器。

掌握 LR 分析原理，不仅有助于使用工具（理解冲突报告、调试文法），也为深入理解编译器的工作机制、优化编译器性能打下坚实基础。