Реальные грамматики LR(k > 1)?

Question

Создание искусственных LR(k) грамматик для k > 1 легко:

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) разбирать дерево. Доказательство этой теоремы приведено в разделе 6.7 Теории синтаксического анализа. II, Sippu & Soisalon-Soininen; они приписывают это "О проблеме полного покрытия для грамматик LR(k)" (1976) М. Д. Микунасом, в JACM 23:17-30.

Таким образом, нет разбираемого языка как LR(k) за k>1 который также не разбирается как LR(1)и, следовательно, действительно нет такой вещи как LR(k) язык для значений k кроме 0 и 1.

Тем не менее, есть языки, для которых LR(2) грамматика намного проще. Одним из классических примеров является грамматика Posix для yacc, который не требует прекращения производства с ;, Это однозначно, потому что производство должно начинаться с идентификатора, за которым следует двоеточие. Написано таким образом, грамматика четко LR(2); по приведенной выше теореме LR(1) грамматика существует, но она не так чиста.