5.1.2. Рекурсивный спуск

­

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

Чтобы прокомментировать этот метод, запишем процедуры для нетерминальных символов следующей грамматики:

инстр  перем  вырif выр then инстр

if выр then инстр else инстр

перем  ii (выр)

выр  терм выр  терм

терм  множ терм  множ

множ  перем (выр)

Перепишем эту грамматику, используя расширенную Бэкусову нормальную форму (РБНФ) с включением факультативных (необязательных) фрагментов –  и итерации– {} (фрагмент повторяется ноль или более раз).

инстр  перем  выр if выр then инстр [ else инстр ]

перем  i [ (выр) ]

выр  терм {  терм }

терм  множ {  множ }

множ  перем (выр)

Запишем процедуры на языке, подобном Паскалю с соблюдением следующих условий:

(1) Глобальная переменная NxtSymb всегда содержит следующий символ, а точнее очередную лексему исходной программы, подлежащую обработке. При вызове процедуры для поиска новой цели первый символ, который процедура должна исследовать уже находится в NxtSymb. Для того чтобы обеспечить такую работу, перед тем как выйти из процедуры с сообщением об успехе, символ, следующий за уже рассмотренной подцепочкой, помещается в NxtSymb.

(2) Процедура Scan готовит очередной символ (лексему) входной цепочки и помещает его в NxtSymb.

(3) Программа Error вызывается при обнаружении ошибки. Она выводит сообщение об ошибке и для идентификации ошибки ей можно передать код ошибки в качестве параметра. Эта процедура может завершать разбор или пытаться нейтрализовать ошибку.

(4) Для того чтобы начать синтаксический анализ исходной строки, в головной программе сначала вызывается программа Scan, которая поместит первый символ в NxtSymb, а затем вызывается процедура State, анализирующая инструкцию.

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

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