parsing - LR(1)项目的讨论：意义？

Question

什么是典型的 LR(1) 项目！我读过龙书，它让我很困惑，（delta，gamma，toh，...）

有人可以帮我解决这个问题吗？

这在英语中是什么意思？[A - > alpha.Bbeta , a]

非常感谢..

Answer 1

[A -> alpha . B beta , a]基本上意味着“假设规则A正在扩展，到目前为止我们已经看到alpha。然后我们期望看到B beta。我们也知道之后A，我们将看到一个a“

因此，在 CLR(1) 中，您拥有由其中一些项目组成的状态。然后你有很多选择：

• 如果前瞻 (gamma) 是 的成员first(B)，并且假设您有诸如 的规则B->gamma C，那么您可以“转移”并进入包含 的状态[B -> gamma . C, beta]。如您所见， the.已经通过gamma（因为gamma是匹配的，并且跟随的B是beta因为那是B规则中的内容A -> alpha B beta。
• 如果前瞻是a并且假设B beta可以生成lambda（空字符串）（在这里，假设 beta 是可以生成的非终结符lambda）。然后，您可以“减少”并进入包含规则的状态，例如C -> something A . a something_else, follow]. 在这种情况下，您已决定可以将堆栈上alpha的B和beta分组为一个A。

这是我能解释的最简单的方法。

Answer 2

IIRC，这是一个“项目”，即某些句子形式解析的潜在状态。

这意味着什么：

[A - > alpha.Bbeta , a]

是当尝试解析可以被视为非终结符A的（目标语言的子字符串）时，是否已经看到了alpha ，并且 (".")预计接下来会出现 Bbeta ，并且如果非终结符的元素可见，如果下一个标记是a ，则它是有效的 A。

（我认为您将 Bbeta 转录错了，它可能是书中的 beta）。