3

为 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)?

4

1 回答 1

6

如果一种语言有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)存在语法,但远没有那么干净。

于 2013-11-26T04:50:08.163 回答