Основы разработки трансляторов в САПР. Коробова И.Л - 9 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

1.2.1. Метод рекурсивного спуска
Процесс грамматического разбора для этого метода состоит из отдельных процедур для каждого
нетерминального символа, определенного в грамматике. Каждая такая процедура старается во входном
потоке найти подстроку, начинающуюся с текущей лексемы, которая может быть интерпретирована как
нетерминальный символ, связанный с данной процедурой. В процессе своей работы она может вызы-
вать другие процедуры или даже рекурсивно саму себя для поиска других нетерминальных символов.
Если эта процедура находит соответствующий нетерминальный символ, то она заканчивает работу и
передает в вызывающую ее программу признак успешного выполнения. Затем рассматривается сле-
дующая лексема, идущая за распознанной подстрокой. Если же процедура не может найти подстроку,
которая могла бы быть интерпретирована как требуемый нетерминальный символ, она заканчивается с
признаком неудачи или же вызывает процедуру диагностического сообщения.
Рассмотрим в качестве примера правило грамматики:
<ввод> → read (<список переменных>)
Процедура метода рекурсивного спуска, соответствующая нетерминальному символу <ввод>, пре-
жде всего исследует две последовательные лексемы "read" и "(". В случае совпадения эта процедура вы-
зывает другую процедуру, соответствующую нетерминальному символу <список переменных>. Если эта
процедура закончится успешно, то процедура <ввод> сравнивает следующую лексему с ")". Если все
эти проверки окажутся успешными, то процедура <ввод> завершается с признаком успеха и устанавли-
вает указатель текущей лексемы на лексему, следующую за ")".
Еще пример. Процедура, соответствующая нетерминальному символу <оператор>, анализирует
очередную лексему для того, чтобы выбрать одну из четырех альтернатив:
<оператор> → <присваивание>/<ввод>/<вывод>/<цикл>
Если это лексема read, то вызывается процедура <ввод>. Если это лексема, соответствующая сим-
волу идентификатор, то вызывается процедура <присваивание>, поскольку это единственная альтерна-
тива, которая может начинаться с лексемы идентификатор, и т.д.
Но если мы попытаемся написать полный набор процедур для грамматики, то столкнемся со сле-
дующей трудностью – процедура для нетерминала <список переменных> будет не в состоянии выбрать
одну из двух альтернатив, поскольку обе альтернативы: ид и <список переменных> могут начинаться с
лексемы ид.
<список переменных> → ид/<список переменных>, ид
Тут скрыта и более существенная трудность. Если процедура каким-либо образом решит попробо-
вать альтернативу <список переменных>/ид, то она немедленно вызовет рекурсивно саму себя для по-
иска нетерминального символа <список переменных>. Это приведет еще к одному рекурсивному вызо-
ву и т.д., в результате чего образуется бесконечная цепочка рекурсивных вызовов. Те же проблемы воз-
никнут и для некоторых других правил грамматики (<раздел переменных>, <раздел операторов>,
<арифметическое выражение>, <слагаемое>). Как избежать такой рекурсии? Для этого применяют дру-
гую запись грамматики. Например:
<список переменных> → ид {, ид}
Эта запись, являющаяся широко принятым расширением БНФ, означает, что конструкция, заклю-
ченная в фигурные скобки, может быть либо опущена, либо повторяться один или более число раз. Та-
ким образом, это правило определяет нетерминальный символ <список переменных> как состоящий из
единственной лексемы ид или же из произвольного числа следующих друг за другом лексем ид, разде-
ленных запятой. Это, бесспорно, эквивалентно ранее принятому правилу. В соответствии с этим новым
определением процедура <список переменных> сначала ищет лексему ид, а затем продолжает сканиро-
вать входной текст до тех пор, пока следующая пара лексем не совпадет с запятой и ид. Такая запись
устраняет проблему рекурсии, а также решает вопрос выбора из двух альтернатив.
Грамматика языка, к которому принадлежит предложение, представленное на рис. 1, имеет вид:

Страницы