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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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


de:Rekursiver Abstieg

en:Recursive descent parser ja:再帰下降構文解析 ko:되부름 하향 구문 분석 pt:Analisador sintático descendente recursivo sr:Analizator rekurzivnim spustom uk:Рекурсивний спуск

Личные инструменты

Served in 0.058 secs.