Теоретико-языковое сравнение грамматик LL и LR

68

Люди часто говорят, что парсеры LR (k) более мощные, чем парсеры LL (k) . Эти заявления в большинстве случаев расплывчаты; в частности, следует ли сравнивать классы для фиксированного или объединения по всем ? Так как на самом деле ситуация? В частности, меня интересует, как вписывается LL (*).kk

Насколько я знаю, соответствующие наборы грамматик, принимаемые синтаксическими анализаторами LL и LR, являются ортогональными, поэтому давайте поговорим о языках, генерируемых соответствующими наборами грамматик. Пусть обозначает класс языков, порожденных грамматиками, которые могут быть проанализированы синтаксическим анализатором и аналогичным для других классов.LR(k)LR(k)

Я заинтересован в следующих отношениях:

  • LL(k)?LR(k)
  • i=1LL(k)?i=1LR(k)
  • i=1LL(k)=?LL()
  • LL()?i=1LR(k)

Некоторые из них, вероятно, легко; Моя цель - собрать «полное» сравнение. Рекомендации приветствуются.

Рафаэль
источник
2
Может быть, это может помочь вам! Изображение грамматики иерархии
Андреа Туччи
1
@AndreaTucci: Да, но это касается только грамматики, а не сгенерированных языков.
Рафаэль

Ответы:

61

Существует множество известных условий содержания. Пусть обозначает сдерживание, а собственно сдерживание. Пусть обозначает несопоставимость.×

Пусть , .LL=kLL(k)LR=kLR(k)

Уровень грамматики

Для LL

  • LL(0)LL(1)LL(2)LL(2)LL(k)LLLL()
  • SLL(1)=LL(1),SLL(k)LL(k),SLL(k+1)×LL(k)

Большинство из них доказано Розенкранцем и Стернсом в « Свойствах детерминированных нисходящих грамматик ». - довольно тривиальное упражнение. Эта презентация Теренса Парра помещает на слайд 13. В статье LL-регулярные грамматики Джарзабека и Кравчика показано , и их доказательство тривиально продолжается доSLL(k+1)×LL(k)LL()LLLLRLLLL()

Для LR

  • LR(0)SLR(1)LALR(1)LR(1)
  • SLR(k)LALR(k)LR(k)
  • SLR(1)SLR(2)SLR(k)
  • LALR(1)LALR(2)LALR(k)
  • LR(0)LR(1)LR(2)LR(k)LR

Это все простые упражнения.

LL против LR

  • LL(k)LR(k) ( Свойства детерминированных грамматик сверху вниз плюс любая левая рекурсивная грамматика)
  • LL(k)×SLR(k),LALR(k),LR(k1) (простое упражнение)
  • LLLR (любая левая рекурсивная грамматика)
  • LL()×LR (левая рекурсия по сравнению с произвольным прогнозом)

Уровень языка

Для LL

  • LL(0)LL(1)LL(2)LL(k)LLLL()
  • SLL(k)=LL(k)

Большинство из них доказано в свойствах детерминированных грамматик сверху вниз . Проблема эквивалентности для LL- и LR-регулярных грамматик Нейхолта ссылается на статьи, показывающие . В работе LL-регулярные грамматики Ярзабека и Кравчика показано , и их доказательство тривиально распространяется наLL(k)LL()LLLLRLLLL()

Для LR

  • LR(0)SLR(1)=LALR(1)=LR(1)=SLR(k)=LALR(k)=LR(k)=LR

Некоторые из них были доказаны Кнутом в его работе « О переводе языков слева направо», в которой он представил LR (k), остальные доказаны в « Преобразовании грамматик LR (k) в LR (1), SLR (1)». и (1,1) Грамматики ограниченного правого контекста Mickunas et al.

LL против LR

  • LLLR(1) (сдерживание следует из вышеизложенного, - канонический пример строгого сдерживания){aibj|ij}
  • LL()×LR (язык показывает половину утверждения, а введение проблемы эквивалентности для LL- и LR-регулярных грамматик по Найхолту дает ссылки на статьи показывая другую половину){aibj|ij}
  • LR(1)=DCFL (см., Например, ссылку здесь ).
Алекс тен Бринк
источник
Отличный ответ, хотя, я уже проголосовал. Я бы подумал, что Фрэнк деРемер доказал LALR <= LR в своей оригинальной статье LALR? (1969?)
user207421
@EJP: является немедленным, если вы определяете путем свертывания состояний . Деремер только доказал, что его конструкция создала тот же парсер. Классы грамматики не равны, что является хорошим упражнением (или даже хорошим вопросом для этого сайта). Равенство языковых классов намного сложнее: прочитайте статью, если вам действительно нужны подробности;)LALR(k)LR(k)LALRLR
Алекс тен Бринк
1
@AlextenBrink Я прочитал газету, и меня научил Фрэнк де Ремер, но это более 30 лет назад ;-) Спасибо за все детали.
user207421
Было бы неплохо собрать примеры грамматик для каждого неравенства.
o11c
1
@ o11c Думаю, это обременительно для одного ответа. У меня сложилось впечатление, что Алекс дал хорошие ссылки, где это необходимо; он заявляет "легкое упражнение" для некоторых. Я думаю, что если читатель не может придумать грамматику, он может опубликовать новый вопрос с просьбой об этом конкретном случае.
Рафаэль