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

Нисходящий синтаксический анализ (англ. top-down parsing) — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному 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>

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

• Рекурсивный нисходящий парсер (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.

Отрывок, характеризующий Нисходящий синтаксический анализ

Последнее пребывание в Богучарове князя Андрея, с его нововведениями – больницами, школами и облегчением оброка, – не смягчило их нравов, а, напротив, усилило в них те черты характера, которые старый князь называл дикостью. Между ними всегда ходили какие нибудь неясные толки, то о перечислении их всех в казаки, то о новой вере, в которую их обратят, то о царских листах каких то, то о присяге Павлу Петровичу в 1797 году (про которую говорили, что тогда еще воля выходила, да господа отняли), то об имеющем через семь лет воцариться Петре Феодоровиче, при котором все будет вольно и так будет просто, что ничего не будет. Слухи о войне в Бонапарте и его нашествии соединились для них с такими же неясными представлениями об антихристе, конце света и чистой воле.
В окрестности Богучарова были всё большие села, казенные и оброчные помещичьи. Живущих в этой местности помещиков было очень мало; очень мало было также дворовых и грамотных, и в жизни крестьян этой местности были заметнее и сильнее, чем в других, те таинственные струи народной русской жизни, причины и значение которых бывают необъяснимы для современников. Одно из таких явлений было проявившееся лет двадцать тому назад движение между крестьянами этой местности к переселению на какие то теплые реки. Сотни крестьян, в том числе и богучаровские, стали вдруг распродавать свой скот и уезжать с семействами куда то на юго восток. Как птицы летят куда то за моря, стремились эти люди с женами и детьми туда, на юго восток, где никто из них не был. Они поднимались караванами, поодиночке выкупались, бежали, и ехали, и шли туда, на теплые реки. Многие были наказаны, сосланы в Сибирь, многие с холода и голода умерли по дороге, многие вернулись сами, и движение затихло само собой так же, как оно и началось без очевидной причины. Но подводные струи не переставали течь в этом народе и собирались для какой то новой силы, имеющей проявиться так же странно, неожиданно и вместе с тем просто, естественно и сильно. Теперь, в 1812 м году, для человека, близко жившего с народом, заметно было, что эти подводные струи производили сильную работу и были близки к проявлению.
Алпатыч, приехав в Богучарово несколько времени перед кончиной старого князя, заметил, что между народом происходило волнение и что, противно тому, что происходило в полосе Лысых Гор на шестидесятиверстном радиусе, где все крестьяне уходили (предоставляя казакам разорять свои деревни), в полосе степной, в богучаровской, крестьяне, как слышно было, имели сношения с французами, получали какие то бумаги, ходившие между ними, и оставались на местах. Он знал через преданных ему дворовых людей, что ездивший на днях с казенной подводой мужик Карп, имевший большое влияние на мир, возвратился с известием, что казаки разоряют деревни, из которых выходят жители, но что французы их не трогают. Он знал, что другой мужик вчера привез даже из села Вислоухова – где стояли французы – бумагу от генерала французского, в которой жителям объявлялось, что им не будет сделано никакого вреда и за все, что у них возьмут, заплатят, если они останутся. В доказательство того мужик привез из Вислоухова сто рублей ассигнациями (он не знал, что они были фальшивые), выданные ему вперед за сено.