判断是否为LR(0)或SLR(1)文法

要判断一个文法是否为 LR(0) 文法 或 SLR(1) 文法，需遵循严格的形式化步骤，核心是通过构造LR(0) 项目集规范族和分析冲突（移进/归约、归约/归约） 的解决能力来区分。以下是详细判断流程，包含基础概念、LR(0) 判断步骤、SLR(1) 判断步骤及示例。

一、前置基础概念

在开始判断前，需明确以下核心术语，避免理解偏差：

术语	定义
LR(0) 项目	文法产生式的“中间状态”，形式为 `A→α·β`（`·` 表示当前分析位置）。例如 `S→·aAb` 表示待匹配 `a`，`S→a·Ab` 表示已匹配 `a`。
项目集规范族	所有 LR(0) 项目通过“闭包（Closure）”和“转移（Goto）”操作生成的集合，是 LR 分析的核心数据结构。
移进/归约冲突	同一项目集中存在两个项目：一个是“移进项目”（`A→α·aβ`，`a` 为终结符），另一个是“归约项目”（`B→γ·`，无后续符号），此时分析器无法确定是移进 `a` 还是归约 `γ`。
归约/归约冲突	同一项目集中存在两个及以上“归约项目”（`A→γ·` 和 `B→δ·`），此时分析器无法确定用哪个产生式归约。
FOLLOW 集	对非终结符 `A`，`FOLLOW(A)` 是所有可能紧跟在 `A` 后的终结符集合（含 `#`，表示输入结束符），是 SLR(1) 解决冲突的关键。

二、判断文法是否为 LR(0) 文法

LR(0) 文法是无任何冲突的文法——其项目集规范族中，所有项目集均无“移进/归约冲突”和“归约/归约冲突”。判断步骤分为 4 步：

步骤 1：构造“增广文法”

为确保文法有唯一的开始符号（避免多个开始符号导致的项目集混乱），需构造增广文法 G'：

设原文法 G 的开始符号为 S，新增一个开始符号 S'，并添加产生式 S'→S（唯一新增产生式）。
示例：原文法 G: S→aAb | b，增广文法 G': S'→S; S→aAb; S→b。

步骤 2：构造 LR(0) 项目集规范族

通过 Closure（闭包） 和 Goto（转移） 两个操作，生成所有项目集：

操作 1：计算闭包（Closure(I)）

对项目集 I，闭包是==“所有可直接或间接推导出的项目”的集合==，规则如下：

初始时，Closure(I) = I（包含 I 中所有项目）。
若 Closure(I) 中存在项目 A→α·Bβ（B 为非终结符，· 后紧跟 B），且 B 的产生式 B→γ 未生成项目 B→·γ，则将 B→·γ 加入 Closure(I)。
重复步骤 2，直到无新项目可加入。

操作 2：计算转移（Goto(I, X)）

对项目集 I 和符号 X（终结符或非终结符），Goto(I, X) 是“I 中所有 · 后紧跟 X 的项目，将 · 移到 X 右侧后形成的项目集的闭包”，规则如下：

先收集 I 中满足 A→α·Xβ 的项目，将 · 右移一位，得到临时项目集 J = { A→αX·β | A→α·Xβ ∈ I }。
计算 Closure(J)，即为 Goto(I, X)。

构造流程

