parsing - LR解析中需要S'->S

Question

有人告诉我，如果没有添加规则 S->S'，我们可能会接受语法语言中不存在的单词，有人能想出一个很好的例子吗？此外，您是否有减少 SLR 解析到多个状态的示例？

Answer 1

您需要这个额外的生产规则的主要原因是能够确定您何时真正完成了对输入字符串的读取。如果你不包括它，你可能会得到一些误报。

例如，考虑以下语法：

S → aS | b

让我们想象一下，我们没有用额外的 start 产生式来扩充这个语法，而是开始为它构建一个 LR(0) 解析器。我们将恢复这些状态

(1)
S -> .aS
S -> .b

(2)
S -> b.

(3)
S -> a.S
S -> .aS
S -> .b

(4)
S -> aS.

现在，假设我们使用这个 LR(0) 解析器来解析字符串 abb。请注意，这个字符串不是语法语言，所以我们不应该接受它。这是发生的事情的痕迹：

 Stack              | State | Input            |  Action
 -------------------+-------+------------------+----------
                    |  (1)  | abb              | Shift, go to (3)
 a                  |  (3)  | bb               | Shift, go to (2)
 ab                 |  (2)  | b                | ???

所以这就是问题所在。在这种状态下，我们有一个归约项 S → b。现在，我们是否在这里做 reduce 并继续解析？还是我们完成了解析？如果我们选择在此停止，我们将错误地报告该字符串在该语言中，即使它实际上并不存在。如果我们不选择在此停止，那么我们将正确解析输入，但这意味着如果我们获得了不同的输入（例如，只是字符 b），那么我们可能会在我们真的应该只是停止解析。此处使用 SLR(1) 解析器无法解决此问题，因为前瞻无法帮助我们区分这些情况。

通过在开始时添加额外的产生式，我们可以明确地区分“我已经与开始符号匹配了一些东西”和“我完全完成了”，因为解析器只有在完成减少时才会考虑该产生式S 并且解析堆栈为空。