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


Нисходящий разбор с возвратами - часть 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 . . .

 

которые приводят к “зацикливанию” алгоритма. В данном случае такое правило применяется само к себе бесконечное число раз.




Начало  Назад  Вперед



Книжный магазин