从“打架”到“和解”：一张图看懂LR(0)的冲突如何被SLR(1)的FOLLOW集解决

从“打架”到“和解”：一张图看懂LR(0)的冲突如何被SLR(1)的FOLLOW集解决

想象你站在一个没有红绿灯的十字路口（LR(0)状态机），突然两辆车同时到达路口中央——一辆要直行（移进动作），另一辆要左转（归约动作）。这就是编译原理中经典的移进-归约冲突。而SLR(1)的FOLLOW集就像突然出现的交通警察，通过分析车辆的目的地（非终结符的后续可能符号），给出明确的通行指令。

1. 冲突现场：当LR(0)分析表遇上歧义文法

在自底向上的语法分析中，LR(0)是最基础的自动机构造方法。它的核心是项目集规范族（Item Sets），每个项目集代表分析器可能处于的一个状态。但当文法存在歧义时，某些状态会出现多重选择：

I1状态示例： E' → E• (待接受) E → E•+T (可移进"+")

这种情况就像十字路口同时亮起绿灯和红灯。根据原始LR(0)规则：

• 如果选择E' → E•：执行归约动作（相当于左转）
• 如果选择E → E•+T：执行移进"+"（相当于直行）

冲突的根源在于LR(0)只关注当前状态的点位置（•），却忽略了上下文信息。这导致它在处理以下常见文法时会出现问题：

提示：LR(0)的"0"表示它不向前看任何符号，相当于盲人过马路——只能靠当前位置判断。

2. SLR(1)的智慧：用FOLLOW集充当交通信号灯

SLR(1)（Simple LR(1)）的改进思路非常巧妙：通过FOLLOW集预测下一个可能的符号。这相当于给每个驾驶员（归约动作）发放目的地通行证：

# 计算非终结符A的FOLLOW集伪代码 def compute_follow(grammar, A): follow = set() if A == grammar.start_symbol: follow.add('$') # 结束符 for production in grammar.productions: for pos, symbol in enumerate(production.rhs): if symbol == A: next_symbol = production.rhs[pos+1] if pos+1 < len(production.rhs) else None if next_symbol: if next_symbol.is_terminal: follow.add(next_symbol) else: follow |= grammar.FIRST[next_symbol] else: follow |= compute_follow(grammar, production.lhs) return follow

当遇到冲突时，SLR(1)会检查：

1. 所有可能移进的符号（•后的终结符）
2. 所有可能归约产生式左部非终结符的FOLLOW集

消解规则：

• 如果移进符号与所有FOLLOW集无交集 → 允许移进
• 如果FOLLOW集之间互不相交 → 允许选择对应归约
• 否则 → 文法不是SLR(1)

以经典表达式文法为例：

FOLLOW(E) = {+, ), $} FOLLOW(T) = {+, ), $}

当I1状态遇到"+"时：

• 移进项E→E•+T允许"+"
• 归约项E'→E•的FOLLOW(E')={$}
• "+" ∉ {$} → 选择移进

3. 可视化对比：冲突解决全流程

通过DFA状态转换图可以清晰看到差异：

LR(0)的冲突状态（I1）：

┌───────────────┐ │ I1 │ ├───────────────┤ │ E' → E • │ ← 归约路口 │ E → E • + T │ ← 移进路口 └───────────────┘ │ ↑ │ + │ ↓ │ ┌───────────────┐ │ I2 │ └───────────────┘

SLR(1)解决方案：

1. 检查归约项E'→E•的FOLLOW集：{$}
2. 检查移进符号："+"
3. "+" ≠ "$" → 排除归约，选择移进

关键对比表格：

4. 实战演练：从冲突到解决方案

让我们用具体文法演示全过程：

示例文法：

(0) S' → E (1) E → E + T (2) E → T (3) T → id

步骤1：构建LR(0)项目集族

• I0: [S'→•E, E→•E+T, E→•T, T→•id]
• I1: [S'→E•, E→E•+T] ← 冲突点!
• I2: [E→T•]
• I3: [T→id•]
• I4: [E→E+•T, T→•id]
• I5: [E→E+T•]

步骤2：计算FOLLOW集

FOLLOW(S') = {$} FOLLOW(E) = {+, $} FOLLOW(T) = {+, $}

步骤3：解决I1冲突

• 移进项：E→E•+T（允许"+"）
• 归约项：S'→E•（FOLLOW={$}）
• 交集检查："+" ∉ {$} → 可消解

最终SLR(1)分析表片段：

注意：实际实现时需要处理所有状态和符号，此处仅为关键部分示例。

常见踩坑点：

1. 忘记拓广文法（必须添加S'→S）
2. FOLLOW集计算遗漏闭包情况
3. 未区分不同非终结符的FOLLOW集
4. 错误地将FIRST集混入FOLLOW集计算

在构建真实编译器时，通常会采用更强大的LR(1)或LALR(1)方法。但理解SLR(1)的冲突解决机制，就像掌握交通调度原理——是构建更复杂系统的基石。