parsing - 不能用 LL 表示的 LR 文法的例子？

Question

所有 LL 语法都是 LR 语法，但不是相反，但我仍然很难处理这种区别。我很好奇没有等效 LL 表示的 LR 语法的小例子（如果有的话）。

Answer 1

好吧，就语法而言，它很容易——任何简单的左递归语法都是 LR（可能是 LR(1)）而不是 LL。所以一个列表语法像：

list ::= list ',' element | element

是 LR(1)（假设元素的产生是）但不是 LL。这样的文法可以很容易地通过左因子等转换为 LL 文法，所以这并不太有趣。

更有趣的是 LR 但不是 LL 的 LANGUAGES - 这是一种存在 LR(1) 语法但没有任何 k 的 LL(k) 语法的语言。一个例子是需要可选尾随匹配的东西。例如，语言中任意数量的a符号后跟相同数量或更少的b符号，但不能更多bs -- { a^ib^j | 我 >= j }。有一个简单的 LR(1) 语法：

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

但没有 LL(k) 语法。原因是 LL 文法在查看 a 时需要决定是匹配 a+b 对还是匹配奇数 a，而 LR 文法可以将这个决定推迟到它看到 b 或输入的结尾之后。

cs.stackechange.com 上的这篇文章有很多关于此的参考