现实世界的 LR(k > 1) 文法？

Question

为 k > 1 制作人工 LR(k) 文法很容易：

Input: A1 B x
Input: A2 B y                   (introduce reduce-reduce conflict for terminal a)
A1   : a
A2   : a
B    : b b b ... b              (terminal b occurs k-1 times)

然而，是否有任何现实世界的非 LR(1) 计算机语言是 LR(k > 1) 可解析的？
或者非 LR(1) 语言也不是 LR(k)？

Answer 1

如果一种语言有LR(k)语法，那么它就有一个LR(1)可以从LR(k)语法中机械生成的语法；此外，可以从LR(1)解析树重新创建原始解析树。该定理的证明出现在 Parsing Theory Vol. 6.7 节。II, Sippu & Soisalon-Soininen; 他们将其归因于 MD Mickunas 在 JACM 23:17-30 中的“关于 LR(k) 语法的完整覆盖问题”（1976 年）。

因此，没有可解析的语言，LR(k)因为k>1它也不能解析为LR(1)，因此对于0 和 1 以外的值，确实没有诸如LR(k) 语言之类的东西k。

但是，有些语言的LR(2)语法要容易得多。一个经典的例子是 Posix 语法 for yacc，它不要求产生式以 结束;。这是明确的，因为产生式必须以标识符开头，后跟冒号。这样写，语法就清楚了LR(2)；根据上述定理，LR(1)存在一个语法，但它远没有那么干净。