不能用LL表示的LR语法的例子是什么？

Question

所有的LL文法都是LR文法，但反之则不然，但我仍然很难区分它们。如果存在的话，我很好奇是否有一些LR文法没有等效的LL表示的小例子。

- Puppy

Answer 1

好的，就语法而言，很容易理解——任何简单的左递归语法都是LR（可能是LR(1)），而不是LL。因此，像下面这样的列表语法：

list ::= list ',' element | element

假设元素的产生式是，LR（1）可行的（但假设它不是LL）。这些语法可以通过左因子化等方式很容易地转换为LL语法，因此并不太有趣。

更有趣的是那些LR但不是LL的“语言”--也就是对于这样的语言，存在一个LR（1）文法，但没有任何k的LL(k)文法。例如，需要可选尾随匹配的事物。例如，任意数量的a符号，后跟相同数量或更少的b符号的语言，但不包括更多的bs - {a^i b^j | i >= j}。有一个微不足道的LR（1）文法：

S ::= a S | P
P ::= a P b | \epsilon

但没有LL(k)文法。原因是LL文法需要在查看a时决定匹配a+b对还是奇数a，而LR文法可以推迟该决策，直到看到b或输入结束。

这篇cs.stackechange.com上的帖子有很多相关参考资料。

- Chris Dodd

---

那似乎相当不可能。语法似乎很匹配 if/else - 即，statement :: = if (...) statement | if (...) statement else (...) statement。据我所知，这在 LL 解析器中是可以处理的。 - Puppy

正如@DeadMG所指出的那样，悬挂else语法是相同的模式，这就是为什么它不是LL，并且不能被任何LL解析器干净地处理。当然，使用手写解析器，您可以使用特别的解决方法（通常是针对此情况的迷你LR解析器），但这并不改变语法不是LL的事实。 - Chris Dodd

有趣。这是否意味着几乎所有遵循此结构的语言都具有非LL语法，而几乎所有LL解析器生成器都必须有解决方法？ - Puppy

是的。这个非LL问题就是为什么许多语言都有一个endif或其他结束标记，必须与if匹配，因为这使得语言再次成为LL。 - Chris Dodd

@ChrisDodd：抱歉，但“平凡的LR（1）语法”是有歧义的，因此它不能是LR：aab有两个不同的解析树，其中第一个或第二个S的替代方案可以作为根。此外，我不会说“任何左递归语法都是LR”，但您可能想说“任何左递归LR语法都不是LL”。 - Gunther

@Gunther：哎呀，你说得对——我不小心简化了语法；它需要第二个非终结符来解决歧义。 - Chris Dodd