所有 LL 语法都是 LR 语法,但反之则不然,但我仍然很难区分。我对没有等效 LL 表示的 LR 语法的小示例(如果存在)感到好奇。
最佳答案
嗯,就语法而言,很简单——任何简单的左递归语法都是 LR(可能是 LR(1))而不是 LL。所以列表语法如下:
list ::= list ',' element | element
是 LR(1)(假设元素的产生式是),但不是 LL。这样的语法可以通过左因子分解等相当容易地转换为 LL 语法,所以这并不是太有趣。
更令人感兴趣的是 LR 但不是 LL 的语言——这种语言存在 LR(1) 语法,但对于任何 k 都没有 LL(k) 语法。一个例子是需要可选尾随匹配的事物。例如,任意数量的 a
符号后跟相同数量或更少的 b
符号的语言,但不能有更多的 b
-- { a^i b^j | a^i b^j |我 >= j }。有一个简单的 LR(1) 语法:
S ::= a S | P
P ::= a P b | \epsilon
但没有 LL(k) 语法。原因是 LL 语法在查看 a 时需要决定是匹配 a+b 对还是奇数 a,而 LR 语法可以推迟该决定,直到看到 b 或输入末尾之后。
This post cs.stackechange.com 上有很多关于此的引用
关于parsing - 无法用 LL 表示的 LR 语法示例?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8809545/