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

Рассмотрим, например, язык, генерируемый грамматикой со следующими порождающими правилами:

PROGRAM->begin DECLIST comma STATELIST end

DECLIST->d semi DECLIST

DECLIST->d

STATELIST->s semi STATELIST STATELIST->s Сначала видоизменим грамматику:

PROGRAM->begin DECLIST comma TATELIST end

DECLIST->d X X->semi DECLIST

X->e STATELIST->s Y

Y->semi STATELIST Y->e.

Теперь напишем процедуру распознавания каждого нетерминала. Начав с символа (PROGRAM), получим

ргос PROGRAM = void: begin if symbol 4)egin tben error fi; symbol: = lexical; DECLIST;

if symbol 9 comma then error fi; symbol: = lexical; STATELIST;

if symbol 7 end then error fi end;

proc DECLIST= void:

begin if symbol 9d then error fi;

symbol := lexical;

end;

proc X=void:

if symbol = semi then

symbol := lexical; DECLIST

elif symbol = comma

then skip

else error

proc STATELIST = void:

begin if symbol then error fi;

symbol := lexical; Y

end;

proc Y = void:

if symbol = semi then

symbol: = lexical; STATELIST

elif symbol = end then skip

else error

В этих процедурах сделан ряд допущений:

1. error - процедура обращения с синтаксическими ошибками; детали нас здесь не интересуют;

2. lexical - процедура, которая читает литеры исходного текста и выдает следующий символ. Если лексический анализ выполняется предыдущим проходом, lexical просто читает следующий символ;

3. semi, comma и т. д. - идентификаторы, значениями которых являются представления соответствующих терминалов во время компиляции;

4. прежде чем вызывается PR0GRAM, происходит следующее присваивание:

symbol: = lexical.

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

PROGRAM->begin DECLIST comma STATELIST end

DECLIST->d (semi d)* STATELIST->s (semi s)* где (х)* означает нуль или более реализациий х. Тогда процедуры для DECLIST и STATELIST становятся такими:

proc DECLIST = void: begin if symbol d then error fi: symbol: = lexical; while symbol = semi do symbol: = lexical; if symbol Ф d then error fi; symbol: = lexical od end:

proc STATELIST = void:

begin if symbol Ф s then error fi;

symbol : = lexical;

while symbol = semi

do symbol: = lexical;

if symbol Ф s then error fi :

symbol : = lexical

Замена рекурсии итерацией, возможно, делает анализатор более эффективным, а также (не бесспорно) более удобочитаемым.

Преимущества написания рекурсивного нисходящего анализатора очевидны. Основные из них - это скорость написания анализатора на основании соответствующей грамматики. Другое преимущества заключается в соответствии между грамматикой и анализатором, благодаря которому увеличивается вероятность того, что анализатор окажется правильным, или, по крайней мере, того, что ошибки будут носить простой характер. Недостатки этого метода, хотя и менее очевидны, не менее реальны. Из-за большого числа вызовов процедур во время синтаксического анализа анализатор становится относительно медленным. Кроме того, он может быть довольно большим по сравнению с анализаторами, основанными на табличных методах разбора, которые описываются ниже. Несмотря на то что данный метод способствует включению в анализатор действия по генерированию кода, это неизбежно приводит к смешиванию различных фаз компиляции. Последнее снижает надежность компиляторов или усложняет обращение с ними и как бы привносит в анализатор зависимость от машины. Рекурсивный метод разбора сверху вниз родствен другому хорошо