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

       

Нисходящий разбор с возвратами


В процессе нисходящего разбора происходит замена каждого нетерминала, который встречается в выводимой цепочке, на правую часть правила, в которой он находится в левой части. Очевидно, что самый простой алгоритм построения цепочки вывода заключается в полном переборе всех возможных цепочек. Тогда мы получаем классическую задачу поиска с полным перебором вариантов, которая решается с использованием рекурсивных функций. Соответствующая программная заготовка имеется в файле 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 . . .

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


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