LR17 (Материалы к контрольным работам)

3.3. Разбор снизу-вверх типа сдвиг-свертка

3.3.1. Основа

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

S S S
/ | \
X1 X2...
/ |
............
/ |
Y Y |
/|\ /|\ Z
/ ... / ... /|\
a.........$ a...........$ a.......b.......$

а) б) в)

Рис. 3.13

Пример 3.5. Рассмотрим грамматику арифметических выражений, приведенную на рис. 3.14 а). Строка а+b*c может быть сведена к S, как показано на рис. 3.14.б). Дерево этой строки приведено на рис. 3.14 в).

В строке a+b*c ищется подстрока, которую можно сопоставить с правой частью некоторого правила вывода. Этому удовлетворяют подстроки a, b и c. Если выбрать самое левое a и заменить его на F - левую часть правила F->id, то получим строку F+b*c. Теперь правой части того же правила можно сопоставить подстроки b и c. Эти свертки представляют собой в обратном порядке правосторонний вывод:

E->E+T->E+T*F->E+T*c->E+F*c->E+b*c->T+b*c->F+b*c->a+b*c

E -> E + T а+b*c E
E -> T F+b*c /+\
T -> T*F T+b*c E T
T -> F E+b*c | |\
F -> id E+F*c T T *
E+T*c | | \
E+T*F F F F
E+T | | \
E id id id
| | |
a b c

а) б) в)
Рис. 3.14

Подстрока сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется основой строки. В приведенном выше выводе основы выделены. Самая левая подстрока, которая сопоставляется правой части некоторого правила вывода A->v, не обязательно является основой, поскольку свертка по правилу A->v может дать строку, которая не может быть сведена к аксиоме. Если, скажем, в примере 3.5 заменить a на F и b на F, то получим строку F+F*c, которая не может быть сведена к S.

Формально, основа правой сентенциальной формы z - это правило вывода A->v и позиция в z, в которой может быть найдена строка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S=>*uAw=>uvw, то A->v в позиции, следующей за u, это основа строки uvw. Строка w справа от основы содержит только терминальные символы. Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод uvw и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с разбираемой строки w. Если w - слово в рассматриваемой грамматике, то w=Z_n, n-я правая сентенциальная форма еще неизвестного правого вывода

S = Z₀ => Z₁ => Z₂ => ... => Z_n-1 => Z_n =w.

Чтобы восстановить этот вывод в обратном порядке, выделяем основу V_n в Z_n и заменяем V_n на левую часть некоторого правила вывода A_n -> V_n, получая (n-1)-ю правую сентенциальную форму Z_n-1. Затем повторяем этот процесс, т.е. выделяем основу V_n-1 в Z_n-1 и сворачиваем эту основу, получая правую сентенциальную форму Z_n-2. Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый вывод входной строки.

Таким образом, главная задача анализатора типа сдвиг-свертка - это выделение и отсечение основы.

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

В названии LR(k) символ L означает, что разбор осуществляется слева-направо, R - что строится правый вывод в обратном порядке, k - число входных символов, на которые заглядывает вперед анализатор при разборе. Когда k опущено, имеют в виду 1.

LR-анализ привлекателен по нескольким причинам:

- LR-анализ - наиболее мощный метод анализа без возвратов типа сдвиг-свертка;

- LR-анализ может быть реализован довольно эффективно;

- практически LR-анализаторы могут быть построены для всех конструкций языков программирования;

• класс грамматик, которые могут быть проанализированы LR-методом, строго включает класс грамматик, которые могут быть анализированы предсказывающими анализаторами (сверху вниз типа LL).

Схематически структура LR-анализатора изображена на рис. 3.15. Он состоит из входа, выхода, магазина, управляющей программы и таблицы анализа, которая имеет две части - действий и переходов. Управляющая программа одна и та же для всех анализаторов, разные анализаторы различаются таблицами анализа. Программа анализатора читает символы из входного буфера по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида S₀X₁S₁X₂S₂...X_mS_m (S_m - верхушка магазина). Каждый X_i - символ грамматики (терминальный или нетерминальный), а S_i - символ, называемый состоянием. Каждый символ состояния выражает информацию, содержащуюся в магазине ниже него, а комбинация символа состояния на верхушке магазина и текущего входного символа используется для индексации таблицы анализа и определяет решение о сдвиге или свертке. В реализации символы состояния не обязательно должны размещаться в магазине. Однако их использование удобно для упрощения понимания поведения LR-анализатора.

Вход a₁ . . . a_i . . . a_n $



Выход
Магазин S_m LR
анализатор
X_m

S_m-1

X_m-1

....
action goto
S₀


Рис. 3.15

Таблица анализа состоит из двух частей: действия (action) и переходов (goto). Начальное состояние этого ДКА - это состояние, помещенное на верхушку магазина LR-анализатора в начале работы.

Конфигурация-LR анализатора - это пара, первая компонента которой - содержимое магазина, а вторая - непросмотренный вход:

(S0 X1 S1 X2 S2 ... Xm Sm, ai ai+1 ... an $)

Эта конфигурация соответствует правой сентенциальной форме

X₁ X₂ ... X_m a_i a_i+1 ... a_n

Префиксы правых сентенциальных форм, которые могут появиться в магазине анализатора, называются активными префиксами. Основа сентенциальной формы всегда располагается на верхушке магазина. Таким образом, активный префикс - это такой префикс правой сентенциальной формы, который не переходит правую границу основы этой формы.

Очередной шаг анализатора определяется текущим входным символом a_i и символом состояния на верхушке магазина S_m. Элемент таблицы действий action[S_m,a_i] для состояния S_m и входа a_i, может иметь одно их четырех значений:

1) shift S, сдвиг, где S - состояние,

2) reduce A->w, свертка по правилу грамматики A -> w,

3) accept, допуск,

4) error, ошибка.

Конфигурации, получающиеся после каждого из четырех типов шагов, следующие

1. Если action[S_m,a_i]=shift S, то анализатор выполняет шаг сдвига, переходя в конфигурацию

(S₀ X₁ S₁ X₂ S₂ ... X_m S_m a_i S, a_i+1 ... a_n $)

В магазин помещаются как входной символ a_i, так и следующее состояние S, определяемое action[S_m,a_i]. Текущим входным символом становится a_i+1.

2. Если action[S_m,a_i]=reduce A->w, то анализатор выполняет свертку, переходя в конфигурацию

(S₀ X₁ S₁ X₂ S₂ ... X_m-r S_m-r A S, a_i a_i+1 ... a_n $)

где S=goto[S_m-r,A] и r - длина w, правой части правила вывода. Функция goto таблицы анализа, построенная по грамматике G, - это функция переходов детерминированного конечного автомата, распознающего активные префиксы G. Анализатор сначала удаляет из магазина 2r символов (r символов состояния и r символов грамматики), так что на верхушке оказывается состояние S_m-r. Затем анализатор помещает в магазин как A - левую часть правила вывода, так и S - содержимое таблицы goto[S_m-r,A]. На шаге свертки текущий входной символ не меняется. Для LR-анализаторов X_m-r+1 ... X_m - последовательность символов грамматики, удаляемых из магазина, всегда соответствует w - правой части правила вывода, по которому делается свертка.

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

3. Если action[S_m,a_i]=accept, то разбор завершен.

4. Если action[S_m,a_i]=error, анализатор обнаружил ошибку, то выполняются действия по диагностике и восстановлению.

Ниже приведен алгоритм LR-анализа. Все LR-анализаторы ведут себя одинаково. Разница между ними заключается в различном содержании таблиц действий и переходов.

Алгоритм 3.7. Алгоритм LR-анализа.