将LR状态合并为用于LALR语法分析的集合



如果假设我有以下状态:

I1: S->TaV.,$

T -> V.,a

I2: T -> V.,a|$

我会合并这些州吗?

基本上,我想知道I1的核心是什么。是{S->TaV.,T->VT->V

Dragonbook说,对于LR(1)项目集合中的每个核心,找到所有具有该核心的集合,并用它们的并集替换它。

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

那么我应该合并这些集合吗?

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

最初的语法是

G: S->TaV | T

T->V | b

V->Ta | c

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

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

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

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

最新更新