Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Дана грамматика 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; Просмотров: 197; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:

  1. C.( №1578) – пример № 3 с.13,14.
  2. C.2 Примеры операций
  3. Cовременные взгляды на атопические болезни как на системные заболевания. Алергические заболевания, класификация, клинические примеры.
  4. Ethernet — пример стандартной технологии коммутации пакетов
  5. II. Процесс реализации стратегии.
  6. Implementation methods Методы реализации
  7. L ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ НОВЫХ МЕТОДИК ОЦЕНКИ ЭФФЕКТИВНОСТИ УПРАВЛЕНИЯ ТРУДОМ
  8. L ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ НОВЫХ МЕТОДИК ОЦЕНКИ ЭФФЕКТИВНОСТИ УПРАВЛЕНИЯ ТРУДОМ
  9. SWOT-анализ в качестве универсального метода анализа.
  10. VI. Требования к отпуску (реализации)лекарственных препаратов в аптечных организациях
  11. А.5 Дополнительный материал по формальным методам
  12. Абсолютная система единиц предусматривает выбор единиц измерения так, чтобы коэффициент пропорциональности А всегда был равен единице, т.е. для приведенного примера будем иметь




studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.166.191.100
Генерация страницы за: 0.11 сек.