2 Syntax Analysis

语法分析是编译器的第二阶段，将词法分析输出的 Token 流转化为抽象语法树 (AST)。核心问题是：给定 CFG 文法 \(G\) 和输入串 \(w\)，判断 \(w \in L(G)\) 并构造推导过程。

2.1 Context-Free Grammars

定义：\(G = (T, N, P, S)\) — 终结符、非终结符、产生式集合、开始符号。

推导 (Derivation)：从开始符号出发，反复用产生式右部替换非终结符，最终得到终结符串。

• 最左推导：总是替换最左非终结符（对应自顶向下分析）。
• 最右推导：总是替换最右非终结符（对应自底向上分析，其逆过程为归约）。

二义性 (Ambiguity)：一个句子对应多棵不同的语法树。通常通过引入分层非终结符（优先级）和规定左/右递归（结合性）来消除。

二义性文法:                  消除二义性后:
E → E + E | E * E | id      E → E + T | T
                             T → T * F | F
                             F → (E) | id

2.2 Top-Down Parsing

从根节点（开始符号）出发，尝试构造语法树使其叶子节点匹配输入。

Recursive Descent：每个非终结符对应一个函数，按产生式依次尝试匹配。缺点是可能需要回溯，效率低。

2.2.1 LL(1) Parsing

LL(1) 是确定性自顶向下方法：从左到右扫描 (L)、最左推导 (L)、向前看 1 个 Token。核心是预测分析表——查表决定用哪条产生式展开当前非终结符。

前提条件：文法是 LL(1) 文法——无左递归、已提取左公因子、FIRST/FOLLOW 集不相交。

FIRST 集：从某符号出发能推导出的所有串的首终结符集合。若可推导出 \(\varepsilon\)，则 \(\varepsilon \in\) FIRST。

FOLLOW 集：在推导过程中，某非终结符之后可能出现的终结符集合（\(\$\) 表示输入结束）。

构造 LL(1) 表：对每个产生式 \(A \to \alpha\)，

• 对每个终结符 \(a \in\) FIRST\((\alpha)\)（\(\varepsilon\) 除外），\(M[A, a] = A \to \alpha\)。
• 若 \(\varepsilon \in\) FIRST\((\alpha)\)，则对每个 \(b \in\) FOLLOW\((A)\)，\(M[A, b] = A \to \alpha\)。

---

Example — 左递归消除后的表达式文法：

(1) E  → T E'
(2) E' → + T E'
(3) E' → ε
(4) T  → F T'
(5) T' → * F T'
(6) T' → ε
(7) F  → (E)
(8) F  → id

FIRST 逐步计算：

