Согласно одной странице на code.google.com, «левая рекурсия» определяется следующим образом:
Левая рекурсия просто относится к любому рекурсивному нетерминалу, который, когда он создает форму предложения, содержащую себя, эта новая копия сама появляется слева от производственного правила.
Википедия предлагает два разных определения:
В терминах контекстно-свободной грамматики нетерминальный r является леворекурсивным, если крайний левый символ в любом из произведений r («альтернатив») либо непосредственно (прямой / непосредственный левый рекурсив), либо через какой-либо другой нетерминальный определения (косвенные / скрытые леворекурсивные) переписываются в r снова.
«Грамматика является леворекурсивной, если мы можем найти некоторую нетерминальную букву А, которая в конечном итоге получит форму предложения с самим собой в качестве левого символа».
Я только начинаю с создания языка здесь, и я делаю это в свое свободное время. Однако, когда дело доходит до выбора синтаксического анализатора языка, поддерживается ли левая рекурсия этим анализатором или этот анализатор является проблемой, которая сразу же выходит вперед и в центр. Поиск таких терминов, как «форма предложения», приводит только к дальнейшим спискам жаргона, но различие «левой» рекурсии почти должно быть чем-то очень простым. Перевод пожалуйста?
источник
::=
сExpression
наTerm
, и если бы вы сделали то же самое после первой||
, это больше не было бы леворекурсивным? Но что, если бы вы только сделали это после::=
, но не так||
, это все равно было бы леворекурсивным?Expression
переключитьсяTerm
как после, так::=
и после первого||
, все будет хорошо; потому что рано или поздно он столкнется с чем-то, что не является ни,Number
ни чемVariable
, и таким образом сможет определить, что что-то неExpression
без дальнейшей казни ...Expression
, он потенциально мог бы найти что-то, чего не былоTerm
, и просто продолжал бы проверять, все лиExpression
снова и снова. Это оно?Я попытаюсь выразить это в терминах непрофессионала.
Если вы думаете с точки зрения дерева разбора (не AST, а посещения синтаксического анализатора и расширения входных данных), левая рекурсия приводит к дереву, которое растет влево и вниз. Правильная рекурсия с точностью до наоборот.
Например, общая грамматика в компиляторе - это список элементов. Давайте возьмем список строк («красный», «зеленый», «синий») и проанализируем его. Я мог бы написать грамматику несколькими способами. Следующие примеры являются рекурсивными непосредственно влево или вправо, соответственно:
Деревья для этих разбора:
Обратите внимание, как оно растет в направлении рекурсии.
Это на самом деле не проблема, это нормально, если вы хотите написать левую рекурсивную грамматику ... если ваш инструмент синтаксического анализа может с этим справиться. Анализаторы снизу вверх справляются с этим просто отлично. Так могут более современные парсеры LL. Проблема с рекурсивными грамматиками заключается не в рекурсии, а в рекурсии без улучшения синтаксического анализатора или в рекурсии без использования токена. Если мы всегда потребляем хотя бы 1 токен, когда выполняем рекурсию, мы в конце концов достигаем конца разбора. Левая рекурсия определяется как рекурсивная без потребления, что представляет собой бесконечный цикл.
Это ограничение является чисто реализацией реализации грамматики с наивным анализатором LL сверху вниз (анализатор рекурсивного спуска). Если вы хотите придерживаться левой рекурсивной грамматики, вы можете справиться с ней, переписав производство так, чтобы оно потребляло как минимум 1 токен перед повторением, так что это гарантирует, что мы никогда не застрянем в непроизводительном цикле. Для любого правила грамматики, которое является леворекурсивным, мы можем переписать его, добавив промежуточное правило, которое выравнивает грамматику только до одного уровня прогнозирования, потребляя токен между рекурсивными производствами. (ПРИМЕЧАНИЕ. Я не говорю, что это единственный или предпочтительный способ переписать грамматику, я просто указываю на обобщенное правило. В этом простом примере лучшим вариантом является использование праворекурсивной формы). Поскольку этот подход является обобщенным, Генератор парсера может реализовать это без участия программиста (теоретически). На практике, я считаю, что ANTLR 4 теперь делает именно это.
Для приведенной выше грамматики реализация LL, отображающая левую рекурсию, будет выглядеть следующим образом. Парсер начнёт с предсказания списка ...
На самом деле мы имеем дело с «наивным исполнением», т.е. мы изначально сделали предикат для данного предложения, затем рекурсивно вызвали функцию для этого прогноза, и эта функция наивно вызывает тот же прогноз снова.
Анализаторы снизу вверх не имеют проблемы рекурсивных правил в обоих направлениях, потому что они не разбирают начало предложения, они работают, собирая предложение вместе.
Рекурсия в грамматике является проблемой, только если мы производим сверху вниз, т.е. наш парсер работает, "расширяя" наши прогнозы, когда мы потребляем токены. Если вместо расширения мы свернемся (производство «сокращено»), как в анализаторе снизу вверх LALR (Yacc / Bison), то рекурсия любой из сторон не является проблемой.
источник