Лекция 13

Восходящий синтаксический анализ. Создание таблицы синтаксического анализа. Особенности LR-анализа.

Восходящий разбор.

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

Пример:

Есть КС-грамматика G с правилами

1. (3)

2. (4)

Цепочка: ω = ((a)(((b)a(a))(b)))

Сделаем левый разбор цепочки:

1. Выделим основу: ((a)(((b)a(a))(b))) по (4) правилу КС-грамматики;

2. Заменяем: (A(((b)a(a))(b))) по (2) правилу КС-грамматики;

3. (A((Sa(a))(b))) по (4) правилу КС-грамматики;

4. (A((SaA)(b))) по (3) правилу КС-грамматики;

5. (A(A(b))) по (2) правилу КС-грамматики;

6. (A(AS)) по (1) правилу КС-грамматики;

7. (AS) по (1) правилу КС-грамматики;

8. S по (1) правилу КС-грамматики.

Определим восходящий анализатор:

Пусть G – некоторая КС-грамматика. Назовём правым анализатором расширенный недетерминированный МП-преобразователь:

δ определяется следующим образом:

1. если – это правило изP с номером i, то ;

2. ;

3. 

Правый анализатор работает следующим образом:

1. переносит входные символы в магазин, используя функцию , построенную по правилу (2) определения;

2. когда наверху магазина появляется основа, анализатор может свернуть её, используя функцию , построенную по правилу (1) определения, и выдать номер правила грамматики, использованного при свёртке;

3. анализатор продолжает переносить в магазин входные символы до тех пор, пока в его верхней части не появится новая основа, которая свёртывается, после чего на выход подаётся номер соответствующего правила грамматики;

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

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

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

Пример:

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

E→E+E

E→E*E

E→(E)

E→id

СТЕК	ВХОД	ДЕЙСТВИЕ
⊥	id1+id2*id3	перенос
⊥id1	+id2*id3	свертка E→id
⊥E	+id2*id3	перенос
⊥E+	id2*id3	перенос
⊥E+id2	*id3	свертка E→id
⊥E+E	*id3	перенос
...........	..........	...........
⊥E	⊥	Допуск

Существуют КС-грамматики, для которых ПС-анализ не применим, т.к. можно достичь , в которой нельзя определить какая из возможных сверток должна применяться, поэтому данный метод используется для 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