РЕКУРСИВНЫЙ СПУСК
Рассмотрим подкласс КС-грамматик - S-грамматики
Определение 5.2. S-грамматики — это подкласс контекстно-свободных грамматик, таких что:
1. Правая часть каждого правила начинается с терминала.
A ® ab | ba
2. Если в грамматике есть альтернативные правила, то они обязательно начинаются с разных терминальных символов
A ® ab | ba, причём a ¹ b.
S-грамматики часто называют разделёнными или простыми.
Пример 5.3. G[S]:
1. S ® aT
2. S ® TbS
3. T ® bT
4. T ® ba
G[S] не является S-грамматикой, так как в правиле 2 первый символ — нетерминальный, а это противоречит условию 1 для S-грамматик. Также 3 и 4 правила не удовлетворяют условию 2, так как два альтернативных правила начинаются с одного терминального символа.
Пример 5.4. G’[S]:
1. S ® abR
2. S ® bRbS
3. R ® a
4. R ® bR
G’[S] — удовлетворяет всем условиям и является S-грамматикой.
Анализ S-грамматик весьма эффективен методом рекурсивного спуска.
Метод рекурсивного спуска. Основная идея метода рекурсивного спуска состоит в том, что каждому нетерминалу грамматики ставится в соответствие определённая программная единица, процедура или функция (например в языке С — функция), которая распознаёт цепочку, порождаемую этим нетерминалом. Эти процедуры (функции) вызываются в соответствии с правилами грамматики, причём иногда вызывают сами себя рекурсивно. Следовательно, языком реализации этого метода, может быть лишь такой язык, который допускает рекурсию.
Пример 5.5. G[S]:
1. S ® aAS
2. S ® b
3. A ® cASb
4. A ® L
Легко видеть, что G[S] —S - грамматика. Приведем анализ G[S] методом рекурсивного спуска (рис. 5.18.).
| Корневой сегмент | Процедура S | Процедура A | |
“Начало”
Установим вход =
первый входной символ;
S;
Если вход ¹  то
ERROR;
Иначе
STOP;
/*
— признак окончания программы
*/
| Переход по символу: | Переход по символу: | |
| Символ | Метка | Символ | Метка |
| a | M1 | a | M4 |
| b | M2 | b | M4 |
| c | ER | с | M3 |
|
| ER |
| ER |
| Другой | ER | Другой | ER |
| M1: Scan; A; S; Возврат; M2: Scan; Возврат; ER: ERROR; Возврат; | M3: Scan; A; S; Если вход ¹ ‘b’ то ERROR; Иначе Scan; Возврат; M2: Возврат; |
Рис. 5.18. Алгоритм работы функции
На рис. 5.18. проиллюстрирован алгоритм работы функции (нетерминалов) A, S и корневого сегмента на некотором псевдоязыке. В соответствии с правилами 1, 2 грамматики G[S] процедура S должна начинаться с терминалов a или b и не может начинаться с терминалов c или , поэтому переход по этим символам влечёт ошибку, то есть переход на метку ERROR.
Приведем еще пример реализации метода рекурсивного спуска для грамматики “инструкция”
G[<инструкция>]
1. <инстр> ® <пер> = <выр> |
IF <выр> THEN <инстр> [ ELSE <инстр> ]
2. <пер> ® i[(<выр>)]
3. <выр> ® T{+T}
4. T ® O{*O}
5. O ® <пер> | (<выр>)
По классификации Хомского легко показать, что G[<инстр>] является контекстно-свободной и разделённой, то есть грамматикой типа LL(1) (LastLeft — самый крайний левый символ). В общем случае рассматривают грамматики LL(К), в которых по К левым символам определяется принадлежность цепочки к соответствующему правилу грамматики. Грамматики этого класса удовлетворяют главному критерию однозначности и безвозвратности разбора. Эти грамматики также как и S-грамматики эффективно анализировать методом рекурсивного спуска. Учитывая выше приведённый алгоритм рекурсивного спуска, покажем реализацию синтаксического процессора методом рекурсивного спуска на Алголоподобном языке с принятыми следующими допущениями:
1) Переменная nx (от слова next) всегда содержит очередной символ, по которому определяется альтернативами LL(1) - грамматики.
2) scan готовит очередной символ исходной программы и помещает его в nx.
3) error процедура, обрабатывающая ошибки синтаксиса (управление передаётся в вызывающую программу).
Следуя методу рекурсивного спуска, все нетерминалы грамматики G[<инстр>] обозначим своими процедурами, несущими туже аббревиатуру, что и нетерминалы.
instr /* <инстр> */
{
if (nx=“IF”) then
begin
scan;
expr;
if (nx!=“THEN”) then
error;
else
begin
scan;
instr;
if (nx=“ELSE”) then
begin
scan;
instr;
end;
end;
end;
else
begin
var;
if (nx!=“=”) then
error;
else
begin
scan;
expr;
end;
end;
}
/*---------------------------------------------------------------------*/
var /* <пер> */
{
if (nx!=“i”) then error;
else
begin
if (nx!=“(”) then
begin
scan;
expr;
if (nx!=“)”) then error;
else scan;
end;
end;
}
/*---------------------------------------------------------------------*/
expr /* <выр> */
{
t;
while (nx=“+”) do
begin
scan;
t;
end;
}
/*---------------------------------------------------------------------*/
t /* Т */
{
o;
while (nx=“*”) do
begin
scan;
o;
end;
}
/*---------------------------------------------------------------------*/
o; /* O */
{
if (nx=“(”) then
begin
scan;
expr;
if (nx!=“)”) then error;
else scan;
end;
else var;
}