Рекурсивный нисходящий парсер
Рекурсивный нисходящий парсер (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:Рекурсивний спуск
Если вам нравится SbUP.com Сайт, вы можете поддержать его - BTC: bc1qppjcl3c2cyjazy6lepmrv3fh6ke9mxs7zpfky0 , TRC20 и ещё....