Нисходящий метод(метод рекурсивного спуска)

Другой метод грамматического разбора - нисходящий метод, называемый рекурсивным спуском. Процессор грамматического разбора, основанный на этом методе, состоит из отдельных процедур для каждого нетерминального символа, определенного в грамматике. Каждая такая процедура старается во входном потоке найти подстроку, начинающуюся с текущей лексемы, которая может быть интерпретирована как нетерминальный символ, связанный с данной процедурой. В процессе своей работы она может вызывать другие подобные процедуры или даже рекурсивно саму себя для поиска других нетерминальных символов. Если эта процедура находит соответствующий нетерминальный символ, то она заканчивает свою работу, передает в вызвавшую ее программу признак успешного завершения и устанавливает указатель текущей лексемы на первую лексему после распознанной подстроки. Если же процедура не может найти подстроку, которая могла бы быть интерпретирована как требуемый нетерминальный символ, она заканчивается с признаком ошибки или вызывает процедуру выдачи диагностического сообщения и процедуру восстановления.

Рассмотрим в качестве примера правило <read> ::= READ ( <id-list> ), записанное в форме Бекуса-Наура (БНФ). Грамматика БНФ состоит из подмножества правил вывода, каждое из которых определяет синтаксис некоторой конструкции языка программирования. Это определение синтаксиса предложения READ языка Паскаль, обозначенное в грамматике как <read>. Символ “::=” можно читать как “является по определению”. Строки символов, заключенные в угловые скобки “<” и ”>”, называются нетерминальными символами, т.е. являются именами конструкций, определенными внутри грамматики. То, что не заключено в угловые скобки, называется терминальными символами грамматики - лексемами. Таким образом, это правило определяет, что конструкция <read> состоит из лексемы READ, за которой следует лексема “(“, за ней следует конструкция языка, называемая <id-list>, за которой следует лексема “)”. Для распознавания нетерминального символа <read> необходимо, чтобы было определение для нетерминального символа <id-list>.

<id-list> ::= id | <id-list>,id

Это правило является рекурсивным, т.е. конструкция <id-list> определяется фактически в терминах себя самой.

Процедура метода рекурсивного спуска, соответствующая нетерминальному символу <read>, прежде всего исследует две последовательные лексемы, сравнивая их с READ и “(“. В случае совпадения эта процедура вызывает другую процедуру, соответствующую нетерминальному символу <id-list>. Если процедура <id-list > завершится успешно, то процедура <read> сравнивает следующую лексему с “)”. Если все эти проверки окажутся успешными, то процедура <read> завершается с признаком успеха и устанавливает указатель текущей лексемы на лексему, следующую за “)”. В противном случае процедура <read> завершится с признаком неудачи. Поэтапный процесс разбора представлен на рисунке 2.

Нисходящий грамматический разбор неприменим непосредственно для грамматик, содержащих левые рекурсии, т.к. один рекурсивный вызов приведет к еще одному рекурсивному вызову и т.д., в результате чего образуется бесконечная цепочка рекурсивных вызовов. Исключая левую рекурсию, получаем правило:

<id-list> ::= id { , id },

которое определяет нетерминальный символ <id-list> как состоящий из единственной лексемы id или же из произвольного числа следующих друг за другом лексем id, разделенных запятыми.

Выводы

В языке программирования отсутствуют какие-либо особенности, заставляющие отдать предпочтение одному из методов грамматического разбора. Возможно одновременное использование обоих методов. Некоторые компиляторы используют метод рекурсивного спуска для распознавания конструкций относительно высокого уровня, например, до уровня отдельных предложений языка, а потом переключаются на метод, аналогичный методу предшествующего спуска для анализа таких конструкций, как, например, арифметические выражения.