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

Основной метод восходящего синтаксического анализа – перенос-свертка (ПС-анализ). Самый широкий класс грамматик, для которых успешно применяется ПС-анализаторы – это LR-грамматики. Достаточно удобный ПС-анализатора состоит в использовании стека для хранения символов грамматики и входного буфера для хранения анализируемой строки. Изначально стек пуст. Входной буфер содержит строку w. СА работает путем переноса нулей или нескольких символов в стек, до тех пор пока на вершине стека не окажется основа β, затем он свертывает β к левой части соответствующей продукции. Повторяет этот цикл пока не будет обнаружена ошибка или он не придет в конфигурацию, когда в стеке находится только стартовый символ, а буфер пуст, тогда сообщает об успешном разборе.

Пример:

Имеется цепочка: id₁+id₂*id₃

E→E+E

E→E*E

E→(E)

E→id

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

LR(k)-анализатор

L – сканирование входного потока слева направо

R – построение обращенных правых разборов, т.е. от листа в корень

k – число входных символов, которые могут быть просмотрены для принятия решения о способе проведения разбора. Если k=1 опущено, то считается, что k=1.

Алгоритм разбора для LR(0)-грамматики

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

Грамматическое вхождение – это символы полного словаря грамматики, снабженные двумя индексами (1 – правило грамматики, в правую часть которого входит данный символ; 2 – номер позиции в этой правой части).

Управляющая программа LR-анализатора функционирует так: она определяет S_m – текущее состояние на вершине стека (магазина) и a_i – текущий входной символ, затем обращается к функции action(S_m., a_i) ячейки таблицы управления, которя может иметь одно из 4 значений:

1) Перенос S (перенос S_i-значение пренос в i состояние);

2) Свертка в соответствие с продукцией;

3) Допуск (acc)ж

4) Ошибка (в таблице пустая клетка).

Кроме функции action в таблице используется функция go to – она получает в качестве аргумента состояние и символ грамматики и возвращает новое состояние, т.е. она представляет собой функцию переходов детерминированного конечного автомата, распознающего активные префиксы грамматики G.

Следующий шаг определяет текущий входной символ a_i и состояние S_m в соответствии с их значениями в таблице.

Пример:

Имеется грамматика:

1) E→E+T

2) E→T

3) T→T*P

4) T→P

5) P→(E)

6) P→id