LR句法分析中S'->S的需求

Question

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

Answer 1

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

举个例子，考虑一下下面的语法：

S→aS |b

假设我们没有使用额外的start production来扩充这个语法，而是开始为它构建一个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                | ???

所以问题来了。在这个状态下，我们有一个reduce项目S→b。现在，我们在这里做reduce并继续解析吗？或者我们已经完成解析了吗？如果我们选择停在这里，我们将错误地报告字符串在语言中，即使它实际上并不在那里。如果我们不选择在这里停止，那么我们将正确地解析输入，但这意味着如果我们获得了不同的输入(例如，只有字符b)，那么在我们真的应该停止解析的情况下，我们可能会减少。这里使用SLR(1)解析器不能解决这个问题，因为lookahead不能帮助我们区分这些情况。

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