3.5. Понятие о рекурсивном спуске

 
  Метод рекурсивного спуска основан на моделировании LL(k) – анализа без необходимости полного моделирования МА. Такая возможность появляется за счет использования рекурсивных алгоритмов, в этом случае МА на самом деле моделируется неявно за счет размещения параметров вызовов в стеке (см. курс «программирование» - рекурсия).
Идея метода. Для каждого нетерминала создается функция, моделирующая анализ начиная с данного нетерминала. В случае если при раскрытии нетерминала встречается другой нетерминал происходит вызов соответствующей функции. Процесс продолжается до исчерпания входной цепочки (программы) или обнаружения ошибки. Необходимым условием реализации идеи – отсутствие левой рекурсии в грамматике (в этом случае анализ будет циклить). Анализ начинается с нетерминала S;
Пример (наш язык).
S -> A;S| A| л
A -> {S}| L@M| k1L| k2M| k3Mk4A| k3Mk4Ak5A| k6Mk7A| k8N(iT)| k9M| k10
L -> iT| iT[M]
M -> iT | iT[M]| cT| N(M)| (M)| MRM
N -> fT
R -> +| -| *| /| \| <| >| ~| $ =| ^
T -> oT| 1T|….| 9T| 0| 1|…| 9
S -> A;S| A| л
A -> {S}| L@M| k1L| k2M| k3Mk4A| k3Mk4Ak5A| k6Mk7A| k8N(iT)| k9M| k10
L -> iT| iT[M]
M -> LZ|cTZ| N(M)Z| (M)Z| MZ
N -> fT
R -> +| -| *| /| \| <| >| ~| $ =| ^
T -> oT| 1T|….| 9T| 0| 1|…| 9
Z->RM|л

Замечание. На самом деле в данном языке существует леворекурсивное правило M->MRM. Однако мы пока не будем обращать на него внимание по причнам, к-е рассмотрим в пункте 3.3.6.

Procedure SAnal; //анализатор S, т.е. всей грамматики
Begin
If str<>’’ then begin //str – анализируемая строка S->л (пустая строка –ОК)
AAnal;
If str – не исчерпана then begin //если исчерпана – OK S->A
If str[cur]<>’;’ then begin //cur – текущая позиция – глобальная переменная
Res:=false; //результат анализа – глобальная переменная
Halt;
End;
Inc(cur); //сдвигаем в строке в соответствии с “;”
SAnal
End
End;

Procedure Anal;
Begin
Case str[cur] of
‘{‘: begin
inc(cur);
SAnal;
If str[cur]<>’}’ then begin
res:=false;
halt
else inc(cur)
end;
‘I’: begin
LAnal;
If str[cur]<>’@’ then begin
res:=false;
halt
else inc(cur);
MAnal;
end;
‘k’: begin
case str[cur+1] of //смотрим один символ вперед
‘1’: begin
…………………//здесь надо смотреть еще 3-й символ – k1 или k10
end;
………
end
end
……………………..
end
end;

…………………………
Аналогично, реализуем процедуры для остальных нетерминалов.