Нисходящий парсер | это... Что такое Нисходящий парсер? (original) (raw)

Нисходящий парсер

Нисходящий парсер

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

Содержание

Идея метода

Для каждого нетерминального символа K строится функция, которая для любого входного слова x делает 2 вещи:

Такая функция должна удовлетворять следующим критериям:

В случае, если такое начало считать не удается (и корректность функции для нетерминала K доказана), то входные данные не соответствуют языку, и следует остановить разбор.

Разбор заключается в вызове описанных выше функций. Если для считанного нетерминала есть составное правило, то при его разборе будут вызваны другие функции для разбора входящих в него терминалов. Дерево вызовов, начиная с самой «верхней» функции эквивалентно дереву разбора.

Наиболее простой и «человечный» вариант создания анализатора, использующего метод рекурсивного спуска, — это непосредственное программирование по каждому правилу вывода для нетерминалов грамматики.

Условия применения

Пусть в данной формальной грамматике N — это конечное множество нетерминальных символов; Σ — конечное множество терминальных символов, тогда метод рекурсивного спуска применим только, если каждое правило этой грамматики имеет следующий вид:

Алгоритмы нисходящего разбора

Литература

Wikimedia Foundation.2010.

Полезное

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