Люди часто говорят, что парсеры LR (k) более мощные, чем парсеры LL (k) . Эти заявления в большинстве случаев расплывчаты; в частности, следует ли сравнивать классы для фиксированного или объединения по всем ? Так как на самом деле ситуация? В частности, меня интересует, как вписывается LL (*).
Насколько я знаю, соответствующие наборы грамматик, принимаемые синтаксическими анализаторами LL и LR, являются ортогональными, поэтому давайте поговорим о языках, генерируемых соответствующими наборами грамматик. Пусть обозначает класс языков, порожденных грамматиками, которые могут быть проанализированы синтаксическим анализатором и аналогичным для других классов.
Я заинтересован в следующих отношениях:
Некоторые из них, вероятно, легко; Моя цель - собрать «полное» сравнение. Рекомендации приветствуются.
Ответы:
Существует множество известных условий содержания. Пусть обозначает сдерживание, а собственно сдерживание. Пусть обозначает несопоставимость.⊆ ⊂ ×
Пусть , .LL=⋃kLL(k) LR=⋃kLR(k)
Уровень грамматики
Для LL
Большинство из них доказано Розенкранцем и Стернсом в « Свойствах детерминированных нисходящих грамматик ». - довольно тривиальное упражнение. Эта презентация Теренса Парра помещает на слайд 13. В статье LL-регулярные грамматики Джарзабека и Кравчика показано , и их доказательство тривиально продолжается доSLL(k+1)×LL(k) LL(∗) LL⊂LLR LL⊂LL(∗)
Для LR
Это все простые упражнения.
LL против LR
Уровень языка
Для LL
Большинство из них доказано в свойствах детерминированных грамматик сверху вниз . Проблема эквивалентности для LL- и LR-регулярных грамматик Нейхолта ссылается на статьи, показывающие . В работе LL-регулярные грамматики Ярзабека и Кравчика показано , и их доказательство тривиально распространяется наLL(k)⊂LL(∗) LL⊂LLR LL⊂LL(∗)
Для LR
Некоторые из них были доказаны Кнутом в его работе « О переводе языков слева направо», в которой он представил LR (k), остальные доказаны в « Преобразовании грамматик LR (k) в LR (1), SLR (1)». и (1,1) Грамматики ограниченного правого контекста Mickunas et al.
LL против LR
источник