Метод рекурсивного спуска ( англ. Recursive descent parser) — алгоритм нисходящего синтаксического анализа , реализуемый путём взаимного вызова процедур, где каждая процедура соответствует одному из правил контекстно-свободной грамматики или БНФ . Применения правил последовательно, слева направо поглощают токены , полученные от лексического анализатора . Это один из самых простых алгоритмов синтаксического анализа, подходящий для полностью ручной реализации.

Варианты реализации

Предсказывающий парсер

Для парсеров этого типа нужна подходящая КС-грамматика , конкретно — LL(k) грамматика, позволяющая по очередному токену или токенам однозначно выбрать (предсказать) один из альтернативных вариантов раскрытия каждого нетерминала.

Такой парсер работает за линейное время.

Вариантом является LL-парсер — реализация предсказывающего парсера с автоматическим построением «таблицы предсказания», определяющей по заданному нетерминалу и очередному токену подходящее правило для раскрытия нетерминала.

Парсер с возвратом

Вместо предсказания парсер просто пытается применить все альтернативные варианты правил по порядку, пока одна из попыток не увенчается успехом.

Такой парсер может потребовать экспоненциального времени работы, и не всегда гарантирует завершение, в зависимости от грамматики. Уязвим для .