Левая рекурсия

Эта статья может быть слишком технической для понимания большинством читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технических деталей. ( Ноябрь 2015 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

Определение [ править ]

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

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

,

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

Прямая левая рекурсия [ править ]

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

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

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

{\ displaystyle {\ mathit {Expression}} \ to {\ mathit {Expression}} + {\ mathit {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}}$

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}

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

Удаление левой рекурсии [ править ]

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

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

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

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

где:

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

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

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

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

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

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

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

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

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

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

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

Удаление всей левой рекурсии [ править ]

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

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

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

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

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

Ловушки [ править ]

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

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

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

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

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

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

{\mathit {Expression}}\rightarrow {\mathit {Term}}\ {\mathit {Expression}}'

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

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

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

{\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 году Фрост и Хафиз описали алгоритм, который учитывает неоднозначные грамматики с прямыми леворекурсивными производственными правилами . ^[3]Этот алгоритм был расширен до полного алгоритма синтаксического анализа для размещения косвенной, а также прямой левой рекурсии за полиномиальное время и для генерации компактных представлений полиномиального размера потенциально экспоненциального числа деревьев синтаксического анализа для весьма неоднозначных грамматик Фростом, Хафизом и Каллаганом в 2007 году. . ^[4] Затем авторы реализовали алгоритм в виде набора комбинаторов синтаксического анализатора, написанных на языке программирования Haskell . ^[5]

См. Также [ править ]

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

Ссылки [ править ]

^ Заметки по теории формального языка и синтаксическому анализу , Джеймс Пауэр, факультет компьютерных наук Национального университета Ирландии, Мейнут Мейнут, графство Килдэр, Ирландия. 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.

[1]