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

Question

Создание искусственных LR (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 (к> 1) - оформленной?
Или языки, отличные от LR (1), также не LR (k)?

Answer 1

Если язык имеет грамматику LR(k), то у него есть грамматика LR(1), которая может быть сгенерирована механически из грамматики LR(k); кроме того, исходное дерево разбора можно воссоздать из дерева разбора LR(1). Доказательство этой теоремы появилось в разделе 6.7 теории парсинга. II, Sippu & Soisalon-Soininen; они приписывают его «О полной проблеме покрытия для грамматик LR (k)» (1976), MD Mickunas, в JACM 23: 17-30.

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

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