context-free-grammar - 合并 LR 状态以形成 LALR 语法分析的集合

Question

如果假设我有以下状态：

I1: S->TaV.,$

T -> V.,a

I2: T -> V.,a|$

我会合并这些州吗？

基本上，我想知道I1的核心是什么。是 { S->TaV。, T->V。I1 的核心还是我会说 I1 包含两个核心 - S->TaV & T->V？

Dragonbook 说，对于 LR(1) 项目集合中存在的每个核心，找到所有具有该核心的集合，并将其替换为它们的并集。

现在，如果 { S->TaV。, T->V。} 是I1的核心，那我就不合并集合了。但是，对于核心T->V。，I1 和 I2 都包含核心，因此必须用它们的并集替换。

那么我应该合并集合吗？

一些可能有用的背景细节：

最初的语法是

G: S->TaV | T

T->V | b

V->Ta | c

Answer 1

LALR(1) 解析器生成器不会真正合并状态。它检查是否已经创建了新创建的状态。它通过比较核心项目将新状态与所有其他状态进行比较。如果核心项目是相同的（相同数量的项目和相同的项目），那么新创建的状态将被丢弃并且转换应该进入旧状态。

LALR(1) 解析器生成器构建 LR(0) 状态机，并且在状态构建过程中不关心前瞻。它只关心项目集。所以答案是否定的，这两个状态不应该合并，因为 I1 有 2 个核心项目，而 I2 有 1 个核心项目。

合并状态的想法适用于最小 LR(1) 状态构造，这是一个比 LR(0) 状态构造更复杂的过程。

这是一个 LALR 语法分析问题，而不是语法解析问题。