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

В лексическом анализе были рассмотрены две модели анализаторов: автоматная и на «жесткой» логике:

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

· В автоматной модели лексика «зашита» в управляющие таблицы конечного автомата (КА), т.е. по существу является данными. Это позволяет настраивать анализатор на различные варианты лексики, но требует предварительной работы по проектированию самого КА и построению его управляющих таблиц, либо наличия языка формального языка описания лексики и транслятора с него.

Наличие двух вариантов иллюстрирует один из фундаментальных тезисов теории алгоритмов - эквивалентность алгоритма и данных: уменьшить объем алгоритмической части программы можно за счет «переноса» управляющих конструкций алгоритма в данные и наоборот.

В синтаксическом анализе, аналогично, известен метод рекурсивного спуска, основанный на «зашивании» правил грамматики непосредственно в управляющие конструкции распознавателя. Идеи нисходящего разбора, принятые в LL(1)-грамматиках, в нем полностью сохраняются:

· происходит последовательный просмотр входной строки слева-направо;

· очередной символ входной строки является основанием для выбора одной из правых частей правил группы при замене текущего нетерминала;

· терминальные символы входной строки и правой части правила «взаимно уничтожаются»;

· обнаружение нетерминала в правой части рекурсивно повторяет этот же процесс.

В методе рекурсивного спуска они претерпевают такие изменения:

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

· во входной строке имеется указатель (индекс) на текущий «закрываемый символ». Этот символ и является основанием для выбора необходимой правой части правила. Сам выбор «зашит» в распознавателе в виде конструкций if или switch. Правила выбора базируются на построении множеств выбирающих символах, как это принято в LL(1)-грамматике;

· просмотр выбранной части реализован в тексте процедуры-распознавателя путем сравнения ожидаемого символа правой части и текущего символа входной строки;

· если в правой части ожидается терминальный символ и он совпадает с очередным символом входной строки, то символ во входной строке пропускается, а распознаватель переходит к следующему символу правой части;

· несовпадение терминального символа правой части и очередного символа входной строки свидетельствует о синтаксической ошибке;

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

Для начала рассмотрим, как работает метод на достаточно простой грамматике, построив для нее формальными методами множества выбирающих символов.

Z:: N# SEL(Z:: N#) = FIRST(N)=FIRST(U)={a}

N:: UM SEL(N:: UM) = FIRST(U)={a}

M:: +UM SEL(M:: +UM) = {+}

M:: e SEL(M:: e) = FOLLOW(M)=FOLLOW(N)={#, ]}

U:: aSK SEL(U:: aSK) = {a}

S:: aS SEL(S:: aS) = {a}

S:: e SEL(S:: e) = FOLLOW(S)=

FIRST*(K)  FOLLOW(U)=

FIRST*(K)  FIRST*(M)  FOLLOW(N)={[, +, ], #}

K:: [N] SEL(K:: [N]) = {[}

K:: e SEL(K:: e) = FOLLOW(K)=FOLLOW(U)=

FIRST*(M)  FOLLOW(N) = {#, +, ]}

Грамматика продуцирует цепочки вида aaa[a+a]+aa+aaa[a+a[a]], состоящие из идентификаторов, построенных из символов a, соединенных в цепочки символом ‘ + ’, возможно с квадратными скобками, в которых могут быть аналогичные цепочки. Текст распознавателя сначала напишем, формально следуя этой грамматике:

//---------------------------------------------------------------------------------------RecDown1.cpp

char s[100]=" aaa[aa+aa[a]]+aa#";

int i=0;

extern void N(), M(), U(), S(), K();

// Z:: N# SEL(Z:: N#)={a}

void Z(){

printf(" Z:: %s\n", & s[i]);

if (s[i]! ='a') throw " error a(1)";

N();

if (s[i]=='#') i++; // Проверка и пропуск символа в правой части правила

else throw " error #";

}

//N:: UM SEL(N:: UM)={a}

void N(){

printf(" N:: %s\n", & s[i]);

if (s[i]! ='a') throw(" error a(2)");

U(); M();

}

//M:: +UM SEL(M:: +UM) = {+}

//M:: e SEL(M:: e) ={#, ]}

void M(){

printf(" M:: %s\n", & s[i]);

switch(s[i]){

case '#':

case ']': return; // Аннулирующее правило

case '+': i++; // пропуск символа +

U(); M(); break;

default: throw " error [, a";

}}

//U:: aSK SEL(U:: aSK) = {a}

void U(){

printf(" U:: %s\n", & s[i]);

if (s[i]! ='a') throw " error a(3)";

i++; // пропуск символа a

S(); K();

}

//S:: aS SEL(S:: aS) = {a}

//S:: e SEL(S:: e) ={[, +, ], #}

void S(){

printf(" S:: %s\n", & s[i]);

if (s[i]=='a') { i++; S(); }

else return; // аннулирующее правило S:: e для всех остальных

}

//K:: [N] SEL(K:: [N]) = {[}

//K:: e SEL(K:: e) = {#, +, ]}

void K(){

printf(" K:: %s\n", & s[i]);

switch(s[i]){

case 'a': throw " error a(4)";

case '[': i++; // пропуск символа [

N();

if (s[i]==']') i++;

else throw " error 4";

break; // ошибка - ожидается символ ]

default: return; // аннулирющее правило по ], +, #

}}

void main(){

try{

Z(); if (s[i]==0) puts(" success");

} catch(char *ss){ puts(ss); puts(& s[i]); } }

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