7.6. Рекурсия и синтаксический анализ

7.6. Рекурсия и синтаксический анализ Синтаксис любого языка содержит прямые или косвенные рекурсивные определения. Например, в список операторов языка входит оператор цикла, который содержит заголовок и тело, являющееся опять-таки оператором. Любое, сколь угодно сложное выражение, заключенное в скобки, становится элементарным выражение (термом). Рекурсия в синтаксических анализаторах (распознавателях) может присутствовать явно или скрыто. Например, магазинные автоматы – конечные автоматы, снабженные стеком, используют этот стек для сохранения частей рекурсивно вложенных друг в друга фрагментов, но при этом сама программа распознавания рекурсии в явном виде не содержит, а является обыкновенным циклом.

Здесь нам более интересны рекурсивные распознаватели. К сожалению, изложение принципов распознавания и его математического аппарата – формальных грамматик, не входит в задачи этой книги. Для серьезного изучения автору остается препроводить читателя к [10,11], а самому попытаться изложить суть приведенных методов распознавания «на пальцах».

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

• рекурсивная функция возвращает значение выражения, представленного текстовой строкой;

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

• если строка содержит только выражение в скобках, то эти скобки уничтожаются, а по отношению к полученной строке функция вызывается рекурсивно;

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

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

//------------------------------------------------------76-01.cpp

// Калькулятор арифметических выражений со ()

int calc(char *s){

int inside=0; // уровень вложенности ()

char p1=NULL,p2=NULL; // указатели на символы операций + и * вне ()

for (char q=s;q!=NULL;q++)

        switch(*q)

                    {

case '*':

case '/': if (inside==0 && p2==NULL) p2=q;

                                break;                           // Запоминание первой * вне ()

case '+':

case '-': if (inside==0 && p1==NULL) p1=q;

                                break;                           // Запоминание первго + вне ()

case '(': inside++; break;

case ')': inside--; break;

                    }

if (p1!=NULL) p2=p1; // Запоминание самой низкоприоритетной

if (p2!=NULL){ // операции

        char c=*p2; *p2=0;                                 // "разрезать" строку на две части

        switch(c)                                               // и выполнить операцию над результатом

                    {                                               // для полученных частей

case '': return calc(s) calc(p2+1);

case '/': return calc(s) / calc(p2+1);

case '+': return calc(s) + calc(p2+1);

case '-': return calc(s) - calc(p2+1);

                    }}

if (s=='(' && (q-1)==')'){ // выражение в () - снять ()

        *(q-1)=0; return calc(s+1);                       // и вызвать рекурсивно для выражения в ()

        }                                                           // накопление константы

for (int n=0;s>='0' && s<='9';s++)

        n=n*10+*s-'0';

        return n;}                                               // все остальное игнорируется

Рекурсия в формальных грамматиках. Описание синтаксиса языков представлено контекстно-свободными формальными грамматиками. Каждой синтаксической единице соответствует группа правил. В левой части правила находится нетерминальный символ, обозначающий эту синтаксическую единицу, а в правых частях – варианты ее представления в виде цепочек, состоящих как из терминальных символов – то есть символов самого распознаваемого текста, так и из нетерминальных символов, то есть других синтаксических единиц, включенных в определение данной синтаксической единицы. Правила определяют такие свойства синтаксиса как вложенность, приоритеты и т.п.. Сущность синтаксического анализа состоит в построении последовательности вложений правил одного в другое по принципу: нетерминальный символ левой части правила может быть замен на одну из своих правых частей. Совокупность таких подстановок, приводящих в конце концов к исходной распознаваемой цепочке (предложение языка, состоящее из терминальных символов), образует дерево и является результатом распознавания.

Общепринятая иллюстрация – грамматика четырех арифметических действий со скобками:

F ::= i | i[E] | c | (E)

T ::= F | T*F | T/F

E ::= T | E+T | E-T

Z ::= E

Первая группа правил определяет терм – первичную синтаксическую единицу в виде идентификатора i, константы c, элемента массива i[E], у которого в скобках может стоять любое выражение. Здесь также определяется правило изменения приоритета операций с помощью скобок, которые превращают любое выражение E в первичную синтаксическую единицу.

Вторая и третья группы правил являются прямо рекурсивными и тем самым определяют способы формирования циклических цепочек произвольной длины вида FF/FF и T+T-T. Кроме того, вложенность описаний нетерминальных символов задает приоритеты операций, используемых в цепочках. Последнее правило определяет Z – начальный символ, из которого выводится любое предложение языка (цепочка символов) и с которого начинается или заканчивается распознавание.

Последовательность применения правил подстановки (дерево синтаксического разбора) для выражения i*(i+i) будет выглядеть так.

   Z     

   |

   E

   |

   T

 -----

 T * F

 | | ------------

 F | (    E     )

 | | | -------  |

 | | | E  +  T  |

 | | | |     |  |

 | | | T  |  F  |

 | | | |  |  |  |

 | | | F  |  i  |

 | | | |  |  |  |

 i * ( i  +  i  )

Синтаксический анализ методом рекурсивного спуска. Рекурсивный спуск является самым «естественным» алгоритм нисходящего разбора – построения дерева «сверху вниз». При нисходящем разборе этот каждый нетерминальный символ необходимо заменить на правую часть одного из правил из соответствующей группы, в котором он присутствует в левой части. Единственным основанием для такого выбора является начало той части терминальной строки (предложения), которое «покрывается» этим нетерминальным символом (синтаксической единицей).

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

//------------------------------------------------------76-02.cpp

//---- Распознаватель правил F ::= i | i[E] | c | (E)

char s[80]; // входная цепочка терминалов

int i; // текущий терминальный символ

extern void E(); // Объявление используемого распознавателя для E

