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) 文法——

• 无左递归 — 立即左递归 \(A \to A\alpha \mid \beta\) 改写为 \(A \to \beta A',\; A' \to \alpha A' \mid \varepsilon\)；间接左递归通过代入后消除。
• 已提取左公因子 — \(A \to \alpha\beta_1 \mid \alpha\beta_2\) 改写为 \(A \to \alpha A',\; A' \to \beta_1 \mid \beta_2\)。
• FIRST/FOLLOW 不相交 — 对每个可推出 \(\varepsilon\) 的非终结符 \(A\)，需 \(\text{FIRST}(A) \cap \text{FOLLOW}(A) = \emptyset\)，否则预测表一格出现多条产生式（如 dangling-else）。

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 集来的，而是从该项所在的具体上下文推导出来的。

初始展望符：增广文法引入 \(S' \to S\) 作为新的开始符号，整个输入为 $S$ $——即 \(S\) 后必是输入结束符。因此种子项为 \([S' \to \cdot S,\; \$]\)，最初的展望符就是 \(\$\)。之后的展望符全部通过下面的 Closure 规则从已有项推导出来。

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_0 = \text{Closure}(\{[S' \to \cdot S,\; \$]\})\)。从 \([S' \to \cdot S, \$]\) 展开 \(S\)、再展开 \(R\) 和 \(L\)（每次按 \(\text{FIRST}(\beta a)\) 计算展望符）：

I₀:
  [S' → ·S,   $]
  [S  → ·L=R, $]    ← FIRST(ε$) = {$}
  [S  → ·R,   $]
  [L  → ·*R,  =]    ← FIRST(=R$) = {=}
  [L  → ·*R,  $]    ← FIRST(ε$) = {$}
  [L  → ·id,  =]
  [L  → ·id,  $]
  [R  → ·L,   $]

关键：\([L \to \cdot *R, =]\) 和 \([L \to \cdot *R, \$]\) 核心相同但展望符不同——LR(0) 合为一个，LR(1) 分开保留，后续走向不同状态，这正是精确性的来源。

其余状态由 Goto 构造（移点 + 闭包，展望符不变传播），列出关键状态：

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

I₂:  [S → L·=R, $]    ← shift = 和 reduce r5 的展望符不同，冲突消除！
     [R → L·,   $]    ← 仅对 $ 归约，因为展望符来自 S'→·S 时 FIRST($)={$}

I₃:  [S → R·, $]

I₄:  [L → *·R, =]  [L → *·R, $]     ← {=} 和 {$} 两组展望符成对
     [R → ·L, =]   [R → ·L, $]
     [L → ·*R, =]  [L → ·*R, $]
     [L → ·id, =]  [L → ·id, $]

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

I₆:  [S → L=·R, $]                   ← 全部展望符为 {$}，因为入边来自 I₂ 的 shift =
     [R → ·L,   $]
     [L → ·*R,  $]
     [L → ·id,  $]

I₇:  [L → *R·, =]  [L → *R·, $]
I₈:  [R → L·, =]   [R → L·, $]       ← 后面 LALR(1) 将合并 I₈ 与 I₁₀
I₉:  [S → L=R·, $]
I₁₀: [R → L·, $]                      ← 仅含 {$}，将与 I₈ 合并
I₁₁: [L → *·R, $]  [R → ·L, $] ...   ← 结构同 I₄ 但全是 {$} 展望符
I₁₂: [L → id·, $]
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₁₂

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 冲突（两个不同产生式的归约项合并后展望符重叠）。实际语言中很少发生。

Reduce-Reduce 冲突示例

S → x X | Y y | Z z
X → Y z | Z y
Y → W
Z → W
W → ε

\(Y\) 和 \(Z\) 在不同上下文中出现——\(S \to Y y\)（Y 后跟 y）vs \(X \to Y z\)（Y 后跟 z）。\(Z\) 同理但上下文相反（\(S \to Z z\) 跟 z，\(X \to Z y\) 跟 y）。

LR(1) 产生两个同心状态，展望符恰好交换：

• 状态 A：\(\{[Y \to W \cdot, \mathbf{y}], [Z \to W \cdot, \mathbf{z}]\}\) — 输入 y 归 Y，输入 z 归 Z，不冲突。
• 状态 B：\(\{[Y \to W \cdot, \mathbf{z}], [Z \to W \cdot, \mathbf{y}]\}\) — 输入 z 归 Y，输入 y 归 Z，不冲突。

LALR(1) 将 A 和 B 合并，展望符取并集：

\[\{[Y \to W \cdot, \{\mathbf{y}, \mathbf{z}\}],\; [Z \to W \cdot, \{\mathbf{y}, \mathbf{z}\}]\}\]

输入 y 时 \(Y \to W \cdot\) 和 \(Z \to W \cdot\) 都想归约 → reduce-reduce 冲突（z 同理）。核心原因：\(Y = W\) 且 \(Z = W\) 都是可空产生式，不同上下文下的展望符发生了置换，合并后互相覆盖。

如何快速判断 LALR(1)？ 没有简单的充要条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 =>
欢迎跟我探讨！！！