Нисходящий разбор с возвратами - часть 2
Для каждого из них она просматривает его правую часть. При этом вводится новая переменная - 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 . . .
которые приводят к “зацикливанию” алгоритма. В данном случае такое правило применяется само к себе бесконечное число раз.