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


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


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

            |_вход   |____выход

 

рекурсивная функция просматривает набор правил  выбирает их них те, которые имеют в левой части входной нетерминал.


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



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