轮次	操作	变化
初始化	终结符：FIRST(+)={+}, FIRST()={}, FIRST(()={(}, FIRST(id)={id}, FIRST())={)}
R1	(7) F→(E)：FIRST(F) +=	FIRST(F)={(}
R1	(8) F→id：FIRST(F) +=	FIRST(F)={(, id}
R1	(4) T→FT'：FIRST(T) += FIRST(F)（F 的 FIRST 无 ε，停）	FIRST(T)={(, id}
R1	(1) E→TE'：FIRST(E) += FIRST(T)（T 的 FIRST 无 ε，停）	FIRST(E)={(, id}
R1	(2) E'→+TE'：FIRST(E') +=	FIRST(E')={+}
R1	(5) T'→FT'：FIRST(T') += {}	FIRST(T')={*}
R1	(3) E'→ε：ε ∈ FIRST(E')	FIRST(E')={+, ε}
R1	(6) T'→ε：ε ∈ FIRST(T')	FIRST(T')={*, ε}

此时推导不出新终结符，不动点到达。

FOLLOW 逐步计算：

轮次	操作	变化
初始化	FOLLOW(E) += {$}（开始符号）	FOLLOW(E)={$}
R1	(7) F→(E)：在 E 后有 )，将 ) 加入 FOLLOW(E)	FOLLOW(E)={$, )}
R1	(1) E→TE'：E' 是产生式末尾，FOLLOW(E') += FOLLOW(E)={$, )}	FOLLOW(E')={$, )}
R1	(1) E→TE'：T 后是 E'，加入 FIRST(E'){ε}={+}，且 ε∈FIRST(E')，加 FOLLOW(E)	FOLLOW(T)={+, $, )}
R1	(4) T→FT'：T' 是末尾，FOLLOW(T') += FOLLOW(T)={+, $, )}	FOLLOW(T')={+, $, )}
R1	(4) T→FT'：F 后是 T'，加入 FIRST(T'){ε}={*}，且 ε∈FIRST(T')，加 FOLLOW(T)	FOLLOW(F)={*, +, $, )}
R2	(2) E'→+TE'：E' 是末尾，FOLLOW(E') += FOLLOW(E')（已有，无变化）	不变
R2	(2) E'→+TE'：T 后是 E'，加入 FIRST(E'){ε}={+}，且 ε∈FIRST(E')，加 FOLLOW(E')={$, )}	FOLLOW(T) += {$, )}（已有）
R2	(5) T'→FT'：同理，F 后是 T'，加 FIRST(T'){ε}={}，加 FOLLOW(T')	FOLLOW(F) += {}（已有）

不动点到达。汇总：

	FIRST	FOLLOW
E	{(, id}	{), $}
E'	{+, ε}	{), $}
T	{(, id}	{+, ), $}
T'	{*, ε}	{+, ), $}
F	{(, id}	{*, +, ), $}

LL(1) 预测分析表：

	id	+	*	(	)	$
E	E→TE'			E→TE'
E'		E'→+TE'			E'→ε	E'→ε
T	T→FT'			T→FT'
T'		T'→ε	T'→*FT'		T'→ε	T'→ε
F	F→id			F→(E)

Trace — 输入 id + id * id：

栈	输入	动作
$E	id+id*id$	E→TE'
$E'T	id+id*id$	T→FT'
$E'T'F	id+id*id$	F→id
$E'T'	+id*id$	match id
$E'	+id*id$	T'→ε
$E'T+	id*id$	E'→+TE'
$E'T	id*id$	match +
$E'T'F	id*id$	T→FT'
$E'T'	*id$	F→id, match id
$E'T'F*	id$	T'→*FT'
$E'T'F	$	match *, F→id, match id
$E'T'	$	T'→ε
$E'	$	E'→ε
$	$	accept

2.3 Bottom-Up Parsing (Shift-Reduce)

从输入串（叶子）出发，不断将栈顶符号串归约为产生式左部非终结符，直到归约为开始符号。

核心操作： - Shift：将下一个输入符号压入栈。 - Reduce：栈顶出现产生式右部 \(\beta\)，弹出 \(|\beta|\) 个符号，压入左部 \(A\)。

LR 分析栈的结构：栈中状态与文法符号交替存放（s₀X₁s₁X₂s₂...），状态驱动移进/归约决策，文法符号用于构造推导。

归约的三步规则 — 对产生式 \(A \to \beta\)（设 \(n = |\beta|\)）：

1. 弹出 \(2n\) 个元素（\(n\) 个文法符号 + \(n\) 个状态），暴露栈顶状态 \(s\)。
2. 压入左部非终结符 \(A\)。
3. 查 GOTO 表：压入 GOTO[s, A]（即 \(s\) 读到 \(A\) 后到达的新状态）。

示例: 栈 = 0 id 5, 执行 r4 (L→id), GOTO(0, L) = 2

  弹出 2 个元素(id, 5) → 暴露状态 0
  压入 L → 栈 = 0 L
  压入 GOTO(0, L) = 2 → 栈 = 0 L 2

当栈顶状态只有归约项（如状态 5 仅含 [L → id·]），该状态的所有合法动作都是归约——此时无需关心"从该状态能去哪个下一状态"，因为归约会先弹出该状态、暴露前一状态，再由 GOTO 表决定去向。

句柄 (Handle)：栈顶可被归约的产生式右部。何时 shift、何时 reduce、按哪条产生式 reduce，由 LR 分析表决定。

LR 系列方法按"冲突解决能力"递增：

方法	核心	冲突处理
LR(0)	仅看栈顶状态，不管输入	极易冲突
SLR(1)	FOLLOW 集过滤归约条件	部分解决
LR(1)	每项自带精确展望符	几乎无冲突，状态爆炸
LALR(1)	合并 LR(1) 同心状态	工程首选（Yacc/Bison）

以下用一个贯穿的经典文法展示四种 LR 方法。该文法在 LR(0) 和 SLR(1) 中均有冲突，在 LR(1) 和 LALR(1) 中解决。

增广文法:
(0) S' → S
(1) S  → L = R
(2) S  → R
(3) L  → * R
(4) L  → id
(5) R  → L

FIRST/FOLLOW：

• FOLLOW\((S) = \{\$\}\)，FOLLOW\((L) =\) FOLLOW\((R) = \{=, \$\}\)。

• FIRST 集较简单：FIRST\((S) =\) FIRST\((L) =\) FIRST\((R) = \{*, id\}\)。

LR(0)

LR(0) 项：在产生式右部某处加点 ·，表示"当前已识别到此处"。如 \(A \to \alpha \cdot \beta\) 表示已识别 \(\alpha\)，期望接下来识别 \(\beta\)。

项集闭包 Closure(\(I\))：若 \([A \to \alpha \cdot B \beta] \in I\)，对每个 \(B \to \gamma\)，将 \([B \to \cdot \gamma]\) 加入，重复至不动点。

Goto(\(I, X\))：从状态 \(I\) "读入"文法符号 \(X\) 后到达的新状态。两步操作：

1. 移动点：找出 \(I\) 中所有点在 \(X\) 之前的项 \([A \to \alpha \cdot X \beta]\)，将点右移得到 \([A \to \alpha X \cdot \beta]\)。
2. 求闭包：对这些移点后的项做 Closure（展开点后的非终结符）。

例如在 \(I_0\) 中，Goto\((I_0, *)\)：先找到 \([L \to \cdot * R]\)，移点得 \([L \to * \cdot R]\)；再展开 \(R\) 的所有产生式（点在最前），得到 \(I_4\)。

LR(0) 自动机构造：从 \(I_0 =\) Closure(\(\{[S' \to \cdot S]\}\)) 出发，对每个已有状态 \(I\) 和每个文法符号 \(X\)，若 Goto\((I, X)\) 非空且为新状态，则创建该状态并添加从 \(I\) 到它的转移。

LR(0) 分析表：对每个状态 \(I_i\)， - 若 \([A \to \alpha \cdot a \beta] \in I_i\) 且 Goto\((I_i, a) = I_j\)：ACTION\([i, a]\) = s\(j\)（shift） - 若 \([A \to \alpha \cdot] \in I_i\)：对所有终结符 \(a\)，ACTION\([i, a]\) = r\(k\)（reduce by production \(k\)） - 若 \([S' \to S \cdot] \in I_i\)：ACTION\([i, \$]\) = acc

LR(0) 的问题

Reduce 项对所有输入符号都填 r，完全不看下一个 Token 是什么，极易产生 shift-reduce 冲突。

---

LR(0) Example — 对示例文法构造自动机：

I₀ = closure({[S' → ·S]})        I₅ = {[L → id·]}
  [S' → ·S]                       → 仅包含归约项
  [S → ·L = R]                    
  [S → ·R]                       I₆ = goto(I₂, =)
  [L → ·* R]                       [S → L = ·R]
  [L → ·id]                        [R → ·L]
  [R → ·L]                         [L → ·* R]
                                    [L → ·id]
I₁ = goto(I₀, S): [S' → S·]
                                  I₇ = goto(I₄, R): [L → * R·]
I₂ = goto(I₀, L)                  I₈ = goto(I₄, L): [R → L·]
  [S → L· = R]
  [R → L·]   ← 冲突！             I₉ = goto(I₆, R): [S → L = R·]

I₃ = goto(I₀, R): [S → R·]

I₄ = goto(I₀, *)  = goto(I₄, *) = goto(I₆, *)
  [L → *·R]
  [R → ·L]
  [L → ·* R]
  [L → ·id]

转移关系：

I₀ ──S──→ I₁    I₀ ──L──→ I₂    I₀ ──R──→ I₃
I₀ ──*──→ I₄    I₀ ─id──→ I₅
I₂ ──=──→ I₆
I₄ ──R──→ I₇    I₄ ──L──→ I₈    I₄ ──*──→ I₄    I₄ ─id──→ I₅
I₆ ──R──→ I₉    I₆ ──L──→ I₈    I₆ ──*──→ I₄    I₆ ─id──→ I₅

冲突分析：

• \(I_2\)：[S → L· = R] 要求 shift =，[R → L·] 要求 reduce → shift-reduce conflict on =
• LR(0) 无法处理此文法。

SLR(1)

改进：Reduce 不再是"对所有输入都归约"，而是仅当输入符号属于 FOLLOW(左部非终结符) 时才归约。

构造规则（其余同 LR(0)）： - 若 \([A \to \alpha \cdot] \in I_i\)：对每个 \(a \in\) FOLLOW\((A)\)，ACTION\([i, a]\) = r\(k\)。

---

SLR(1) Example — 沿用上面的 LR(0) 自动机（状态相同）。

已知 FOLLOW\((R) = \{=, \$\}\), FOLLOW\((L) = \{=, \$\}\), FOLLOW\((S) = \{\$\}\)。

SLR(1) 分析表：

State	id	*	=	$	S	L	R
0	s5	s4			1	2	3
1				acc
2			s6 / r5	r5
3			r2	r2
4	s5	s4				8	7
5		r4	r4	r4
6	s5	s4				8	9
7		r3	r3	r3
8		r5	r5	r5
9			r1	r1

Note

\(I_2\)：shift = 和 reduce r5 同在 = 列 → SLR(1) 仍然冲突。因为 FOLLOW\((R)\) 包含 =，无法区分"该移进 ="还是"该归约 \(R \to L\)"。

Trace — 输入 id = id 的 SLR(1) 分析过程（假设强制选择 shift 来演示）：

栈	输入	动作
0	id=id$	s5
0id5	=id$	r4 (L→id), GOTO(0,L)=2
0L2	=id$	s6
0L2=6	id$	s5
0L2=6id5	$	r4 (L→id), GOTO(6,L)=8
0L2=6L8	$	r5 (R→L), GOTO(6,R)=9
0L2=6R9	$	r1 (S→L=R), GOTO(0,S)=1
0S1	$	acc

归约时如何确定新状态？ 以第一步 r4 为例：

栈当前为 0 id 5（状态 0 → 符号 id → 状态 5）。状态 5 中的项 [L → id·] 要求归约。 1. 弹出 \(2 \times 1 = 2\) 个元素：符号 id + 状态 5，暴露状态 0。 2. 压入左部符号 L → 栈 = 0 L。 3. 查 GOTO 表：GOTO[0, L] = 2（见分析表第 0 行 L 列），压入状态 2 → 栈 = 0 L 2。

同理，第二步 r4：栈顶暴露状态 6，GOTO[6, L] = 8；第三步 r5：暴露状态 6，GOTO[6, R] = 9；第四步 r1：暴露状态 0，GOTO[0, S] = 1。

状态 5 本身只包含归约项 [L → id·]——它不参与"去哪个状态"的决策，因为归约的第一步就是把它弹出去。

SLR(1) 在 \(I_2\) 存在冲突——此处恰好"猜对"了 shift 才能成功，若选择 reduce 则失败。

LR(1)

SLR(1) 的缺陷在于：它用 FOLLOW 集决定是否归约，但 FOLLOW 集是"全局"的——只要某个 Token 在整个文法中可能跟在 \(A\) 后面，SLR(1) 就在所有状态下都允许对 \(A\) 做归约。这过于粗糙。

改进：每个项附加一个展望符 (Lookahead)，格式：\([A \to \alpha \cdot \beta, a]\)，其中 \(a\) 是终结符或 \(\$\)。归约项 \([A \to \alpha \cdot, a]\) 的含义是：只有当下一个输入 Token 恰好是 \(a\) 时才执行归约。这个 \(a\) 不是从全局 FOLLOW 集来的，而是从该项所在的具体上下文推导出来的。

Closure 扩展规则

这是 LR(1) 最核心的机制。规则如下：

若项集 \(I\) 中有 \([A \to \alpha \cdot B \beta,\; a]\)，则对文法中每个 \(B \to \gamma\)，将 \([B \to \cdot \gamma,\; b]\) 加入 \(I\)，其中 \(b \in \text{FIRST}(\beta a)\)。

为什么要算 \(\text{FIRST}(\beta a)\)？

把产生式连起来看：\(A \to \alpha B \beta\)，项中点已过 \(\alpha\)、刚到 \(B\) 前。\(B\) 之后是 \(\beta\)，而整条产生式的展望符是 \(a\)。

• 如果 \(\beta\) 非空：\(B\) 归约完成后，下一个要分析的符号由 \(\beta\) 的第一个终结符决定 → 用 \(\text{FIRST}(\beta)\)。
• 如果 \(\beta\) 可为空：\(B\) 归约完成后轮到 \(\beta\)，但 \(\beta \Rightarrow^* \varepsilon\)，所以最终跟在 \(B\) 后面的是原来的展望符 \(a\) → 用 \(\text{FIRST}(a) = \{a\}\)。

统一公式 \(\text{FIRST}(\beta a)\) 同时覆盖了这两种情况： - \(\beta\) 非空且不可空 → \(\text{FIRST}(\beta a) = \text{FIRST}(\beta)\) - \(\beta\) 可空 → \(\text{FIRST}(\beta a) = \text{FIRST}(\beta) \cup \{a\}\)

Goto 中的展望符传播

Goto 操作不改变展望符——展望符跟着产生式走：

\[\text{Goto}(I, X) = \text{Closure}\left(\{[A \to \alpha X \cdot \beta,\; a] \mid [A \to \alpha \cdot X \beta,\; a] \in I\}\right)\]

点右移一位，展望符原封不动带上。新闭包展开时再按上述规则重新计算展望符。

---

LR(1) Example — 对同一文法构造完整的 LR(1) 自动机。

详细构造 I₀

以 \(I_0 = \text{Closure}(\{[S' \to \cdot S,\; \$]\})\) 为例，逐步展开：

第 0 步 — 种子项

\[[S' \to \cdot S,\; \$]\]

第 1 步 — 点后是 \(S\)，展开 \(S\) 的所有产生式

对 \([S' \to \cdot S,\; \$]\)，\(\alpha = \varepsilon\)、\(B = S\)、\(\beta = \varepsilon\)、$a = $ $。

\(\text{FIRST}(\beta a) = \text{FIRST}(\varepsilon \$) = \{\$\}\)。

• \(S \to L = R\)：加入 \([S \to \cdot L = R,\; \$]\)
• \(S \to R\)：加入 \([S \to \cdot R,\; \$]\)

第 2 步 — 检查新加项，点后是 \(L\)，展开 \(L\)

对 \([S \to \cdot L = R,\; \$]\)，\(\alpha = \varepsilon\)、\(B = L\)、\(\beta = \; = R\)、$a = $ $。

\(\text{FIRST}(\beta a) = \text{FIRST}(=R\$) = \{=\}\)（因为 \(\beta\) 以终结符 \(=\) 开头）。

• \(L \to *R\)：加入 \([L \to \cdot *R,\; =]\)
• \(L \to \text{id}\)：加入 \([L \to \cdot \text{id},\; =]\)

---

对 \([S \to \cdot R,\; \$]\)，\(\alpha = \varepsilon\)、\(B = R\)、\(\beta = \varepsilon\)、$a = $ $。

\(\text{FIRST}(\beta a) = \text{FIRST}(\$) = \{\$\}\)。

• \(R \to L\)：加入 \([R \to \cdot L,\; \$]\)

第 3 步 — 检查 \([R \to \cdot L,\; \$]\)，点后是 \(L\)，再次展开 \(L\)

对 \([R \to \cdot L,\; \$]\)，\(\alpha = \varepsilon\)、\(B = L\)、\(\beta = \varepsilon\)、$a = $ $。

\(\text{FIRST}(\beta a) = \text{FIRST}(\$) = \{\$\}\)。

• \(L \to *R\)：加入 \([L \to \cdot *R,\; \$]\)
• \(L \to \text{id}\)：加入 \([L \to \cdot \text{id},\; \$]\)

第 4 步 — 检查 \([L \to \cdot *R,\; =]\)：点后是终结符 \(*\)，不展开。同理 \([L \to \cdot \text{id},\; =]\) 不展开。无新非终结符，闭包完成。

汇总 \(I_0\)（注意：LR(1) 中，核心相同但展望符不同的项保留为两个独立项，这正是 LR(1) 比 LR(0) 状态更多的原因）：

I₀:
  [S' → ·S,   $]
  [S  → ·L=R, $]
  [S  → ·R,   $]
  [L  → ·*R,  =]    ← 来自 S→·L=R ($)
  [L  → ·*R,  $]    ← 来自 R→·L ($)
  [L  → ·id,  =]    ← 来自 S→·L=R ($)
  [L  → ·id,  $]    ← 来自 R→·L ($)
  [R  → ·L,   $]

关键观察：\([L \to \cdot *R, =]\) 和 \([L \to \cdot *R, \$]\) 是两个不同的项（核心相同但展望符不同）。在 LR(0) 中它们合并为一个。现在它们分开，后续会走向不同的状态，这就是 LR(1) 精确性的来源。

各状态详细构造

每个 Goto 都执行"移点 + 闭包"两步。

\(I_1 = \text{Goto}(I_0, S)\)：从 \([S' \to \cdot S, \$]\) 移点得 \([S' \to S \cdot, \$]\)。点后无符号，闭包无新项。

I₁:  [S' → S·, $]

\(I_2 = \text{Goto}(I_0, L)\)：从 \(I_0\) 中 \(L\) 前的项移点： - \([S \to \cdot L = R, \$] \to [S \to L \cdot = R, \$]\) - \([R \to \cdot L, \$] \to [R \to L \cdot, \$]\)

点后无非终结符，闭包无新项。

I₂:  [S → L· = R, $]
     [R → L·,     $]    ← 仅在 $ 上归约！

与 LR(0) 的区别：\([R \to L \cdot]\) 在 LR(0) 中对所有终结符归约，SLR(1) 中对 \(\{=, \$\}\) 归约，而这里仅对 \(\{\$\}\) 归约。因为该展望符来自 \(I_0\) 中 \(S' \to \cdot S\) 下展开 \(R\) 时的 \(\text{FIRST}(\$)\)，不包含 \(=\)。

\(I_3 = \text{Goto}(I_0, R)\)：

I₃:  [S → R·, $]

\(I_4 = \text{Goto}(I_0, *)\)：从 \(I_0\) 中 \(*\) 前的项移点：

• \([L \to \cdot *R, =] \to [L \to * \cdot R, =]\)
• \([L \to \cdot *R, \$] \to [L \to * \cdot R, \$]\)

然后闭包展开点后的 \(R\)。对两项分别：

• \([L \to * \cdot R, =]\)：\(\text{FIRST}(\varepsilon \cdot =) = \{=\}\)。 展开 \(R \to L\) → \([R \to \cdot L, =]\)。 再展开 \(L\)：\(\text{FIRST}(\varepsilon \cdot =) = \{=\}\) → \([L \to \cdot *R, =],\; [L \to \cdot \text{id}, =]\)。

• \([L \to * \cdot R, \$]\)：\(\text{FIRST}(\varepsilon \cdot \$) = \{\$\}\)。 展开 \(R \to L\) → \([R \to \cdot L, \$]\)。 再展开 \(L\)：\(\text{FIRST}(\varepsilon \cdot \$) = \{\$\}\) → \([L \to \cdot *R, \$],\; [L \to \cdot \text{id}, \$]\)。

I₄:  [L → *·R, =]  [L → *·R, $]
     [R → ·L,  =]  [R → ·L,  $]
     [L → ·*R, =]  [L → ·*R, $]
     [L → ·id, =]  [L → ·id, $]

注意：\(I_4\) 中的项成对出现（\(\{=\}\) 和 \(\{\$\}\) 两组展望符），因为入边来源于 \(I_0\) 中两个不同展望符的 \([L \to \cdot *R]\) 项。这与 LR(0) 的 \(I_4\) 不同——LR(0) 中这些项合为一份。

\(I_5 = \text{Goto}(I_0, \text{id})\)：

I₅:  [L → id·, =]  [L → id·, $]

\(I_6 = \text{Goto}(I_2, =)\)：从 \([S \to L \cdot = R, \$]\) 移点得 \([S \to L = \cdot R, \$]\)。然后闭包展开 \(R\)：

• \([S \to L = \cdot R, \$]\)：\(\text{FIRST}(\varepsilon \cdot \$) = \{\$\}\)。 展开 \(R \to L\) → \([R \to \cdot L, \$]\)。 再展开 \(L\)：\(\text{FIRST}(\varepsilon \cdot \$) = \{\$\}\) → \([L \to \cdot *R, \$],\; [L \to \cdot \text{id}, \$]\)。

I₆:  [S → L = ·R, $]
     [R → ·L,     $]
     [L → ·*R,    $]
     [L → ·id,    $]

关键：\(I_6\) 中所有项的展望符都是 \(\{\$\}\)——因为进入 \(I_6\) 的唯一路径来自 \(I_2\) 的 shift =，而 \(I_2\) 中 \([S \to L \cdot = R]\) 的展望符是 \(\$\)。这导致后续从 \(I_6\) 展开的 \([R \to \cdot L]\) 也只有 \(\$\) 展望符，最终 \(R \to L\) 的归约仅对 \(\$\) 触发。

\(I_7 = \text{Goto}(I_4, R)\)：

I₇:  [L → *R·, =]  [L → *R·, $]

\(I_8 = \text{Goto}(I_4, L)\)：

I₈:  [R → L·, =]  [R → L·, $]

\(I_9 = \text{Goto}(I_6, R)\)：

I₉:  [S → L = R·, $]

\(I_{10} = \text{Goto}(I_6, L)\)：

I₁₀: [R → L·, $]         ← 仅含 {$} 展望符！

\(I_{11} = \text{Goto}(I_6, *)\)：从 \([L \to \cdot *R, \$]\) 移点 → 闭包展开 \(R\) 和 \(L\)（展望符均为 \(\$\)）：

I₁₁: [L → *·R, $]
     [R → ·L,  $]
     [L → ·*R, $]
     [L → ·id, $]

\(I_{12} = \text{Goto}(I_6, \text{id})\)：

I₁₂: [L → id·, $]

\(I_{13} = \text{Goto}(I_{11}, R)\)：

I₁₃: [L → *R·, $]

转移关系汇总：

I₀ ──S──→ I₁    I₀ ──L──→ I₂    I₀ ──R──→ I₃
I₀ ──*──→ I₄    I₀ ─id──→ I₅
I₂ ──=──→ I₆
I₄ ──R──→ I₇    I₄ ──L──→ I₈    I₄ ──*──→ I₄    I₄ ─id──→ I₅
I₆ ──R──→ I₉    I₆ ──L──→ I₁₀   I₆ ──*──→ I₁₁   I₆ ─id──→ I₁₂
I₁₁──R──→ I₁₃   I₁₁──L──→ I₁₀   I₁₁──*──→ I₁₁   I₁₁─id──→ I₁₂

关键对比：展望符从哪里来

状态	项	展望符来源
\(I_2\)	\([R \to L \cdot, \$]\)	从 \(I_0\) 中 \(S' \to \cdot S\) 展开 \(R\) 时，\(\text{FIRST}(\$) = \{\$\}\)
\(I_8\)	\([R \to L \cdot, =]\)	从 \(I_4\) 中 \([L \to * \cdot R, =]\) 展开 \(R\) 时，\(\text{FIRST}(=) = \{=\}\)
\(I_8\)	\([R \to L \cdot, \$]\)	从 \(I_4\) 中 \([L \to * \cdot R, \$]\) 展开 \(R\) 时，\(\text{FIRST}(\$) = \{\$\}\)
\(I_{10}\)	\([R \to L \cdot, \$]\)	从 \(I_6\) 中 \([S \to L = \cdot R, \$]\) 展开 \(R\) 时，\(\text{FIRST}(\$) = \{\$\}\)

LR(1) 化解冲突：\(I_2\) 中 \([S \to L \cdot = R, \$]\) 要 shift =，\([R \to L \cdot, \$]\) 仅在 $ 上归约——shift 和 reduce 的触发 Token 不再重叠，冲突消除。

LR(1) 分析表：

State	id	*	=	$	S	L	R
0	s5	s4			1	2	3
1				acc
2			s6	r5
3			r2	r2
4	s5	s4				8	7
5		r4	r4	r4
6	s12	s11				10	9
7		r3	r3	r3
8		r5	r5	r5
9			r1	r1
10				r5
11	s12	s11				10	13
12				r4
13				r3

Trace — 输入 id = id：

栈	输入	动作
0	id=id$	s5
0id5	=id$	r4 (L→id), GOTO(0,L)=2
0L2	=id$	s6
0L2=6	id$	s12
0L2=6id12	$	r4 (L→id), GOTO(6,L)=10
0L2=6L10	$	r5 (R→L), GOTO(6,R)=9
0L2=6R9	$	r1 (S→L=R), GOTO(0,S)=1
0S1	$	acc

整个过程无冲突，每次决策唯一确定。

对比 SLR(1) 的 Trace：归约机制完全相同（弹出→暴露状态→查 GOTO），差异在于状态编号——LR(1) 多了 \(I_{10}\)、\(I_{12}\) 等状态（含精确展望符），归约触发条件也更精确（如状态 10 的 r5 仅在 $ 上归约，不在 = 上归约），从而消除了 SLR(1) 中 \(I_2\) 的冲突。

代价：LR(1) 有 14 个状态（LR(0) 仅 10 个），对于实际语言的状态数可达数千。

---

LALR(1)

核心思想：将 LR(1) 自动机中核心项相同（忽略展望符）的状态合并，保留展望符的并集。合并后状态数回溯至 LR(0)/SLR(1) 级别（本例中 10 个），而分析能力接近 LR(1)。

合并过程（对上例）：

LR(1) 状态对	核心项	合并后展望符
\(I_4 + I_{11}\)	\(L \to * \cdot R, R \to \cdot L, L \to \cdot *R, L \to \cdot id\)	\(\{=, \$\}\)
\(I_7 + I_{13}\)	\(L \to * R \cdot\)	\(\{=, \$\}\)
\(I_8 + I_{10}\)	\(R \to L \cdot\)	\(\{=, \$\}\)
\(I_5 + I_{12}\)	\(L \to id \cdot\)	\(\{=, \$\}\)

合并后得到 10 个状态，与 LR(0)/SLR(1) 结构相同，但带精确展望符。

LALR(1) 不会引入新的 shift-reduce 冲突（证明略），但可能引入 reduce-reduce 冲突（两个不同产生式的归约项合并后展望符重叠）。实际语言中很少发生。

---

LALR(1) Example — 合并后的分析表：

State	id	*	=	$	S	L	R
0	s5	s4			1	2	3
1				acc
2			s6	r5
3			r2	r2
4	s5	s4				8	7
5		r4	r4	r4
6	s5	s4				8	9
7		r3	r3	r3
8		r5	r5	r5
9			r1	r1

注意 \(I_2\)：reduce r5 仅在 $ 列（LR(1) 精确展望符带来的好处保留），= 列为纯 shift s6。冲突已消除。

2.4 Comparison

	LR(0)	SLR(1)	LR(1)	LALR(1)
展望符	无	FOLLOW 集	精确传播	合并后并集
状态数	最少	同 LR(0)	最多（可达 LR(0) 的 10 倍）	同 LR(0)
能力	最弱	较弱	最强	接近 LR(1)
工程使用	无	教学用	几乎不用（表太大）	Yacc/Bison 默认

表达能力链

LL(1) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1)。任何 LL(1) 文法也是 LR(1) 文法。实际编程语言的文法通常可用 LALR(1) 描述。

评论区

对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！