Синтаксический анализ приоритета операторов

Конфликты в процессе ПС-анализа

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

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

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

Задача состоит в том, чтобы определить эти отношения предшествования между символами грамматики. При этом грамматика может быть отнесена к одному из классов грамматик предшествования (простого предшествования, расширенного предшествования, слабого предшествования и т.д.).

Основное понятие, которое используется в грамматиках предшествования – отношение предшествования.

Пусть имеется КС-грамматика и на некотором шаге вывода получена сентенциальная форма вида ξ^* ξ_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^*.

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

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

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

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

Если между символами ξ_i и ξ_j выполняется не более одного отношения предшествования, можно выделить основу для выполнения свертки.

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