4. Разработка синтаксического анализатора методом рекурсивного спуска

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

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

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

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

Пример.Пусть имеется следующий набор определений для нетерминального символа <оператор>:

<оператор> --> <оператор чтения>|<оператор присваивания>|<оператор вывода>

<оператор чтения> --> READ(<список имен>)

<оператор присваивания> --> ИМЯ:=<выражение>

<оператор вывода>--> WRITE(<список имен>)

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

Если очередная лексема есть лексема READ, то для продолжения следует выбрать первую альтернативу, и из процедуры для нетерминального символа <оператор> должна вызываться процедура, соответствующая нетерминальному символу <оператор чтения>. Если же очередной прочитанной лексемой является лексема типа идентификатор (обобщенное название ИМЯ), то должна быть вызвана процедура, соответствующая нетерминальному символу <оператор присваивания>. Если прочитанной является лексемаWRITE, то должна вызываться процедура, соответствующая нетерминальному символу <оператор вывода>.

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

Соответствующая нетерминальному символу <оператор> процедура могла бы иметь следующий вид:

ProcedureОператор;

Begin

ifЛексема =I{текущая лексема имеет тип имя}

thenПрисваивание {вызов процедуры для оператора присваивания}

elseifЛексема =Read

thenЧтение {вызов процедуры для оператора чтения}

elseifЛексема =Write

thenЗапись {вызов процедуры для оператора записи}

elseОшибка в операторе;

end;

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

1) <оператор>-><оператор чтения>|<оператор присваивания>|<оператор вывода>

2) <оператор чтения> -> READ(<список имен>)

3) <оператор вывода>--> WRITE(<список имен>)

4) <оператор присваивания>->ИМЯ:=<выражение>

5) <список имен>->ИМЯ|<список имен>ИМЯ

6) <выражение>-><терм>|<выражение>+<терм>|<выражение>-<терм>

7) <терм>-><множитель>|<терм>*<множитель>

8) <множитель>->ИМЯ|ЦЕЛОЕ|(<выражение>)

Здесь терминальные символы, обозначенные как ИМЯ и ЦЕЛОЕ, означают соответственно любой идентификатор и любую константу целого типа.

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

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

Рассмотрим правило 5. Оно состоит из 2 альтернатив, вторая из которых начинается с нетерминального символа <список имен>, т.е. это правило имитирует структуру следующего вида:

A->a|Aa,

где нетерминальному символу А соответствует <список имен>,

терминальному символу aсоответствует ИМЯ.

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

Свойством леворекурсивности обладают также правила 6 и 7. Чтобы исключить левую рекурсию в этих правилах, можно представить их в несколько иной форме, используя итерацию (итеративное повторение) вместо рекурсии:

5) <список имен>::=ИМЯ {, ИМЯ}

6) <выражение>::=<терм>{(+<терм>,-<терм>)}

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

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

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

Пример 1Необходимо методом рекурсивного спуска провести анализ предложения языка

READ(G);

Для разбора этого предложения потребуется 2 процедуры, соответствующие нетерминальным символам <оператор чтения> и <список имен>. Первую процедуру назовем ЧТЕНИЕ, вторую – ИМЯ. В примере будут даны описания этих процедур на псевдоязыке, подобном Паскалю. В процедурах используется переменная под именем ЛЕКСЕМА, значением которой являются коды лексем. Пусть таблица кодов лексем имеет следующий вид:

№ п/п	Лексема	Код
1	ИМЯ	I
2	КОНСТАНТА	C
3	,	T2
4	:=	T5
5	(	T6
6	)	T7
7	+	T8
8	WRITE	T9
9	READ	T18
10	-	T21
11	*	T22

Кроме того, в процедурах будут использоваться:

а) логическая переменная под именем РЕЗУЛЬТАТ (RESULTAT), принимающая значениеTRUE,FALSEв зависимости соответственно от успешного или неуспешного завершения работы очередной синтаксической процедуры;

б) вспомогательная процедура ЧтСл, что означает чтение следующей лексемы, которая осуществляет обращение к таблице кодов лексем сканера (лексического анализатора), читает оттуда очередную лексему и присваивает ее значение переменной ЛЕКСЕМА.

Procedure ЧТЕНИЕ;

Begin

Resultat:=FALSE;

If ЛЕКСЕМА=T18 Then

Begin

ЧтСл;

