# 编译原理(一) · LR(0)/SLR(1)文法

原文：https://blog.tonks.top/posts/bianyiyuanli1/

题型比较好理解，但是考得好难好复杂，算不过来了要。闲下来翻翻ppt和网课，倒点垃圾，希望期末能过：

一个**项目（Item）** 的形式是：`A → α . β`

- 点`.` 表示当前分析进度。
- `α` 是已经看到/规约的部分。
- `β` 是期望接下来看到的部分。

***

### LR(0)文法与分析表构建

**仅根据项目本身来决定动作，不看向前看符号。**

**第1步：文法拓广**

- 目的：使构造的DFA有唯一的初态和唯一的接受状态。
- 方法：增加一个新的开始符号`S'`，并添加产生式 `S' → S`（其中`S`是原文法的开始符号）。

**第2步：计算LR(0)项目集的闭包（Closure）**

- **规则**：如果项目集 I 中包含 `A → α . B β`，那么对于所有 `B → .γ`，也要加入到 I 中。
- **通俗理解**：看到一个非终结符`B`，就要把`B`所有可能的产生式（点在最左边的项目）都考虑进来。

**第3步：计算状态转换（Goto）**

- **规则**：对于项目集 I 和文法符号 X（终结符或非终结符），`Goto(I, X) = Closure( { A → α X . β | A → α . X β 属于 I } )`。
- **通俗理解**：从状态 I “吃掉”一个符号 X 后，我们能到达哪些新的项目集？计算这个新集合的闭包，就是一个新状态。

**第4步：构造LR(0)项目集规范族（即DFA的所有状态）**

1. 从拓广文法的初始项目集 `I₀ = Closure( { [S' → .S] } )` 开始。
2. 不断对每个状态 I 和每个文法符号 X 应用 `Goto(I, X)` 函数，直到不再产生新的状态为止。
3. 每个 `Goto(I, X)` 都是一条从状态 I 到新状态的标记为 X 的边。

**第5步：填充LR(0)分析表（ACTION表 和 GOTO表）**
对于每个状态 Iᵢ：

1. **移进动作（Shift）**：
   - 如果项目 `A → α . a β` 在 Iᵢ 中，且 `a` 是终结符，同时 `Goto(Iᵢ, a) = Iⱼ`。
   - **动作**：在 ACTION表的 `[i, a]` 格填 `sⱼ`（表示移进a，并转移到状态j）。
2. **规约动作（Reduce）**：
   - 如果项目 `A → α .` 在 Iᵢ 中（**点在最右端，称为规约项目**），并且它**不是** `S' → S .`（接受项目）。
   - **动作**：对于**所有**的终结符 `a`（包括结束符`$`），在 ACTION表的 `[i, a]` 格填 `rₖ`（k是产生式 `A → α` 的编号）。
3. **接受动作（Accept）**：
   - 如果项目 `S' → S .` 在 Iᵢ 中。
   - **动作**：在 ACTION表的 `[i, $]` 格填 `acc`。
4. **GOTO表**：
   - 如果 `Goto(Iᵢ, A) = Iⱼ`，且 A 是非终结符。
   - **动作**：在 GOTO表的 `[i, A]` 格填 `j`。

**第6步：检查冲突**

- 如果一个状态（项目集）中同时出现：
  - **移进-规约冲突**：既有 `A → α . a β`，又有 `B → γ .`。
  - **规约-规约冲突**：既有 `A → α .`，又有 `B → β .`。
- 如果存在任何冲突，则该文法**不是LR(0)文法**。

***

### SLR(1)文法与分析表构建

SLR(1)是对LR(0)的简单改进。核心思想是：**在规约时，使用Follow集来解决LR(0)中不必要的冲突。**

#### **SLR(1) 做题步骤**

**第1步 \~ 第4步**：与LR(0)完全相同。

1. 拓广文法。
2. 构造LR(0)项目集规范族（DFA）。

**第5步：计算所有非终结符的Follow集**

**第6步：填充SLR(1)分析表（与LR(0)的关键区别）**
对于每个状态 Iᵢ：

1. **移进动作（Shift）**：与LR(0)完全相同。
   - 如果 `A → α . a β` 在 Iᵢ 中，且 `a` 是终结符，`Goto(Iᵢ, a) = Iⱼ`。
   - ACTION `[i, a]` = `sⱼ`。
2. **规约动作（Reduce）**：**【这是关键区别！】**
   - 如果项目 `A → α .` 在 Iᵢ 中，并且它**不是** `S' → S .`。
   - **动作**：对于**所有**属于 `Follow(A)` 的终结符 `a`，在 ACTION表的 `[i, a]` 格填 `rₖ`。
   - **注意**：不再是像LR(0)那样对所有终结符都规约！
3. **接受动作（Accept）**：与LR(0)完全相同。
   - 如果 `S' → S .` 在 Iᵢ 中。
   - ACTION `[i, $]` = `acc`。
4. **GOTO表**：与LR(0)完全相同。

**第7步：检查冲突**

- 检查分析表的每个格子：
  - 如果同一个格子被定义了多个动作（例如，既有`sⱼ`又有`rₖ`，或者有多个`rₖ`），则存在**冲突**。
  - 如果存在移进-规约或规约-规约冲突，则该文法**不是SLR(1)文法**。

***

### 第三部分：解题思路总结与对比

| 特性       | LR(0)                          | SLR(1)                                               |
| :------- | :----------------------------- | :--------------------------------------------------- |
| **能力**   | 最弱                             | 比LR(0)强，比LR(1)弱                                      |
| **核心区别** | **只看状态，不看符号**                  | **规约时看Follow集**                                      |
| **规约动作** | 状态中有 `A → α .`，就对**所有**输入符号规约  | 状态中有 `A → α .`，只对 `Follow(A)` 中的输入符号规约               |
| **冲突解决** | 无法解决任何冲突，有冲突就不是LR(0)           | 能用Follow集解决**部分**LR(0)的移进-规约和规约-规约冲突                 |
| **构造步骤** | 1. 拓广 2. 构造DFA 3. 填表（规约动作填满一行） | 1. 拓广 2. 构造DFA 3. **求Follow集** 4. 填表（规约动作只填Follow集列） |

#### **通用做题流程**

1. **判断题目要求**：是判断文法类型，还是构造分析表？
2. **无脑开始构造**：
   - 拓广文法。
   - 从 `I₀` 开始，逐步计算闭包和Goto，画出完整的LR(0)项目集规范族（DFA图）。**这一步是基础，LR(0)和SLR(1)共用。**
3. **如果是LR(0)**：
   - 尝试填LR(0)表。
   - **检查**：在构造DFA的过程中，如果发现任何一个状态同时包含移进项目和规约项目，或者包含多个规约项目，**直接判定不是LR(0)文法**。
4. **如果是SLR(1)**：
   - 计算所有非终结符的 **Follow集**。
   - 基于第2步的DFA和Follow集来填SLR(1)表。
   - **检查**：填表时，如果发现同一个ACTION格子需要填入两种不同的动作（如`s`和`r`，或两个`r`），则**判定不是SLR(1)文法**。如果没有冲突，就是SLR(1)文法。

## 依旧网课