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