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

­

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

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

Поиск по сайту: