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

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

1. восходящие;

2. нисходящие.

Восходящие методы (методы "снизу-вверх") начинают создание дерева с конечных узлов дерева и пытаются объединить их построением узлов всё более и более высокого уровня до тех пор, пока не будет достигнут корень дерева. Нисходящие методы (методы "сверху-вниз") начинают построение с корня дерева грамматического разбора и пытаются так его наращивать, чтобы последующие узлы соответствовали синтаксису анализируемого предложения.

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

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

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

Для иллюстрации данного метода рассмотрим следующую грамматику.

1. <оператор>::=<переменная>:=<выражение>

2. <переменная>::=ИМЯ | ИМЯ(<выражение>)

3. <выражение>:: =<терм> | <выражение>+<терм>

4. <терм>::=<множитель> | <терм>*<множитель>

5. < множитель>:: =< переменная> | (<выражение>)

Здесь ИМЯ - терминальный символ, представляемый как последовательность букв и цифр, начинающихся с буквы.

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

Реализация таких правил приводит к множественному рекурсивному вызову соответствующих процедур, что ведёт к зацикливанию программы синтаксического анализатора.

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

1. < оператор>::=<переменная>:=<выражение>

2. < переменная>::=ИМЯ | ИМЯ(<выражение>)

3. < выражение>::=<терм>{+<терм>}

4. < терм>:: =<множитель> {*<множитель>}

5. <множитель>:: =<переменная> | (<выражение>)

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

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

PROCEDURE INSTRUCT; Процедура для нетерминала <оператора>

BEGIN.

VARIABLE; Анализируется наличие переменной.

IF NXTSYMB<>’:=’ Проверяется наличие символа ": ="

THEN ERROR и затем анализируется выражение.

ELSE

BEGIN SCAN;

EXPR

END

END;

PROCEDURE VARIABLE; Процедура для нетерминала <переменная>.

BEGIN

IF NXTSYMB<>'буква’ Переменная должна начинаться с буквы.

THEN ERROR

ELSE

BEGIN SCAN; Взять символ, следующий за первой бук

WHILE NXTSYMB=’буква’ вой. Читать символы, пока они являются

OR NXTSYMB='цифра' DO буквами или цифрами.

SCAN;

IF NXTSYMB =’(‘

THEN Если символ, следующий за последней бук-

BEGIN SCAN; EXPR; вой иди цифрой, есть открывающаяся ско-

IF NXTSYMB<>')' бка, перейти к разбору выражения и про-

THEN ERROR верить, следует ли за выражением эакры-

ELSE SCAN ваюшаяся скобка. Занести в NXTSYMB сим-

END вол, следующий за обработанной констру-

END кцией.

END;

PROCEDURE EXPR; Процедура для нетерминала < выражение>.

BEGIN TERM; Выражение должно начинаться термом.

WHILE NXTSYMB=' +' DO После этого проверяется наличие конеч-

BEGIN SCAN; ного числа конструкций вида "+<терм>".

TERM

END

END;

PROCEDURE TERM; Процедура для нетерминала <терм> ана-

BEGIN FACTOR; логична предыдущей процедуре.

WHILE NXTSYMB=' *' DO

BEGIN SCAN;

FACTOR

END

END;

PROCEDURE FACTOR; Процедура для нетерминала <множитель>.

BEGIN По первому символу выбирается альтер

IF NXTSYMB=’(' THEN натива. Если это открывающаяся скобка,

BEGIN SCAN; EXPR; то анализируется выражение, которое

IF NXTSYMB<>')' должно заканчиваться закрывающейся

THEN ERROR скобкой. Если первый символ не скобка,

ELSE SCAN то анализируется переменная.

END

ELSE VARIABLE

END;

В представленных процедурах используются вся глобальная переменная NXTSYMB и несколько дополнительных процедур. Переменная NXTSYMB всегда содержит ту лексему, которая должна обрабатываться следующей. Процедура SCAN читает эту лексему из таблицы кодов лексем и помешает её в NXTSYMB. Процедура ERROR вызывается в тех случаях, когда обнаруживется ошибка. Она формирует и выдаёт сообщение об ошибке на стандартные устройства вывода и возвращает управление обратно. Синтаксический анализ начинается с обращения к процедуре SCAN, которая помещает самую первую лексему анализируемого текста в NXTSYMB, после чего вызывается процедура INSTRUCT, соответствующая корневому символу модифицированной грамматики. В процессе работы этой процедуры последовательно могут быть вызваны другие процедуры анализатора.

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