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

Question

所有的LL文法都是LR文法，但不是反过来，但我仍然在努力处理区别。我对没有等价LL表示的LR文法的小示例感到好奇。

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上的This post有很多关于这方面的参考资料