03.com.ua- свободная медицинская энциклопедия. Каждый зарегистрированый участник может редактировать статьи
Метод рекурсивного спуска
Метод рекурсивного спуска - это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно-свободной грамматикой
Идея метода
Для каждого нетерминального символа K строится функция, которая для любого входного слова x делает 2 вещи:
- Находит наибольшее начало z слова x, способное быть началом выводимого из K слова
- Определяет, является ли начало z выводимым из K
Такая функция должна удовлетворять следующим критериям:
- считывать из еще необработанного входного потока максимальное начало A, являющегося началом некоторого слова, выводимого из K
- определять является ли A выводимым из K или просто невыводимым началом выводимого из K слова
В случае, если такое начало считать не удается (и корректность функции для нетерминала K доказана), то входные данные не соответствуют языку, и следует остановить разбор.
Разбор заключается в вызове описанных выше функций. Если для считанного нетерминала есть составное правило, то при его разборе будут вызваны другие функции для разбора входящих в него терминалов. Дерево вызовов, начиная с самой “верхней” функции эквивалентно дереву разбора.
Наиболее простой и “человечный” вариант создания анализатора, использующего метод рекурсивного спуска, – это непосредственное программирование по каждому правилу вывода для нетерминалов грамматики.
Условия применения
Пусть в данной формальной грамматике N - это конечное множество нетерминальных символов; Σ - конечное множество терминальных символов, тогда метод рекурсивного спуска применим только, если каждое правило этой грамматики имеет следующий вид:
- или <math>A \rightarrow \alpha</math>, где <math>\alpha \subset (\Sigma \cup N)*</math>, и это единственное правило вывода для этого нетерминала
- или <math>A \rightarrow a_1\alpha_1|a_2\alpha_2|...|a_n\alpha_n</math> для всех <math>i=1,2...n; a_i \ne a_j, i \ne j; \alpha \subset (\Sigma \cup N)*</math>
Список литературы
- А. Шень. Программирование: теоремы и задачи. 2-е изд., М.: МЦНМО, 2004