LR(0)/SLR(1)文法学习笔记#

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

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

第1步：文法拓广

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

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

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

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

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

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

第6步：检查冲突

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

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

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

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

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

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

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