Пример реализации метода рекурсивного спуска

Дана грамматика G({a,b,c},(A,B,C,S},P,S):

Р:

S -> аА | bВ

А -> а | bА | сС

В -> b | аВ | сС

С -> АаВb

Необходимо построить распознаватель, работающий по методу рекурсивного спуска.

Видно, что грамматика удовлетворяет условиям, необходимым для построения такого распознавателя.

Напишем процедуры на языке программирования С, которые будут обеспечи­вать разбор входных цепочек языка, заданного данной грамматикой. Согласно алгоритму, необходимо построить процедуру разбора для каждого нетерминаль­ного символа грамматики, поэтому дадим процедурам соответствующие наиме­нования. Входные данные для процедур разбора будут следующие:

· цепочка входных символов;

· положение указателя (считывающей головки МП-автомата) во входной це­почке;

· массив для записи номеров примененных правил;

· порядковый номер очередного правила в массиве.

Результатом работы каждой процедуры может быть число, отличное от нуля («истина»), или 0 («ложь»). В первом случае входная цепочка символов прини­мается распознавателем, во втором случае — не принимается. Для удобства реа­лизации в том случае, если цепочка принимается распознавателем, будем воз­вращать текущее положение указателя в цепочке. Кроме того, потребуется еще одна дополнительная процедура для ведения записей в массиве последователь­ности правил (назовем ее WriteRules).

Теперь для распознавания входной цепочки необходимо иметь целочисленный массив Rules достаточного объема для хранения номеров правил. Тогда работа распознавателя заключается в вызове процедуры proc_S(Str,0,Ru1es,&N), где Str — это входная цепочка символов, N — переменная для запоминания количества при­мененных правил (первоначально N = 0). Затем требуется обработка полученно­го результата: если результат на 1 превышает длину цепочки — цепочка принята, иначе — цепочка не принята. В первом случае в массиве Rules будем иметь по­следовательность номеров правил грамматики, необходимых для вывода цепоч­ки, а в переменной N — количество этих правил. На основе этой цепочки можно легко построить дерево вывода.

Объем массива Rules заранее не известен, так как заранее не известно количество шагов вывода. Чтобы избежать проблем с недостаточным объемом статического массива, приведенные выше процедуры распознавателя можно модифицировать так, чтобы они работали с динамическим распределением памяти (изменив про­цедуру WriteRules и тип параметра piRul в вызовах остальных процедур). На ло­гику работы распознавателя это никак не повлияет. Следует помнить также, что метод рекурсивного спуска основан на рекурсивном вызове множества проце­дур, что при значительной длине входной цепочки символов может потребовать соответствующего объема стека вызовов для хранения адресов процедур, их па­раметров и локальных переменных.

Из приведенного примера видно, что алгоритм рекурсивного спуска удобен и прост в реализации. Главным препятствием в его применении является то, что класс грамматик, допускающих разбор на основе этого алгоритма, сильно ограничен.

Дата добавления: 2014-01-20