Нисходящий разбор с возвратами
В процессе нисходящего разбора происходит замена каждого нетерминала, который встречается в выводимой цепочке, на правую часть правила, в которой он находится в левой части. Очевидно, что самый простой алгоритм построения цепочки вывода заключается в полном переборе всех возможных цепочек. Тогда мы получаем классическую задачу поиска с полным перебором вариантов, которая решается с использованием рекурсивных функций. Соответствующая программная заготовка имеется в файле sindown.cpp. Приведенная в ней грамматика определяет 4 действия арифметики и круглые скобки. Для понимания сущности рекурсивного алгоритма нужно сосредоточиться на выполнении одного шага рекурсии, не пытаясь заглянуть “вглубь”:
грамматика задана в виде массива указателей на строки, содержащин правила. Входная цепочка - также строка
char *GR[]={”E:TM”,”M:E”,”M:+E”,”M:”,”T:FG”,“
G:*T”,”G:/T”,”G:”,”F:a”,”F:(E)”,NULL};
char str[80];
- рекурсивная функция при каждом своем вызове получает на вход очередной нетерминал и начало терминальной цепочки, которая должна быть выведена из него. Начало цепочки определяется номером очередного символа во входной строке str
int Step(char sym, int s)
- результатом работы текущего, а также всех вложенных (внутренних) вызовов является “покрытие” некоторой левой части цепочки деревом правил, выводимых из данного нетерминала. При этом функция выводит целое число, номер символа в строке, следующего за “покрытой” цепочкой. Если вывод неудачен, то возвращается значение -1.
.
E
T M
----- -------
F G (пусто)
| ----
a / T
| | ----
| | F G
| | | -------
| | a (пусто)
| | |
( a / a )
|_вход |____выход
рекурсивная функция просматривает набор правил выбирает их них те, которые имеют в левой части входной нетерминал.
Для каждого из них она просматривает его правую часть. При этом вводится новая переменная - k -индекс “незакрытой” части цепочки в процессе применения текущего правила
int Step(char sym, int s)
{ int i,j,k;
for (i=0; GR[i]!=NULL; i++)
if (GR[i][0]==sym)
{ for (j=2,k=s; GR[i][j]!=0; j++)
если текущий символ правила является терминальным, то необходимо сравнить его с текущим “незакрытым” символом во входной строке. Если они одинаковы, то “закрыть его” - перейти к следующему и в правиле, и в цепочке. Если нет, отказаться от этого правил и перейти к следующему.
if (isNT(GR[i][j])!=-1)
{. . .}
else
if (GR[i][j]==str[k]) k++;
else break;
для нетерминального символа в правиле нужно выполнить тот же самый алгоритм - попробовать произвести из него вывод и закрыть часть цепочки. Это делается рекурсивным вызовом той же функции, но уже для новой “незакрытой” части цепочки и нового нетерминала. Если полученный результат будет свидетельствовать об удачном выводе, то следует в текущем правиле также пропустить “закрытую” данным нетерминалом часть цепочки. Если вывод неудачен - перейти к следующему правилу.
if (isNT(GR[i][j])!=-1)
{ int l=Step(GR[i][j],k);
if (l==-1) break;
cout << “*” << GR[i] << “\n”; k=l;
}
обнаружение конца правила при попытке закрыть им часть цепочки свидетельствует об удачном его применении. Тогда функция возвращает индекс первого “незакрытого” символа, оставшегося после применения этого и вложенных в него правил
for (i=0; GR[i]!=NULL; i++)
if (GR[i][0]==sym)
{ for (j=2,k=s; GR[i][j]!=0; j++)
{ . . . }
if (GR[i][j]==0)
{
cout<<GR[i]<<”__”<<&str[k]<<”\n”; return k;
}
} return -1;
Естественным ограничением для полного перебора вариантов является исключение прямой или косвенной левосторонней рекурсии. То есть в грамматике принципиально недопустимы правила вида
E ::= E + T или сочетания правил
E ::= X . . .
X ::= E . . .
которые приводят к “зацикливанию” алгоритма. В данном случае такое правило применяется само к себе бесконечное число раз.
