Левые рекурсивные правила в контекстно-свободной грамматике

Question

Итак, все, что я читал, говорит о том, что левые рекурсивные правила в CFG проходят бесконечно и продолжают показывать процесс преобразования его в правое рекурсивное правило и выполняют это, используя альфа- и бета-термины для представления нескольких нетерминалов (я думаю, Я правильно понял эту часть) Поэтому, на мой взгляд, оставил рекурсивные правила = плохо при работе с LL-парсерами.

Так есть ли ситуация, когда оставленные рекурсивные правила являются приемлемыми / желательными? Если нет, то почему существуют левые рекурсивные правила, помимо плохого замысла или термина, описывающего «обратный» (термин, используемый слегка) правых рекурсивных правил?

Технически, это не вопрос домашнего задания, но это связано с моим классом.

Answer 1

Ключ к вашему вопросу в том, что левые рекурсивные правила плохи только при работе с LL-парсерами.Если вы используете парсер LR, я часто чувствую, что грамматика становится намного понятнее.Возьмем, к примеру, стандартную грамматику выражения

E : E + T | T
T : T * F | F
F : number | ( E )

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

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