初始项目集 I0 = Closure({ S'→·S })（从增广文法的开始项目出发）。
对每个已生成的项目集 I，遍历所有可能的符号 X（终结符 + 非终结符），若 Goto(I, X) 非空且未加入规范族，则将其加入，并标记为新的项目集（如 I1, I2, ...）。
重复步骤 2，直到无新项目集可生成。

步骤 3：检查项目集规范族的冲突

遍历所有项目集，判断是否存在冲突：

无冲突：所有项目集均无“移进/归约冲突”和“归约/归约冲突”→ 该文法是 LR(0) 文法。
有冲突：存在任一冲突→ 不是 LR(0) 文法，需进一步判断是否为 SLR(1) 文法。

示例：判断 LR(0) 文法

以文法 G: S→aA | bB; A→aA | ε; B→bB | ε（增广文法 G': S'→S）为例：

构造 I0 = Closure({ S'→·S }) = { S'→·S, S→·aA, S→·bB }（无冲突，均为移进项目）。
计算 Goto(I0, S) = Closure({ S'→S· }) = { S'→S· }（归约项目，无冲突，记为 I1）。
计算 Goto(I0, a) = Closure({ S→a·A }) = { S→a·A, A→·aA, A→·ε }（存在冲突：A→·aA 是移进项目，A→·ε 是归约项目）。

结论：因 I 存在“移进/归约冲突”，故该文法不是 LR(0) 文法。

三、判断文法是否为 SLR(1) 文法

SLR(1) 文法是 LR(0) 冲突可通过 FOLLOW 集解决的文法——其核心思想是：对冲突项目，通过“归约项目的非终结符 FOLLOW 集”与“移进符号/其他归约项目的 FOLLOW 集”是否不相交，来判断冲突是否可解决。

SLR(1) 的判断需在 LR(0) 项目集规范族 基础上，增加“计算 FOLLOW 集”和“冲突解决检查”两步：

步骤 1：计算所有非终结符的 FOLLOW 集

FOLLOW 集的计算规则（设 A 为非终结符，# 为输入结束符）：

初始规则：FOLLOW(S') = { # }（增广文法开始符号的 FOLLOW 集只有结束符）。
推导规则：
- 若有产生式 A→αBβ（B 后有符号 β），则 FIRST(β) 中所有终结符加入 FOLLOW(B)（FIRST(β) 是 β 能推导出的首个终结符集合）。
- 若有产生式 A→αB 或 A→αBβ 且 β→ε（B 在产生式末尾，或后续符号可空），则 FOLLOW(A) 中所有符号加入 FOLLOW(B)。
重复步骤 2，直到所有 FOLLOW 集不再变化。

步骤 2：用 FOLLOW 集解决 LR(0) 冲突

针对 LR(0) 项目集规范族中的冲突，分两种情况检查：

情况 1：解决“移进/归约冲突”

若项目集 I 中存在：

移进项目：A→α·aβ（移进符号为 a，终结符）。
归约项目：B→γ·（归约非终结符为 B）。

冲突可解决的条件：a ∉ FOLLOW(B)（移进符号 a 不在 B 的 FOLLOW 集中）。
→ 分析时，若当前输入符号是 a，则移进；若当前输入符号在 FOLLOW(B) 中，则归约；无重叠，冲突消除。

情况 2：解决“归约/归约冲突”

若项目集 I 中存在两个归约项目：

归约项目 1：A→γ·（归约非终结符 A）。
归约项目 2：B→δ·（归约非终结符 B）。

冲突可解决的条件：FOLLOW(A) ∩ FOLLOW(B) = ∅（两个非终结符的 FOLLOW 集无交集）。
→ 分析时，若当前输入符号在 FOLLOW(A) 中，用 A→γ 归约；若在 FOLLOW(B) 中，用 B→δ 归约；无重叠，冲突消除。

步骤 3：判断是否为 SLR(1) 文法

若 LR(0) 项目集规范族中的 所有冲突均可通过上述 FOLLOW 集规则解决 → 该文法是 SLR(1) 文法。
若存在任一冲突无法解决（如移进符号在 FOLLOW 集中，或 FOLLOW 集交集非空）→ 不是 SLR(1) 文法（需进一步判断 LALR(1) 或 LR(1)）。

示例：判断 SLR(1) 文法

延续上文示例（文法 G: S→aA | bB; A→aA | ε; B→bB | ε）：

计算 FOLLOW 集：
- FOLLOW(S') = { # }。
- FOLLOW(S)：由 S'→S，得 FOLLOW(S) = FOLLOW(S') = { # }。
- FOLLOW(A)：由 S→aA（A 在末尾），得 FOLLOW(A) = FOLLOW(S) = { # }；由 A→aA（A 在末尾），无新增，最终 FOLLOW(A) = { # }。
- FOLLOW(B)：同理，FOLLOW(B) = { # }。
检查冲突项目集 I：
- 项目集 I = { S→a·A, A→·aA, A→·ε } 中，冲突为“移进项目 A→·aA（移进符号 a）”和“归约项目 A→·ε（归约非终结符 A，FOLLOW(A)={#}）”。
- 检查条件：a ∉ FOLLOW(A)（a 不是 #）→ 冲突可解决。
其他项目集（如 Goto(I, b) 生成的项目集）冲突同理可解决。

结论：该文法是 SLR(1) 文法。

四、LR(0) 与 SLR(1) 文法的核心区别

对比维度	LR(0) 文法	SLR(1) 文法
冲突允许度	不允许任何冲突（移进/归约、归约/归约）	允许 LR(0) 冲突，但需通过 FOLLOW 集解决
分析能力	弱（仅覆盖部分无冲突文法）	强（覆盖更多含冲突但可解决的文法）
关键依赖	仅依赖 LR(0) 项目集规范族	依赖 LR(0) 项目集规范族 + 非终结符 FOLLOW 集
包含关系	LR(0) 文法 ⊂ SLR(1) 文法（所有 LR(0) 都是 SLR(1)）

五、判断流程

输入文法：确定文法的非终结符、终结符、产生式和开始符号。
构造增广文法：新增 S'→S，确保唯一开始符号。
生成 LR(0) 项目集规范族：通过 Closure 和 Goto 操作生成所有项目集。
判断 LR(0) 文法：
- 若所有项目集无冲突 → 是 LR(0) 文法（同时也是 SLR(1) 文法）。
- 若存在冲突 → 不是 LR(0) 文法，进入下一步。
计算所有非终结符的 FOLLOW 集：按 FOLLOW 规则推导。
判断 SLR(1) 文法：
- 若所有冲突均可通过 FOLLOW 集解决 → 是 SLR(1) 文法。
- 若存在无法解决的冲突 → 不是 SLR(1) 文法。