Введение
В формальной теории языков в информатике, левая рекурсия — это особый случай рекурсии, при котором строка распознается как часть языка благодаря тому, что она раскладывается на строку из того же языка (слева) и суффикс (справа). Например, выражение может быть распознано как сумма, поскольку его можно разложить на выражение, также являющееся суммой, и суффикс, являющийся подходящим дополнением. В терминах контекстно-свободной грамматики, нетерминал является леворекурсивным, если самый левый символ в одном из его правил вывода является самим собой (в случае прямой левой рекурсии) или может быть сведен к самому себе некоторой последовательностью подстановок (в случае косвенной левой рекурсии).
Косвенная левая рекурсия
Косвенная левая рекурсия возникает, когда определение левой рекурсии выполняется через несколько подстановок. Она включает в себя набор правил, соответствующих следующей схеме:
где α и β – последовательности, каждая из которых может порождать пустую строку, а γ может быть любой последовательностью терминальных и нетерминальных символов. Обратите внимание, что эти последовательности могут быть пустыми. Тогда вывод
приводит к тому, что в его конечной цепочке символов находится в крайней левой позиции.
Применение
Левая рекурсия обычно используется как идиома для обеспечения левой ассоциативности операций: выражение a+b c d+e вычисляется как (((a+b) c) d)+e. В этом случае такой порядок вычислений можно обеспечить синтаксически с помощью трех грамматических правил.
Эти правила позволяют разбирать выражение a+b c d+e только как состоящее из a+b c d и e, где a+b c d, в свою очередь, состоит из a+b c и d, а a+b c состоит из a+b и c, и так далее.
Удаление левой рекурсии
Левая рекурсия часто представляет собой проблему для парсеров, поскольку либо приводит их к бесконечной рекурсии (как в случае большинства нисходящих парсеров), либо потому, что они требуют правил в нормальной форме, которая её запрещает (как в случае многих восходящих парсеров). Поэтому грамматика часто предварительно обрабатывается для устранения левой рекурсии.
Уместительность левой рекурсии в анализе сверху вниз
Формальная грамматика, содержащая левую рекурсию, не может быть разобрана LL(k)-парсерoм или другим наивным рекурсивным нисходящим парсером, если она не преобразована в слабо эквивалентную форму с правой рекурсией. В отличие от этого, левая рекурсия предпочтительна для LALR-парсеров, поскольку она приводит к меньшему использованию стека, чем правая рекурсия. Однако более сложные нисходящие парсеры могут реализовать общие контекстно-свободные грамматики с использованием отсечения. В 2006 году Фрост и Хафиз описали алгоритм, который обрабатывает неоднозначные грамматики с непосредственной левой рекурсией. В 2007 году Фрост, Хафиз и Каллаган расширили этот алгоритм до полноценного алгоритма разбора, способного обрабатывать как непосредственную, так и косвенную левую рекурсию за полиномиальное время, а также генерировать компактные полиномиальные представления потенциально экспоненциального числа синтаксических деревьев для сильно неоднозначных грамматик. Авторы затем реализовали этот алгоритм в виде набора комбинаторов парсера, написанных на языке программирования Haskell.