какой тип рекурсии мы должны использовать? (Обсуждение)

Question

я изучал тему "рекурсия влево и вправо в компиляторе", где я запутался в утверждении

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

но разве не так

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

M застрял там, дайте мне понять, что был бы благодарен

Answer 1

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

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

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

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