parsing - 真实世界的 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(k > 1) 可解析的非 LR(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 中的“On the complete covering problem for LR(k) grammars”(1976 年)。

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

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