С точки зрения непрофессионала, что осталось от рекурсии?

12

Согласно одной странице на code.google.com, «левая рекурсия» определяется следующим образом:

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

Википедия предлагает два разных определения:

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

  2. «Грамматика является леворекурсивной, если мы можем найти некоторую нетерминальную букву А, которая в конечном итоге получит форму предложения с самим собой в качестве левого символа».

Я только начинаю с создания языка здесь, и я делаю это в свое свободное время. Однако, когда дело доходит до выбора синтаксического анализатора языка, поддерживается ли левая рекурсия этим анализатором или этот анализатор является проблемой, которая сразу же выходит вперед и в центр. Поиск таких терминов, как «форма предложения», приводит только к дальнейшим спискам жаргона, но различие «левой» рекурсии почти должно быть чем-то очень простым. Перевод пожалуйста?

Panzercrisis
источник

Ответы:

21

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

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

Expression ::= Multiplication '+' Expression
            || Multiplication

Multiplication ::= Term '*' Term
                 || Term

Term ::= Number | Variable

Как написано, здесь нет левой рекурсии - мы могли бы передать эту грамматику синтаксическому анализатору с рекурсивным спуском.

Но предположим, что вы пытались написать это так:

Expression ::= Expression '*' Expression
            || Expression '+' Expression
            || Term

Term ::= Number | Variable

Это грамматика, и некоторые парсеры могут справиться с ней, но парсеры рекурсивного спуска и парсеры LL не могут - потому что правило для Expressionначинается с Expressionсамого себя. Должно быть очевидно, почему в синтаксическом анализаторе с рекурсивным спуском это приводит к неограниченной рекурсии без фактического использования какого-либо ввода.

Неважно, относится ли правило к себе прямо или косвенно; Если Aимеет альтернативу, которая начинается с B, и Bимеет альтернативу, которая начинается с A, то Aи Bкосвенно леворекурсивны, и в синтаксическом анализаторе с рекурсивным спуском их функции соответствия привели бы к бесконечной взаимной рекурсии.

Hobbs
источник
Итак, во втором примере, если вы изменили самую первую вещь после ::=с Expressionна Term, и если бы вы сделали то же самое после первой ||, это больше не было бы леворекурсивным? Но что, если бы вы только сделали это после ::=, но не так ||, это все равно было бы леворекурсивным?
Panzercrisis
Похоже, вы говорите, что многие парсеры идут слева направо, останавливаясь на каждом символе и рекурсивно оценивая его на месте. В этом случае, если с первым Expressionпереключиться Termкак после, так ::=и после первого ||, все будет хорошо; потому что рано или поздно он столкнется с чем-то, что не является ни, Numberни чем Variable, и таким образом сможет определить, что что-то не Expressionбез дальнейшей казни ...
Panzercrisis
... Но если бы кто-то из них все еще начинал Expression, он потенциально мог бы найти что-то, чего не было Term, и просто продолжал бы проверять, все ли Expressionснова и снова. Это оно?
Panzercrisis
1
@Panzercrisis более или менее. Вам действительно нужно поискать значения паролей LL, LR и рекурсивного спуска.
Хоббс
Это технически точно, но, возможно, недостаточно просто (по словам непрофессионала). Я также хотел бы добавить, что на практике парсеры LL, как правило, будут иметь возможность обнаруживать рекурсию и избегать ее (потенциально отвергая придуманные строки, которые допустимы в процессе), а также тот факт, что на практике большинство языков программирования имеют грамматику, определенную в таким образом, чтобы избежать бесконечной рекурсии.
4

Я попытаюсь выразить это в терминах непрофессионала.

Если вы думаете с точки зрения дерева разбора (не AST, а посещения синтаксического анализатора и расширения входных данных), левая рекурсия приводит к дереву, которое растет влево и вниз. Правильная рекурсия с точностью до наоборот.

Например, общая грамматика в компиляторе - это список элементов. Давайте возьмем список строк («красный», «зеленый», «синий») и проанализируем его. Я мог бы написать грамматику несколькими способами. Следующие примеры являются рекурсивными непосредственно влево или вправо, соответственно:

arg_list:                           arg_list:
      STRING                              STRING
    | arg_list ',' STRING               | STRING ',' arg_list 

Деревья для этих разбора:

         (arg_list)                       (arg_list)
          /      \                         /      \
      (arg_list)  BLUE                  RED     (arg_list)
       /       \                                 /      \
   (arg_list) GREEN                          GREEN    (arg_list)
    /                                                  /
 RED                                                BLUE

Обратите внимание, как оно растет в направлении рекурсии.

Это на самом деле не проблема, это нормально, если вы хотите написать левую рекурсивную грамматику ... если ваш инструмент синтаксического анализа может с этим справиться. Анализаторы снизу вверх справляются с этим просто отлично. Так могут более современные парсеры LL. Проблема с рекурсивными грамматиками заключается не в рекурсии, а в рекурсии без улучшения синтаксического анализатора или в рекурсии без использования токена. Если мы всегда потребляем хотя бы 1 токен, когда выполняем рекурсию, мы в конце концов достигаем конца разбора. Левая рекурсия определяется как рекурсивная без потребления, что представляет собой бесконечный цикл.

Это ограничение является чисто реализацией реализации грамматики с наивным анализатором LL сверху вниз (анализатор рекурсивного спуска). Если вы хотите придерживаться левой рекурсивной грамматики, вы можете справиться с ней, переписав производство так, чтобы оно потребляло как минимум 1 токен перед повторением, так что это гарантирует, что мы никогда не застрянем в непроизводительном цикле. Для любого правила грамматики, которое является леворекурсивным, мы можем переписать его, добавив промежуточное правило, которое выравнивает грамматику только до одного уровня прогнозирования, потребляя токен между рекурсивными производствами. (ПРИМЕЧАНИЕ. Я не говорю, что это единственный или предпочтительный способ переписать грамматику, я просто указываю на обобщенное правило. В этом простом примере лучшим вариантом является использование праворекурсивной формы). Поскольку этот подход является обобщенным, Генератор парсера может реализовать это без участия программиста (теоретически). На практике, я считаю, что ANTLR 4 теперь делает именно это.

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

bool match_list()
{
    if(lookahead-predicts-something-besides-comma) {
       match_STRING();
    } else if(lookahead-is-comma) {
       match_list();   // left-recursion, infinite loop/stack overflow
       match(',');
       match_STRING();
    } else {
       throw new ParseException();
    }
}

На самом деле мы имеем дело с «наивным исполнением», т.е. мы изначально сделали предикат для данного предложения, затем рекурсивно вызвали функцию для этого прогноза, и эта функция наивно вызывает тот же прогноз снова.

Анализаторы снизу вверх не имеют проблемы рекурсивных правил в обоих направлениях, потому что они не разбирают начало предложения, они работают, собирая предложение вместе.

Рекурсия в грамматике является проблемой, только если мы производим сверху вниз, т.е. наш парсер работает, "расширяя" наши прогнозы, когда мы потребляем токены. Если вместо расширения мы свернемся (производство «сокращено»), как в анализаторе снизу вверх LALR (Yacc / Bison), то рекурсия любой из сторон не является проблемой.

codenheim
источник