Пример 21

Стек Вход

Стек Вход

Стековая реализация ПС-анализа

Пример 20

Рассмотрим грамматику из примера 19 и входную строку id₁ + id₂ * id₃. После­довательность сверток, приводящая входную строку к стартовому символу E, показана на рис.31. Последовательность правосентенциальных форм в этом примере представляет собой обращение первой последовательности правых порождений.

Правосентенциальная форма	Основа	Сворачивающая продукция
id1+id2+id3 E+id2*id3 E+E*id3 E+E*E E	id1 id2 id3 E*E E+E	E → id E → id E → id E → E*E E → E+E

Рис. 31. Свертки, выполняемые ПС-анализатором

Существует две проблемы при синтаксическом анализе методом ПС-анализа. Первая заключается в обнаружении подстроки для свертки в правосентенциальной форме, вторая — в определении, какая именно продукция должна быть выбрана, если имеет несколько продукций с соответствующей подстрокой в правой части. Достаточно удобный путь реализации ПС-анализатора состоит в использовании стека для хранения символов грамматики и входного буфера для хранения анализируемой строки. В качестве маркера дна стека используется $, и этот же символ является маркером правого конца входной строки. Изначально стек пуст, а входной буфер содержит строку w $.

$ w $

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

$ S $

Попав в эту конфигурацию, синтаксический анализатор прекращает работу и сообщает об успешном разборе входной строки.

Последовательность действий, выполняемых синтаксическим анализатором при разборе входной строки id₁+id₂*id₃ грамматики из примера 19, используя первое порождение примера, показана на рис. 32.

Стек	Вход	Действие
(1) $ (2) $id1 (3) $ E (4) $ E + (5) $ E + id2 (6) $ E + E (7) $ E + E * (8) $ E + E *id3 (9) $ E + E*E (10) $ E + E (11) $ E	id1+id2* id3$ +id2* id3$ +id2* id3$ id2* id3$ * id3$ * id3$ id3$ $ $ $ $	Перенос Свертка по E →id Перенос Перенос Свертка по E →id Перенос Перенос Свертка по E →id Свертка по E*E Свертка по E+E Допуск

Рис. 32. Конфигурации ПС-анализатора для входной строки id₁+id₂*id₃

Основными операциями синтаксического анализатора являются перенос и свертка, но на самом деле ПС-анализатор может выполнять четыре действия: (1) перенос, (2) сверт­ка, (3) допуск, (4) ошибка.

1. При переносе очередной входной символ переносится на вершину стека.

2. При свертке синтаксический анализатор распознает правый конец основы на вер­шине стека, после чего он должен найти левый конец основы и принять решение о том, каким нетерминалом заменить основу.

3. При допуске синтаксический анализатор сообщает об успешном разборе входной строки.

4. При ошибке синтаксический анализатор обнаруживает ошибку во входном потоке и вызывает программу восстановления после ошибок.

Замечание. Синтаксический анализатор для получения очередной основы переносит нуль или несколько символов в стек. Синтаксический анализатор никогда не заглядывает внутрь стека в поисках правого края основы. Все это делает стек особенно удобным для использования в реализации ПС-анализатора.

Дата добавления: 2014-12-27