Основы конструирования компиляторов

         

Рекурсивный спуск


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

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

В процедуре A для случая, когда имеется правило A

ui, такое, что ui
*e (напомним, что не может быть больше одного правила, из которого выводится e), приведены два варианта 1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующий входной символ FOLLOW(A). Если нет - выдается ошибка. Во втором варианте

этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую A.

void A(){ // A

u1 | u2 | ...| uk

if (InSym

FIRST(ui)) // только одному!

if (parse(ui))

result("A

ui");

else error();

else

//Вариант 1:

if (имеется правило A

ui

такое, что ui

*e)

//Вариант 1.1

if (InSym

FOLLOW(A))

result("A

ui");



else error();

//Конец варианта 1.1

//Вариант 1.2:

result("A

ui");

//Конец варианта 1.2

//Конец варианта 1

//Вариант 2:

if (нет правила A

ui такого, что ui
*e)

error();

//Конец варианта 2

}

 

boolean parse(u){ // из u не выводится e!

v = u;

while (v

e){ // v = Xz

if (X - терминал a)

if (InSym

a)

return(false);

else InSym = getInsym();

else // X - нетерминал B

B();

v = z;

}

return(true);

}



Содержание раздела