If ЛЕКСЕМА=T6 Then

Begin

ЧтСл;

IfИМЯ завершилось успешноThen

IfЛЕКСЕМА=Т7Then

Begin

Resultat:=TRUE;

ЧтСл;

End

End

End

If Resultat=TRUE Then

успешное завершение

Elseнеудачное завершение

End{чтение}

Procedure ИМЯ;

Begin

Resultat:=FALSE;

If ЛЕКСЕМА=I Then

Begin

Resultat:=True;

ЧтСл;

While ЛЕКСЕМА=T2 AND (Resultat=TRUE) Do

Begin

ЧтСл;

If ЛЕКСЕМА=I Then

ЧтСл;

Else Resultat:=FALSE;

End

End

If Resultat=TRUE Then

успешное завершение

Elseнеудачное завершение

End{ИМЯ}

Процедура ЧТЕНИЕ распознает во входной строке лексем сначала READ, затем лексему «(», после этого вызывается процедура ИМЯ; она распознает текущую лексему либо как одиночное имя, либо как последовательность одиночных имен, разделенных запятой, при этом если встречается конструкция «ИМЯ,», за которой не следует еще одно имя, то подобное сочетание лексем рассматривается как ошибка и процедура ИМЯ завершается с признаком неудачного окончания. Если процедура ИМЯ заканчивается успешно, то выполняется возврат в процедуру ЧТЕНИЕ, там осуществляется попытка обработки очередной лексемы как «)». После этого процедура ЧТЕНИЕ завершает свою работу с признаком успешного завершения.

Пример 2Необходимо выполнить анализ предложения следующего вида:

SUM:=SUM* 100.

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

1. ПРИСВАИВАНИЕ (главная процедура), а также три вызываемых,

2. ВЫРАЖЕНИЕ,

3. ТЕРМ,

4. МНОЖИТЕЛЬ.

Procedure ПРИСВАИВАНИЕ;

Begin

Resultat:=FALSE

If ЛЕКСЕМА=I Then

ЧтСл;

If ЛЕКСЕМА=T5 Then

Begin

ЧтСл;

IfВЫРАЖЕНИЕ завершено успешноTHEN

Resultat:=TRUE;

End

If Resultat=TRUE Then

успешное завершение

Else неудачное завершение

End

Эта процедура интерпретирует текущие читаемые лексемы в соответствии с правилом 4.

Procedure ВЫРАЖЕНИЕ;

Begin

Resultat:=FALSE;

IfТЕРМ завершилось успешноThen

Begin

Resultat:=TRUE;

While ((ЛЕКСЕМА=T8) OR (ЛЕКСЕМА=T21))

AND (Resultat:=TRUE) Do

Begin

ЧтСл;

If ТЕРМ завершилось неудачно Then

Resultat:=FALSE;

End

End

If Resultat=TRUE Then

успешное завершение

Elseнеудачное завершение

End{ВЫРАЖЕНИЕ}

Эта процедура интерпретирует строку читаемых лексем в соответствии с правилом 6.

Procedure TEPM;

Begin

Resultat:=FALSE;

IfМНОЖИТЕЛЬ завершилось успешноThen

Begin

Resultat:=TRUE;

While (ЛЕКСЕМА=T22) AND

(Resultat=TRUE) Do

Begin

ЧтСл;

IfМНОЖИТЕЛЬ закончилось неудачноThen

Resultat:=FALSE

End

End

If Resultat=TRUE Then

успешное завершение

Elseнеудачное завершение

End; {ТЕРМ}

Эта процедура интерпретирует текущую строку лексем в соответствии с правилом 7.

Procedure МНОЖИТЕЛЬ;

Begin

Resultat:=FALSE;

If (ЛЕКСЕМА=I) OR (ЛЕКСЕМА=С) Then

Begin

Resultat:=TRUE;

ЧтСл;

End

Else

If ЛЕКСЕМА=T6 Then

Begin

ЧтСл;

IfВЫРАЖЕНИЕ завершилось успешноThen

If ЛЕКСЕМА=T7 Then

Begin

Resultat:=TRUE;

ЧтСл;

End;

End;

If Resultat=TRUE Then

успешное завершение

Elseнеудачное завершение

End; {МНОЖИТЕЛЬ}

Эта процедура интерпретирует текущую строку лексем в соответствии с правилом 8.