![]() КАТЕГОРИИ: Архитектура-(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) |
Пример 21
Стек Вход Стек Вход Стековая реализация ПС-анализа Пример 20
Рассмотрим грамматику из примера 19 и входную строку id1 + id2 * id3. Последовательность сверток, приводящая входную строку к стартовому символу E, показана на рис.31. Последовательность правосентенциальных форм в этом примере представляет собой обращение первой последовательности правых порождений.
Рис. 31. Свертки, выполняемые ПС-анализатором
Существует две проблемы при синтаксическом анализе методом ПС-анализа. Первая заключается в обнаружении подстроки для свертки в правосентенциальной форме, вторая — в определении, какая именно продукция должна быть выбрана, если имеет несколько продукций с соответствующей подстрокой в правой части. Достаточно удобный путь реализации ПС-анализатора состоит в использовании стека для хранения символов грамматики и входного буфера для хранения анализируемой строки. В качестве маркера дна стека используется $, и этот же символ является маркером правого конца входной строки. Изначально стек пуст, а входной буфер содержит строку w $. $ w $ Синтаксический анализатор работает путем переноса нуля или нескольких символов в стек до тех пор, пока на вершине стека не окажется основа β. Затем он свертывает β левой части соответствующей продукции. Синтаксический анализатор повторяет этотцикл, пока не будет обнаружена ошибка или он не придет в конфигурацию, когда в стеке находится только стартовый символ, а входной буфер пуст: $ S $ Попав в эту конфигурацию, синтаксический анализатор прекращает работу и сообщает об успешном разборе входной строки.
Последовательность действий, выполняемых синтаксическим анализатором при разборе входной строки id1+id2*id3 грамматики из примера 19, используя первое порождение примера, показана на рис. 32.
Рис. 32. Конфигурации ПС-анализатора для входной строки id1+id2*id3
Основными операциями синтаксического анализатора являются перенос и свертка, но на самом деле ПС-анализатор может выполнять четыре действия: (1) перенос, (2) свертка, (3) допуск, (4) ошибка. 1. При переносе очередной входной символ переносится на вершину стека. 2. При свертке синтаксический анализатор распознает правый конец основы на вершине стека, после чего он должен найти левый конец основы и принять решение о том, каким нетерминалом заменить основу. 3. При допуске синтаксический анализатор сообщает об успешном разборе входной строки. 4. При ошибке синтаксический анализатор обнаруживает ошибку во входном потоке и вызывает программу восстановления после ошибок.
Замечание. Синтаксический анализатор для получения очередной основы переносит нуль или несколько символов в стек. Синтаксический анализатор никогда не заглядывает внутрь стека в поисках правого края основы. Все это делает стек особенно удобным для использования в реализации ПС-анализатора.
Дата добавления: 2014-12-27; Просмотров: 615; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |