Левая рекурсия - Left recursion

В формальной теории языка в информатике , левая рекурсия является частным случаем рекурсии , где строка распознаются как часть языка, тем , что он разлагается в строку из того же языка (слева) и суффикс (на право). Например, его можно распознать как сумму, потому что его можно разбить на сумму и подходящий суффикс. ${\ displaystyle 1 + 2 + 3}$ ${\ displaystyle 1 + 2}$ ${\ displaystyle {} +3}$

С точки зрения контекстно-свободной грамматики , нетерминал является леворекурсивным, если крайний левый символ в одной из его продукций является самим собой (в случае прямой левой рекурсии) или может быть образован некоторой последовательностью замен (в случае косвенной левая рекурсия).

Определение

Грамматика является леворекурсивной тогда и только тогда, когда существует нетерминальный символ, который может образовывать сентенциальную форму с самим собой в качестве крайнего левого символа. Символично, ${\ displaystyle A}$

{\ displaystyle A \ Rightarrow ^ {+} A \ alpha}

,

где обозначает операцию выполнения одной или нескольких замен, а - любая последовательность оконечных и нетерминальных символов. ${\ displaystyle \ Rightarrow ^ {+}}$ ${\ displaystyle \ alpha}$

Прямая левая рекурсия

Прямая левая рекурсия возникает, когда определение может быть удовлетворено только одной заменой. Требуется правило формы

{\ Displaystyle от А \ до А \ альфа}

где - последовательность нетерминалов и терминалов. Например, правило ${\ displaystyle \ alpha}$

{\ displaystyle {\ mathit {Expression}} \ to {\ mathit {Expression}} + {\ mathit {Term}}}

является непосредственно леворекурсивным. Парсер рекурсивного спуска слева направо для этого правила может выглядеть так:

void Expression() {
  Expression();
  match('+');
  Term();
}

и такой код при выполнении попадет в бесконечную рекурсию.

Косвенная левая рекурсия

Косвенная левая рекурсия возникает, когда определение левой рекурсии выполняется с помощью нескольких замен. Это влечет за собой набор правил по образцу

{\ displaystyle A_ {0} \ to \ beta _ {0} A_ {1} \ alpha _ {0}}

{\ Displaystyle A_ {1} \ to \ beta _ {1} A_ {2} \ alpha _ {1}}

{\ displaystyle \ cdots}

{\ displaystyle A_ {n} \ to \ beta _ {n} A_ {0} \ alpha _ {n}}

где - последовательности, каждая из которых может давать пустую строку , а могут быть любые последовательности конечных и нетерминальных символов. Обратите внимание, что эти последовательности могут быть пустыми. Вывод ${\ displaystyle \ beta _ {0}, \ beta _ {1}, \ ldots, \ beta _ {n}}$ ${\ displaystyle \ alpha _ {0}, \ alpha _ {1}, \ ldots, \ alpha _ {n}}$

{\ displaystyle A_ {0} \ Rightarrow \ beta _ {0} A_ {1} \ alpha _ {0} \ Rightarrow ^ {+} A_ {1} \ alpha _ {0} \ Rightarrow \ beta _ {1} A_ {2} \ alpha _ {1} \ alpha _ {0} \ Rightarrow ^ {+} \ cdots \ Rightarrow ^ {+} A_ {0} \ alpha _ {n} \ dots \ alpha _ {1} \ alpha _ {0}}

затем выдает как крайний левый в своей окончательной форме предложения. ${\ displaystyle A_ {0}}$

Удаление левой рекурсии

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

Удаление прямой левой рекурсии

Общий алгоритм удаления прямой левой рекурсии следующий. В этот метод внесено несколько улучшений. Для леворекурсивного нетерминала отбросьте все правила формы и рассмотрите оставшиеся: ${\ displaystyle A}$ ${\ displaystyle A \ rightarrow A}$

{\ displaystyle A \ rightarrow A \ alpha _ {1} \ mid \ ldots \ mid A \ alpha _ {n} \ mid \ beta _ {1} \ mid \ ldots \ mid \ beta _ {m}}

где:

каждый - непустая последовательность нетерминалов и терминалов, и ${\ displaystyle \ alpha}$
каждый - это последовательность нетерминалов и терминалов, не начинающаяся с . ${\ displaystyle \ beta}$ ${\ displaystyle A}$

Замените их двумя наборами продукции, один набор для : ${\ displaystyle A}$

{\ Displaystyle A \ rightarrow \ beta _ {1} A ^ {\ prime} \ mid \ ldots \ mid \ beta _ {m} A ^ {\ prime}}

