Курс Основы построения трансляторов

       

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


Рассмотрим еще один  “естественный” алгоритм нисходящего СА. Пусть имеется некоторый нетерминальный символ, из которого выводится предложение языка - цепочка терминальных символов. При нисходящем разборе этот нетерминал на первом шаге необходимо заменить на правую часть одного из правил, в котором он присутствует в левой части. Рассмотрим пример:

F ::= i | i[E] | c | *E | &E | i.i | (E)

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

.

         F

         |

   aaa[jj+46]…      (…i[i+c]…)

Для удобства восприятия входная строка приведена и в синтаксических, и в лексических единицах. Тогда единственная проблема состоит в том, чтобы на очередном шаге построения дерева нетерминал  F заменить на правую часть одного из перечисленных  правил. Человек сделает это интуитивно, выбирая правило F::=i[E] - определение элемента массива

.           

                   F

                   |

              i [  E   ]

                   |

 aaa[ jj+46 ]… (i[i+c])

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


Для понимания вышесказанного рассмотрим фрагмент программы:

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

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

void F()

{

switch(s[i])

      {

case ‘*’: i++; E(); break;

case ‘&’: i++; E(); break;

case ‘c’: i++; break;

case ‘(‘: i++; E();

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

case ‘i’: i++;

if (s[i]==’.’)

{ i++; if (s[i]==’i’) i++;

else error(); }

else if (s[i]==’[’)

{ i++; E(); if (s[i]==’]’) i++;

else error(); }

else i++;

break;

      }}

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

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

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

выбор одной или другой правой части может быть произведен только на основе анализа одного или нескольких текущих терминальных символов. Так

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

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


Например, процедура обработки нетерминала F для правила F::=i[E] вызывает процедуру обработки нетерминала E, который в свою очередь может вызвать процедуру обработки нетерминала F. Поэтому данный метод получил название РЕКУРСИВНОГО СПУСКА.

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

int F()             // результат вычисления F

{

int v,n;            // результат промежуточных вычислений

switch(s[i])     

      {

case ‘(‘: i++; v=E();

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

case ‘c’: i++; v = значение_константы_c; break;

case ‘i’: i++;

if (s[i]==’.’)

{ i++; if (s[i]==’i’)

{ v=значение_поля_s[i]_переменной_s[i-2]; i++;}

else error(); }

else if (s[i]==’[’)

{ i++; n=E(); if (s[i]==’]’)

{ v=значение_элемента_n_массива_s[i-2]; i++; }

else error(); }

else { v=значение_переменной_s[i];i++; }

break;

} return v; }

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

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

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



void T()

{ while (1)

{ F();

if (!(s[i]==’*’ || s[i]==’/’)) break;

i++;

}

}

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

int      VAR[26];      // Массив значений переменных A..Z

char S[100];           // Входная строка

int      i;            // Текущий символ строки

void      error(int n, int i); // Вывод сообщения об ошибке

 // с номером n и символом i

extern      int      E();

int      F()                   // F ::= a..z | целое | (E)

{ int      x;

if (isdigit(S[i]))

      { x=0;                  // Накопление целой константы

      do      { x=x * 10 + S[i] - ‘0’; i++; }

while (isdigit(S[i])); return(x); }

else

if (isalpha(S[i]))            // Чтение значения переменной

{ x=VAR[toupper(S[i])-‘A’]; i++; return(x); }

else

if (S[i]==’(‘)                // Анализ выражения в скобках

{ i++; x=E();

if (S[i]==’)’) { i++; return(x); }}

else { error(2,i); return(0); }}

int      T()                  // T ::= T * F | T / F | F

{ int x; x=F();

while (1)

switch      (S[i]) {

case      ‘*’: i++; x=x*F(); break;

case      ‘/’: i++; x=x/F(); break;

default:      return(x); }}

int      E()                 // E ::= E + T | E - T | T

{ int x; x=T();

while (1)

switch      (S[i]) {

case      ‘+’: i++; x=x+T(); break;

case      ‘-‘: i++; x=x-T(); break;

default:      return(x); }}

// Правила объединяют операции сравнения и присваивания

int      P()      // P ::= E=>a…z | E=E | E>E | E<E | E#E

{ int x;      x=E();

switch      (S[i]) {

case ‘=’:   i++;

if (S[i]==’>’)

                { i++;

    if (isalpha(S[i]))

                    { VAR[toupper(S[i])-‘A’] = x;

                    return(x); }

                else      { error(4,i); return(0); }

            }

            else return( x== E() );

case ‘#’:   i++; return( x!= E() );

case ‘<’:   i++; return( x < E() );

case ‘>’:   i++; return( x > E() );

case ‘\0’:  return(x);

default:    error(3,i); return(0); }}


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