理解一个语法是否是 LR(1) 没有解析 table

Question

我找到了一个练习，它需要一个技巧来理解语法是否是 LR(1)，没有解析 table 操作。

语法如下：

S -> Aa | Bb
A -> aAb | ab
B -> aBbb | abb

你知道背后的套路是什么吗？

谢谢，:)

Answer 1

假设您是一个 LR(1) 解析器，并且您刚刚阅读了 aab，并提前阅读了 b。（我知道，你可能在想"man, that happens to me all the time!"）你到底应该在这里做什么？

看语法，你无法判断初始产生式是Aa还是Bb，所以你将不得不同时考虑A的产生式规则和 B。如果您查看 A 选项，您会发现这里的一个选项是减少 A → ab，这在这里是合理的，因为前瞻是 b这正是您在扩展 A 时看到 ab 后期望找到的内容（请注意有规则 A → aRb，因此任何递归扩展As 后跟 b)。所以这告诉你减少。另一方面，查看 B 选项。如果您看到 aab 后跟 b，您会想 "oh, that second b is going to make aabb, and then I'd go and reduce B → abb, because that's totally a thing I like to do because I'm an LR(1) parser." 所以这告诉您换档。那时，砰！你有一个 shift/reduce 冲突，所以你几乎肯定不会有 LR(1) 语法。

那真的发生了吗？好吧，让我们开始构建 LR(1) 配置集，如果我们确实阅读了 aab 并看到 b 作为前瞻：

Initial State
S' -> .S    [$]
S  -> .Aa   [$]
S  -> .Bb   [$]
A  -> .aAb  [a]
A  -> .ab   [a]
B  -> .aBbb [b]
B  -> .abb  [b]

State after reading a
A  -> a.Ab  [a]
A  -> a.b   [a]
A  -> .aAb  [b]
A  -> .ab   [b]
B  -> a.Bbb [b]
B  -> a.bb  [b]
B  -> .aBbb [b]
B  -> .abb  [b]

State after reading aa
A  -> a.Ab  [b]
A  -> a.b   [b]
A  -> .aAb  [b]
A  -> .ab   [b]
B  -> a.Bbb [b]
B  -> a.bb  [b]
B  -> .aBbb [b]
B  -> .abb  [b]

State after reading aab
A  -> ab.   [b]
B  -> ab.b  [b]

嘿！这就是我们正在谈论的 shift/reduce 冲突。第一项在 b 上减少，但第二项在 b 上移动。所以你去吧！我们的直觉使我们认为这不会是 LR(1) 文法，如果我们查看表格，证据将得到数据支持。

那你怎么知道要试试呢？好吧，总的来说，这很难做到。至少对我来说，主要线索是解析器必须猜测它在某个时候是想要 A 还是 B，但它打破平局的方式是 b 的数量.解析器将不得不在某个时候确定它是否喜欢 ab 并使用 A 或它是否喜欢 abb 并使用 B，但它可以在做出决定之前，请先查看两个 b。这让我想到我们想要找到某种冲突，我们已经看到足够多的东西知道发生了一些递归（这样尾随 b 会导致问题）并找到一个地方两个产生式规则之间的递归会有所不同。

理解一个语法是否是 LR(1) 没有解析 table

Understand whether a grammar is LR(1) with no parsing table

parsing

context-free-grammar

lr