и еще один набор для свежего нетерминала (часто называемого "хвостом" или "остальным"): ${\ displaystyle A '}$

{\ displaystyle A ^ {\ prime} \ rightarrow \ alpha _ {1} A ^ {\ prime} \ mid \ ldots \ mid \ alpha _ {n} A ^ {\ prime} \ mid \ epsilon}

Повторяйте этот процесс до тех пор, пока не останется прямой левой рекурсии.

В качестве примера рассмотрим набор правил

{\ displaystyle {\ mathit {Expression}} \ rightarrow {\ mathit {Expression}} + {\ mathit {Expression}} \ mid {\ mathit {Integer}} \ mid {\ mathit {String}}}

Это можно переписать, чтобы избежать левой рекурсии, как

{\ displaystyle {\ mathit {Expression}} \ rightarrow {\ mathit {Integer}} \, {\ mathit {Expression}} '\ mid {\ mathit {String}} \, {\ mathit {Expression}}'}

{\ displaystyle {\ mathit {Expression}} '\ rightarrow {} + {\ mathit {Expression}} \, {\ mathit {Expression}}' \ mid \ epsilon}

Удаление всей левой рекурсии

Установив топологический порядок на нетерминалах, описанный выше процесс можно расширить, чтобы также исключить косвенную левую рекурсию:

Входные данные Грамматика: набор нетерминалов и их продукции ${\ Displaystyle A_ {1}, \ ldots, A_ {n}}$

Выходные данные Измененная грамматика, генерирующая тот же язык, но без левой рекурсии.

Для каждого нетерминала : ${\ displaystyle A_ {i}}$
1. Повторяйте, пока итерация не оставит грамматику неизменной:
  1. Для каждого правила , представляющего собой последовательность терминалов и нетерминалов: ${\ displaystyle A_ {i} \ rightarrow \ alpha _ {i}}$ ${\ displaystyle \ alpha _ {я}}$
    1. Если начинается с нетерминального и : ${\ displaystyle \ alpha _ {я}}$ ${\ displaystyle A_ {j}}$ ${\ displaystyle j <i}$
      1. Пусть будет без его руководства . ${\ displaystyle \ beta _ {я}}$ ${\ displaystyle \ alpha _ {я}}$ ${\ displaystyle A_ {j}}$
      2. Удалите правило . ${\ displaystyle A_ {i} \ rightarrow \ alpha _ {i}}$
      3. Для каждого правила : ${\ displaystyle A_ {j} \ rightarrow \ alpha _ {j}}$
        Добавьте правило . ${\ displaystyle A_ {i} \ rightarrow \ alpha _ {j} \ beta _ {i}}$
2. Удалите прямую левую рекурсию, как описано выше. ${\ displaystyle A_ {i}}$

Обратите внимание, что этот алгоритм очень чувствителен к нетерминальному порядку; оптимизации часто сосредотачиваются на правильном выборе этого порядка.

Ловушки

Хотя приведенные выше преобразования сохраняют язык, созданный грамматикой, они могут изменять деревья синтаксического анализа , свидетельствующие о распознавании строк. При соответствующем учете перезапись дерева может восстановить оригиналы, но если этот шаг пропустить, различия могут изменить семантику синтаксического анализа.

Ассоциативность особенно уязвима; левоассоциативные операторы обычно появляются в правой ассоциативной структуре в новой грамматике. Например, начиная с этой грамматики:

{\ displaystyle {\ mathit {Expression}} \ rightarrow {\ mathit {Expression}} \, - \, {\ mathit {Term}} \ mid {\ mathit {Term}}}

{\ displaystyle {\ mathit {Term}} \ rightarrow {\ mathit {Term}} \, * \, {\ mathit {Factor}} \ mid {\ mathit {Factor}}}

{\ displaystyle {\ mathit {Factor}} \ rightarrow ({\ mathit {Expression}}) \ mid {\ mathit {Integer}}}

стандартные преобразования для удаления левой рекурсии дают следующее:

{\ displaystyle {\ mathit {выражение}} \ rightarrow {\ mathit {термин}} \ {\ mathit {выражение}} '}

{\ displaystyle {\ mathit {Expression}} '\ rightarrow {} - {\ mathit {Term}} \ {\ mathit {Expression}}' \ mid \ epsilon}

{\ displaystyle {\ mathit {Term}} \ rightarrow {\ mathit {Factor}} \ {\ mathit {Term}} '}

{\ displaystyle {\ mathit {Term}} '\ rightarrow {} * {\ mathit {Factor}} \ {\ mathit {Term}}' \ mid \ epsilon}

{\ displaystyle {\ mathit {Factor}} \ rightarrow ({\ mathit {Expression}}) \ mid {\ mathit {Integer}}}

Анализ строки "1-2-3" с первой грамматикой в анализаторе LALR (который может обрабатывать леворекурсивные грамматики) привел бы к дереву синтаксического анализа:

Леворекурсивный разбор двойного вычитания

Это дерево синтаксического анализа группирует термины слева, давая правильную семантику (1-2) - 3 .

Парсинг со второй грамматикой дает

Праворекурсивный разбор двойного вычитания

который при правильной интерпретации означает 1 + (-2 + (-3)) , также правильный, но менее точный для ввода и намного сложнее реализовать для некоторых операторов. Обратите внимание, как термины справа появляются глубже в дереве, так же, как праворекурсивная грамматика упорядочивает их для 1 - (2 - 3) .

Учет левой рекурсии при синтаксическом анализе сверху вниз

Формальная грамматика , которая содержит левую рекурсию не может быть проанализирована с помощью LL (к) -parser или другого наивныма метода рекурсивного спуска , если он не преобразуется в слабо эквивалентную правой рекурсии формы. Напротив, левая рекурсия предпочтительнее для парсеров LALR, потому что она приводит к меньшему использованию стека, чем правая рекурсия . Однако более сложные нисходящие синтаксические анализаторы могут реализовывать общие контекстно-свободные грамматики с помощью сокращения. В 2006 году Фрост и Хафиз описали алгоритм, который учитывает неоднозначные грамматики с прямыми леворекурсивными производственными правилами . Этот алгоритм был расширен до полного алгоритма синтаксического анализа , чтобы приспособить косвенную, а также прямую левую рекурсию за полиномиальное время и сгенерировать компактные представления полиномиального размера потенциально экспоненциального числа деревьев синтаксического анализа для весьма неоднозначных грамматик Фростом, Хафизом и Каллаганом в 2007 году. Затем авторы реализовали алгоритм в виде набора комбинаторов синтаксического анализатора, написанных на языке программирования Haskell .

Смотрите также

Хвостовая рекурсия

Ссылки

^ Заметки по теории формального языка и синтаксическому анализу , Джеймс Пауэр, факультет компьютерных наук Национального университета Ирландии, Мейнут Мейнут, графство Килдэр, Ирландия. JPR02
↑ Мур, Роберт С. (май 2000 г.). «Удаление левой рекурсии из контекстно-свободных грамматик» (PDF) . 6-я конференция по прикладной обработке естественного языка : 249–255.
^ Frost, R .; Р. Хафиз (2006). «Новый алгоритм нисходящего синтаксического анализа для устранения неоднозначности и левой рекурсии за полиномиальное время» . Уведомления ACM SIGPLAN . 41 (5): 46–54. DOI : 10.1145 / 1149982.1149988 ., доступно у автора по адресу http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf. Архивировано 8 января 2015 г. на Wayback Machine.
^ Frost, R .; Р. Хафиз; П. Каллаган (июнь 2007 г.). «Модульный и эффективный анализ сверху вниз для неоднозначных леворекурсивных грамматик» (PDF) . 10-й Международный семинар по технологиям синтаксического анализа (IWPT), ACL-SIGPARSE : 109–120. Архивировано из оригинального (PDF) 27 мая 2011 года.
^ Frost, R .; Р. Хафиз; П. Каллаган (январь 2008 г.). Комбинаторы синтаксического анализатора для неоднозначных леворекурсивных грамматик (PDF) . 10-й Международный симпозиум по практическим аспектам декларативных языков (PADL), ACM-SIGPLAN . Конспект лекций по информатике. 4902 . С. 167–181. DOI : 10.1007 / 978-3-540-77442-6_12 . ISBN 978-3-540-77441-9.

внешние ссылки

Практические соображения по грамматике LALR (1)

[1] Заметки по теории формального языка и синтаксическому анализу , Джеймс Пауэр, факультет компьютерных наук Национального университета Ирландии, Мейнут Мейнут, графство Килдэр, Ирландия. JPR02

[Moore2000-2] Мур, Роберт С. (май 2000 г.). «Удаление левой рекурсии из контекстно-свободных грамматик» (PDF) . 6-я конференция по прикладной обработке естественного языка : 249–255.

[FrostHafiz2006-3] Frost, R .; Р. Хафиз (2006). «Новый алгоритм нисходящего синтаксического анализа для устранения неоднозначности и левой рекурсии за полиномиальное время» . Уведомления ACM SIGPLAN . 41 (5): 46–54. DOI : 10.1145 / 1149982.1149988 ., доступно у автора по адресу http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf. Архивировано 8 января 2015 г. на Wayback Machine.

[FrostHafizCallaghan2007-4] Frost, R .; Р. Хафиз; П. Каллаган (июнь 2007 г.). «Модульный и эффективный анализ сверху вниз для неоднозначных леворекурсивных грамматик» (PDF) . 10-й Международный семинар по технологиям синтаксического анализа (IWPT), ACL-SIGPARSE : 109–120. Архивировано из оригинального (PDF) 27 мая 2011 года.

[FrostHafizCallaghan2008-5] Frost, R .; Р. Хафиз; П. Каллаган (январь 2008 г.). Комбинаторы синтаксического анализатора для неоднозначных леворекурсивных грамматик (PDF) . 10-й Международный симпозиум по практическим аспектам декларативных языков (PADL), ACM-SIGPLAN . Конспект лекций по информатике. 4902 . С. 167–181. DOI : 10.1007 / 978-3-540-77442-6_12 . ISBN 978-3-540-77441-9.

Languages

In other projects