Нисходящий синтаксический анализ

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

Идея методаПравить

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

• Находит наибольшее начало z слова x, способное быть началом выводимого из K слова
• Определяет, является ли начало z выводимым из K

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

• считывать из еще необработанного входного потока максимальное начало A, являющегося началом некоторого слова, выводимого из K
• определять является ли A выводимым из K или просто невыводимым началом выводимого из K слова

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

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

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

Условия примененияПравить

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

• или $A\to <!--\; \to \; -->\mathrm{\alpha <!--\; \alpha \; -->}$$A\rightarrow \alpha$ , где $\mathrm{\alpha <!--\; \alpha \; -->}\subset <!--\; \subset \; -->(\mathrm{\Sigma <!--\; \Sigma \; -->}\cup <!--\; \cup \; -->N)\ast <!--\; \ast \; -->$$\alpha \subset (\Sigma \cup N)*$ , и это единственное правило вывода для этого нетерминала
• или $A\to <!--\; \to \; -->a_1{\mathrm{\alpha <!--\; \alpha \; -->}}_1|a_2{\mathrm{\alpha <!--\; \alpha \; -->}}_2|...|a_n{\mathrm{\alpha <!--\; \alpha \; -->}}_n$$A\rightarrow a_{1}\alpha _{1}|a_{2}\alpha _{2}|...|a_{n}\alpha _{n}$  для всех $i=1,\mathrm{2...}n;a_i\ne <!--\; \ne \; -->a_j,i\ne <!--\; \ne \; -->j;\mathrm{\alpha <!--\; \alpha \; -->}\subset <!--\; \subset \; -->(\mathrm{\Sigma <!--\; \Sigma \; -->}\cup <!--\; \cup \; -->N)\ast <!--\; \ast \; -->$$i=1,2...n;a_{i}\neq a_{j},i\neq j;\alpha \subset (\Sigma \cup N)*$ 

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

• Рекурсивный нисходящий парсер (en:Recursive descent parser)
• LL-парсер (en:LL parser)
• Парсер старьёвщика (en:Packrat parser)

ЛитератураПравить

• А. Шень. Программирование: теоремы и задачи. 2-е изд., М.: МЦНМО, 2004
• Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4.
• Робин Хантер. Основные концепции компиляторов = The Essence of Compilers. — М.: «Вильямс», 2002. — С. 256. — ISBN 5-8459-0360-2.