这是语法 LR(2) 吗？我如何确定它？

Question

为了确定我的解析器是否正常工作，我需要找到 lr(2+) 语法。经过快速研究后，我发现了这个语法，我相信它是 lr(2)。但是，我不确定如何确定这一点。

Terminals: b, e, o, r, s
NonTerminals: A, B, E, Q, SL
Start: P
Productions:
P -> A
A -> E B SL E | b e
B -> b | o r
E -> e | Ɛ
SL -> s SL | s

我很高兴，如果有人能够确认或否认这个语法是 lr(2) 并且最多给我一个简短的解释如何自己确定它。

非常感谢！

Answer 1

我很确定它是 LR(2)，但我没有方便的 LR(2) 解析器生成器来测试它，这将是进行测试的最终方法。当然，您可以手动生成解析器表。语法不是那么复杂，所以不会花你太长时间。

肯定不是LR(1)，从一对输入可以看出：

b e
b s e

最左边的推导是：

P->A->b e
P->E B SL E->B SL E->b SL E->b s E->b s e

因此在解析开始时，解析器可以移动 b 以便遵循第一个推导链，或者将空序列减少到 E 以便继续第二个推导链衍生链。需要第二个标记才能在这两个选项之间进行选择，因此至少需要 2 个先行。

附带说明一下，为 LR(2) 语法挖掘 Whosebug 应该非常简单；他们不时提出问题。这是我通过搜索 LALR(2) 找到的一些：（我使用 Google 搜索 site:whosebug.com 因为 SO 自己的搜索引擎不能很好地处理不是单词的搜索模式。不Google 做得很好，但确实做得更好。）

Persistent Shift - Reduce Conflict in Goldparser

我没有验证那些问题和答案中的说法，还有其他问题似乎没有那么明确的结果。

最经典的LALR(2)文法是Yacc本身的文法，有点讽刺。这是一个简化版本：

grammar: %empty | grammar production
production: ID ':' symbols
symbols: %empty | symbols symbol
symbol: ID | QUOTED_LITERAL

这个简单的语法省略了操作和可选的分号。但它抓住了语法的 LALR(2)-ness 的本质，这恰恰是分号是可选的结果。那不是抱怨；语法是明确的，所以分号真的是多余的，没有人应该被迫输入多余的标记:-)

这是语法 LR(2) 吗？我如何确定它？

Is this grammar LR(2) and how can i determine it?

grammar

parsing

computation-theory

lr