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

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

Стек $ Вход w$

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

Стек $S Вход $

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

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

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

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

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

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

Грамматики предшествования

Принцип организации распознавателя входных цепочек языка, заданного грамматикой предшествования, основан на том, что для каждой упорядоченной пары символов в грамматике устанавливается некоторое отношение, называемое отношением приоритетов. В процессе разбора входной строки расширенный МП-автомат сравнивает текущий символ входной цепочки с одним из символов, находящихся на вершине стека автомата. В процессе сравнения проверяется, какое из возможных отношений приоритетов существует между этими двумя символами. В зависимости от найденного отношения, выполняется либо перенос, либо свертка. При отсутствии отношения приоритетов между символами алгоритм сигнализирует об ошибке.

Пусть имеется КС-грамматика и на некотором шаге вывода получена сентенциальная форма вида ξ^* ξ_i ξ_j ξ^*. Символы ξ_i ξ_j стоят рядом в сентенциальной форме. Соседство этих символов характеризуется одним из отношений специального вида – отношений предшествования.

1) Между символами ξ_i и ξ_j существует отношение ξ_i ξ_j, если в грамматике есть правило вида A–>α ξ_i ξ_j β, где α , β принадлежат алфавиту V^*.

2) Между символами ξ_i и ξ_j существует отношение ξ_i <• ξ_j, если в грамматике есть правило вида A–>α ξ_i В β и вывод вида В=^*> ξ_j γ, где α , β, γ принадлежат алфавиту V^*.

3) Между символами ξ_i и ξ_j существует отношение ξ_i •> ξ_j, если в грамматике есть правило вида A–>α ВС β и выводы вида В=^*> γ₁ ξ_j и С=^*> ξ_j γ₂ или правило вывода вида A–>α В ξ_j β и вывод В=^*> γ ξ_i , где α , β, γ_1, γ₂ , γ принадлежат алфавиту V^*.

Тип отношения предшествования показывает, что, если

1. ξ_i ξ_j, то оба символа принадлежат одной основе.

2. ξ_i <• ξ_j, то ξ_j – самый левый символ некоторой основы.

3. ξ_i •> ξ_j, то ξ_i – самый правый символ некоторой основы.

КС-грамматика является грамматикой простого предшествования, если она однозначна, не содержит ε-продукций и для любой пары ее символов (терминальных и нетерминальных) выполняется не более одного отношения предшествования.

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