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

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

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

Определение

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

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

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

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

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

${\displaystyle A\to A\alpha }$

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

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

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

void Выражение () { Выражение (); совпадение ( '+' ); Термин (); }     

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

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

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

${\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}}$

Использует

Левая рекурсия обычно используется как идиома для создания левоассоциативных операций : выражение a+b-c-d+eоценивается как (((a+b)-c)-d)+e. В этом случае этот порядок оценки может быть достигнут как вопрос синтаксиса с помощью трех грамматических правил

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

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

${\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}-{\mathit {Term}}}$

Они позволяют анализировать только тот вариант, который состоит из и , где в свою очередь состоит из и , в то время как состоит из и и т. д. ${\displaystyle {\mathit {Expression}}}$ a+b-c-d+e ${\displaystyle {\mathit {Expression}}}$ a+b-c-d ${\displaystyle {\mathit {Term}}}$ ea+b-c-d ${\displaystyle {\mathit {Expression}}}$ a+b-c ${\displaystyle {\mathit {Term}}}$ da+b-c ${\displaystyle {\mathit {Expression}}}$ a+b ${\displaystyle {\mathit {Term}}}$ c

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

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

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

Ниже приведен общий алгоритм удаления прямой левой рекурсии. Было сделано несколько улучшений этого метода. ^[2] Для леворекурсивного нетерминала отбросьте все правила формы и рассмотрите те, которые остались: ${\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}}$

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

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

Шаг 1.1.1 сводится к расширению начального нетерминала в правой части некоторого правила , но только если . Если был одним шагом в цикле производств, приводящих к левой рекурсии, то это сократило этот цикл на один шаг, но часто ценой увеличения количества правил. ${\displaystyle A_{j}}$ ${\displaystyle A_{i}\to A_{j}\beta }$ ${\displaystyle j<i}$ ${\displaystyle A_{i}\to A_{j}\beta }$

Алгоритм можно рассматривать как установление топологического порядка на нетерминалах: после этого может быть только правило , если . Обратите внимание, что этот алгоритм очень чувствителен к нетерминальному порядку; оптимизации часто фокусируются на выборе этого порядка. ^{[ необходимо разъяснение ]} ${\displaystyle A_{i}\to A_{j}\beta }$ ${\displaystyle j>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 {Expression}}\rightarrow {\mathit {Term}}\ {\mathit {Expression}}'}$

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

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

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

Ссылки

1. Заметки о формальной теории языка и синтаксическом анализе на Wayback Machine (архив 2007-11-27). Джеймс Пауэр, кафедра компьютерных наук Национального университета Ирландии, Мейнут Мейнут, графство Килдэр, Ирландия.JPR02
2. Мур, Роберт С. (май 2000 г.). «Удаление левой рекурсии из контекстно-свободных грамматик» (PDF) . 6-я конференция по прикладной обработке естественного языка : 249–255.
3. Frost, R.; R. Hafiz (2006). «Новый алгоритм анализа сверху вниз для учета неоднозначности и левой рекурсии за полиномиальное время». ACM SIGPLAN Notices . 41 (5): 46–54. doi :10.1145/1149982.1149988. S2CID  8006549., доступно у автора по адресу http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf Архивировано 08.01.2015 на Wayback Machine
4. Frost, R.; R. Hafiz; P. Callaghan (июнь 2007 г.). «Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars» (PDF) . 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE : 109–120. Архивировано из оригинала (PDF) 2011-05-27.
5. Frost, R.; R. Hafiz; P. Callaghan (январь 2008). "Parser Combinators for Ambiguous Left-Recursive Grammars". Практические аспекты декларативных языков (PDF) . Конспект лекций по информатике. Том 4902. С. 167–181. doi :10.1007/978-3-540-77442-6_12. ISBN 978-3-540-77441-9.

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

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