该语法可以用于 LALR(1) 解析器吗？

Question

我有以下语法：

S -> aSb
S -> c

在不冲突的情况下，它可以用于 LR(1) 解析器。然而，当我将状态与相同的 LR(0) 项和不同的前瞻组合起来时，我得到了一个 LALR(1) 的解析表，它不包含任何已知的冲突（shift-shift、shift-reduce、reduce-reduce），但是我ACTION-GOTO 表的 GOTO 部分发生冲突。也就是说，在一个非终结符的单元格中，我得到 2 种可能的状态。从未见过任何相同的例子，所以想确认一下。

尝试搜索龙书、网上参考资料；没有遇到任何例子。

Answer 1

你在状态合并过程中肯定犯了一个错误。

这是示例语法的规范 LR(1) 自动机，其中等效状态（LR(0) 核心）用颜色标记：

我不会详细说明逐步合并过程，但希望您可以按照

7=9

、

4=8

、

2=5

和

3=6

等顺序进行操作，以获得最终的 LALR( 1) 自动机（保留颜色来源）：

在经历这个相当繁琐的状态合并过程时，很容易犯错误。从理论上讲，在构建过程中进行状态合并通常比事后更容易。

---

出于教育目的，我必须指出，这并不是获得 LALR(1) 的非常方便的方法。我不会详细介绍所有细节，但您可以使用 DeRemer 和 Pennello 的著名论文LALR 的高效计算中的思想轻松（在本例中）将 LR(0) 自动机升级为 LALR(1) (1) 前瞻集.

特别是，当语法没有可为空的符号时，整个基于关系的方法不需要中间计算（该算法的大部分复杂性就在于此） - 因此，reduce 项的前瞻正是可以通过其相应的“直接读取的终端”回顾”过渡。

您可以通过在心里查看拼出reduce项的生产主体的路径来识别回溯链接：

那些绿线表示每个归约项的“回溯”关系（您可以通过拼出产生式主体的符号从每个状态向后搜索，以找到这些转换）。紧随相关非终结符转换之后的终结符位于相应归约项的先行集中。

如果您知道没有任何内容可以为空，那么这种方法在纸面上通常会更有效。