Метод рекурсивного спуска (англ. Recursive descent parser) — алгоритм нисходящего синтаксического анализа, реализуемый путём взаимного вызова процедур, где каждая процедура соответствует одному из правил контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов синтаксического анализа, подходящий для полностью ручной реализации.
Энциклопедичный YouTube
-
1/3Просмотров:6 2088 604933
-
Парсеры (метод рекурсивного спуска)
-
Java. Вычисление арифметического выражения из строки методом рекурсивного спуска.
-
Методы трансляции 3 курс - теорема о LL(1) грамматиках, рекурсивный спуск, устранение левой рекурсии
Субтитры
Варианты реализации
Предсказывающий парсер
Для парсеров этого типа нужна подходящая КС-грамматика, конкретно — LL(k) грамматика, позволяющая по очередному токену или токенам однозначно выбрать (предсказать) один из альтернативных вариантов раскрытия каждого нетерминала.
Такой парсер работает за линейное время.
Вариантом является LL-парсер — реализация предсказывающего парсера с автоматическим построением «таблицы предсказания», определяющей по заданному нетерминалу и очередному токену подходящее правило для раскрытия нетерминала.
Парсер с возвратом
Вместо предсказания парсер просто пытается применить все альтернативные варианты правил по порядку, пока одна из попыток не увенчается успехом.
Такой парсер может потребовать экспоненциального времени работы, и не всегда гарантирует завершение, в зависимости от грамматики. Уязвим для левой рекурсии.
| Общие понятия | |
|---|---|
| Тип 0 | |
| Тип 1 |
|
| Тип 2 | |
| Тип 3 | |
| Синтаксический анализ | |
Эта страница в последний раз была отредактирована 3 февраля 2023 в 02:05.
Обычно почти сразу, изредка в течении часа.