Рекурсивный нисходящий парсер

Рекурсивный нисходящий парсер

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

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

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

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

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

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

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

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

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "Рекурсивный нисходящий парсер" в других словарях:

  • Нисходящий парсер — Метод рекурсивного спуска или нисходящий разбор  это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно свободной грамматикой. Это класс алгоритмов грамматического анализа, где… …   Википедия

  • Нисходящий синтаксический анализ — (англ. top down parsing)  это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно свободной грамматикой. Это класс алгоритмов грамматического анализа, где правила… …   Википедия

  • Рекурсивный спуск — Метод рекурсивного спуска или нисходящий разбор  это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно свободной грамматикой. Это класс алгоритмов грамматического анализа, где… …   Википедия

  • Нисходящий разбор — Метод рекурсивного спуска или нисходящий разбор  это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно свободной грамматикой. Это класс алгоритмов грамматического анализа, где… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»