14 Нисходящий синтаксический анализ. Методы восстановления после ошибок.

Восстановление после синтаксических ошибок

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

Если в момент обнаружения ошибки на верхушке магазина оказался нетерминальный символ A и для него нет правила, соответствующего входному символу, то сканируем вход до тех пор, пока не встретим символ либо из FIRST(A), либо из FOLLOW(A). В первом случае разворачиваем A по соответствующему правилу, во втором - удаляем A из магазина.

Если на верхушке магазина терминальный символ, то можно удалить все терминальные символы с верхушки магазина вплоть до первого (сверху) нетерминального символа и продолжать так, как это было описано выше.

15 Восходящий синтаксический анализ. Понятие основы.

основной метод восходящего синтаксического анализа, известный как синтаксический анализ типа "перенос/свертка". Простой для реализации вид ПС-анализа, именуемый синтаксическим анализом приоритета операторов. ПС-анализ пытается строить дерево разбора для входной строки, начиная с листьев (снизу) и работая по направлению к корню дерева (вверх). Этот процесс можно рассматривать как свертку строки w к стартовому символу грамматики. На каждом шаге свертки некоторая подстрока, соответствующая правой части продукции, заменяется символом из левой части этой продукции, и если на каждом шаге подстроки выбираются корректно, то мы получаем обращенное правое порождение.

Выделяют 3 базовых понятия.

Основа строки А – это подстрока , для которой существует правило в этой грамматике B -> .

Свертка – это замещение основы на левый символ, правила в цепочке вывода ( на B)

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

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

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

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

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

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

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

Основа находится на вершине стека. ПС-анализатор не просматривает всю строку.

Если грамматика является неоднозначной, то ПС-анализатор не может ее распознать.

Восстановление после ошибок в восходящем анализе.

Имеется два условия, когда процесс синтаксического анализа может обнаружить син­таксическую ошибку.

1. Если между терминалом на вершине стека и текущим входным символом не определено ни одно из отношений приоритета.

2. Если найдена основа, но не имеется продукции с этой основой в правой части. Вспомним, что в алгоритме синтаксического анализа приоритета операторов свертываются основы, составленные только из терминалов. Однако хотя нетерминалы и рассматриваются как неразличимые, в стеке синтаксического анализа для них имеются соответствующие места. Таким образом, когда в (2) мы говорим о соответ­ствии основы и правой части продукции, то подразумеваем, что в них должны быть одни и те же терминалы и позиции, занятые нетерминалами.