void F() {

          switch(s[i]){

case 'c' : i++; printf("F::=c\n"); break;

case 'i' : i++;

                       if (s[i]=='['){

                                            printf("F::=i[E]\n");

                       i++; E();

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

                       }

else printf("F::=i\n");

          break;

case '(' : i++;

          printf("F::=(E)\n");

          E();

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

          else error();

          break;

default: error();

          }}

Индекс i является указателем на текущий нетерминальный символ во входной строке (цепочке). Каждая процедура, анализируя очередной символ, продвигает этот указатель вперед, если в выбранной правой части правила находится такой же символ, в противном случае информирует о синтаксической ошибке. Например, в правой части правила F::=i[E] после символа [ и нетерминала E следует символ ]. Последний и проверяется после вызова функции анализа нетерминала E. Если он действительно присутствует в строке как текущий символ, то он пропускается.

  if (S[i])==’]’) i++; else error();

Eсли в правой части правила имеется нетерминал, то в тот момент, когда в просматриваемом фрагменте строки «наступает очередь» этого нетерминала, вызывается функция, которая должна производить этот анализ для группы правил с этим нетерминалом в левой части. Например, после анализа цепочки терминалов i[ выясняется, что речь идет о правиле F::=i[E], тогда для выполнения анализа выражения в скобках необходимо просто вызвать фунцию распознавания для E.

Выбор одной или другой правой части может быть произведен только на основе анализа одного или нескольких текущих терминальных символов. Так выбор одного из правил F::=i | i[E] производится по первым двум символам (одного здесь не достаточно).

Некоторые трудности могут возникнуть при анализе правил, правая часть которых начинается с нетерминального символа. В этом случае необходимы содержательные преобразования группы правил. Например, вторая группа правил генерирует цепочки вида F F / F F / F с переменным количеством нетерминалов F и знаками операций , / между ними. Очевидно, процедура для нетерминала T должна распознавать циклическую последовательность таких символов и завершать распознавание, когда во входной цепочке ей встретится очередной символ, отличный от и / .

void T() {

puts("T::=F|T*F|T/F");

F(); while(s[i]=='*' || s[i]=='/') { i++; F(); }

}

void E() {

puts("E::=T|E+T|E-T");

T(); while(s[i]=='+' || s[i]=='-') { i++; T(); }

}

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

Нисходящий разбор с возвратами. Следующий пример является скорее иллюстративным, нежели практически значимым. Задача синтаксического анализа решается в нем путем полного перебора всех возможных правил подстановки. Отметим уже известные нам принципы организации рекурсивного процесса:

• рекурсивная функция при каждом своем вызове получает на вход очередной нетерминал sym и индекс начала терминальной цепочки s, которая должна быть выведена из него;

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

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

• если текущий символ правила является терминальным, то необходимо сравнить его с текущим «незакрытым» символом во входной строке. Если они одинаковы, то «закрыть его» - перейти к следующему и в правиле, и в цепочке. Если нет, отказаться от этого правил и перейти к следующему;

• для нетерминального символа в правиле нужно выполнить тот же самый алгоритм - попробовать произвести из него вывод и закрыть часть цепочки. Это делается рекурсивным вызовом той же функции, но уже для новой «незакрытой» части цепочки и нового нетерминала. Если полученный результат будет свидетельствовать об удачном выводе, то следует в текущем правиле также пропустить «закрытую» данным нетерминалом часть цепочки. Если вывод неудачен - перейти к следующему правилу;

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

//------------------------------------------------------76-03.cpp

char str[100]; // Правила грамматики

char GR[]={ "E:TM", "M:-E", "M:+E", "M:", "T:FG", "G:T", "G:/T", "G:",

"F:c", "F:iX", "X:[E]","X:", "F:(E)", NULL};

int isNT(char c) { // Является ли заданный символ нетерминальным

for (int i=0; GR[i]!=NULL; i++) if (GR[i][0]==c) return i;

return -1; }

int Step(char sym, int s){ // Вывод для нетерминала sym и

int i,j,k; // незакрытой части цепочки s

for (i=0; GR[i]!=NULL; i++) // Просмотр всех правил

if (GR[i][0]==sym){ // Левая часть правила совпадает с sym

    for (j=2,k=s; GR[i][j]!=0; j++){                      // Посимвольный просмотр правила

                    if (isNT(GR[i][j])==-1){                 // Нетерминальный символ

                                if (GR[i][j]==str[k])          // совпадает с символом строки

k++; // перейти в строке к следующему

else break; // иначе - неверное правило

                                }

else { // Нетерминал - рекурсивный вызов

                                int l=Step(GR[i][j],k);

                                if (l==-1) break;              // Нельзя вывести - неверное правило

k=l; // Иначе - пропустить закрытую часть

printf("*%s\n",GR[i]);

                    }

}

// Разбор правила удалось провести до конца

if (GR[i][j]==0) { printf("%s__%s\n",GR[i],&str[k]); return k; }

}

return -1; } // Ни одного правила не найдено

void main(){ printf("Строка:"); gets(str);

int k=Step('E',0); if (k!=-1 && str[k]==0) puts("O.K.");}

Естественным ограничением для полного перебора вариантов является исключение прямой или косвенной левосторонней рекурсии. То есть в грамматике принципиально недопустимы правила вида которые приводят к «зацикливанию» алгоритма. Такое правило будет применяется само к себе бесконечное число раз.

E ::= E + T или сочетания правил

E ::= X . . .

X ::= E . . .

Поэтому грамматика четырех арифметических действий со скобками должна быть представлена здесь несколько в другом виде (LL(1)-грамматика), содержащем правила с пустой правой частью.

E::= TM

M::= +E | -E | (пусто)

T::= FG

G::= *T | /T | (пусто)

F::= c | iX | (E)

X::= [E]| (пусто)