Лекции по конструированию компиляторов. В.А. Серебряков (1134687), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

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-анализа.

while (true)
{Пусть S - состояние на верхушке магазина;
if (action[S,InSym]==“shift S'“)
{поместить InSym и затем S' на верхушку
магазина;
прочитать в InSym следующий входной символ;
}
else if (action[S,InSym]==“reduce N->w”)
{удалить из магазина 2*|w| символов;
пусть теперь на верхушке магазина состояние S';
поместить на верхушку магазина N, а
затем состояние goto[S',N];
вывести правило N->w;
}
else if (action[S,InSym]==“accept”)
{result(“success”);
break;
}
else {result(error());
break;
}
}

Вначале в магазине помещено начальное состояние S₀, а в буфере w$, InSym содержит первый символ w$; Анализатор выполняет приведенную программу до тех пор, пока будет достигнуто либо состояние accept, либо состояние error.

Пример 3.6. На рис. 3.16 изображены функции action и goto LR-таблиц для грамматики арифметических выражений с бинарными операциями + и * примера 3.5. Здесь S_i означает сдвиг и помещение в магазин состояния i, R_j - свертку по правилу номер j, acc - допуск, пустая клетка - ошибку.

На входе id+id*id последовательность состояний магазина и входа показаны на рис. 3.17. Например, в первой строке LR-анализатор находится в нулевом состоянии и читает первый входной символ id. Действие S6 в нулевой строке и столбце id в поле action рис. 3.17 означает сдвиг и помещение S6 на верхушку магазина. Это и изображено во второй строке: первый символ id и символ состояния S6 помещаются в магазин и id удаляется из входной строки.

Состо- action goto
яния
id + * $ E T F

0 S6 1 2 3
1 S4 acc
2 R2 S7 R2
3 R4 R4 R4
4 S6 5 3
5 R1 S7 R1
6 R5 R5 R5
7 S6 8
8 R3 R3 R3

Рис. 3.16

Активный Магазин Вход Действие
префикс

0 id + id * id $ сдвиг
id 0 id 6 + id * id $ F -> id
F 0 F 3 + id * id $ T -> F
T 0 T 2 + id * id $ E -> T
E 0 E 1 + id * id $ сдвиг
E+ 0 E 1 + 4 id * id $ сдвиг
E+id 0 E 1 + 4 id 6 * id $ F -> id
E+F 0 E 1 + 4 F 3 * id $ T -> F
E+T 0 E 1 + 4 T 5 id $ сдвиг
E+T* 0 E 1 + 4 T 5 * 7 id $ сдвиг
E+T*id 0 E 1 + 4 T 5 * 7 id 6 $ F -> id
E+T*F 0 E 1 + 4 T 5 * 7 F 8 $ T -> T*F
E+T 0 E 1 + 4 T 5 $ E -> E+T
E 0 E 1 допуск

Рис. 3.17

Текущим входным символом становится +, и действием в состоянии 6 на вход + является свертка по F->id. Из магазина удаляются два символа (один символ состояния и один символ грамматики). Теперь анализируется нулевое состояние Поскольку goto в нулевом состоянии по символу F - это 3, F и 3 помещаются в магазин. Теперь имеем конфигурацию, соответствующую третьей строке. Остальные шаги определяются аналогично.

3.3.3. LR-грамматики

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

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

Для принятия решения о сдвиге или свертке анализатор просматривает очередные k входных символов. Практический интерес представляют случаи k=0 и k=1. Например, в таблице действий рис. 3.16 используется один символ. Грамматика, которая может быть проанализирована LR анализатором, заглядывая на k входных символов на каждом шаге, называется LR(k)-грамматикой.

Можно дать другое определение LR(k)-грамматики. Пополненной грамматикой для данной грамматики G называется КС-грамматика, в которой введена новая аксиома S' и правило вывода S'->S. Это дополнительное правило вводится для того, чтобы определить, когда анализатор должен остановить разбор и зафиксировать допуск входа. Таким образом допуск имеет место тогда и только тогда, когда анализатор осуществляет свертку по правилу S'->S. Пополненная грамматика называется LR(k) для k>=0, если из условий

(1) S' =>* uAw => uvw,
(2) S' =>* zBx => uvy,
(3) FIRST(w)=FIRST(y)

следует, что uAy=zBx (т.е. u=z, A=B и x=y).

Согласно этому определению, если uvw и uvy - правовыводимые цепочки пополненной грамматики, у которых FIRST(w)=FIRST(y) и A->v - последнее правило, использованное в правом выводе цепочки uvw, то правило A->v должно применяться и в правом разборе при свертке uvy к uAy. Так как A дает v независимо от w, то LR(k) условие означает, что в FIRST(w) содержится информация, достаточная для определения того, что uv за один шаг выводится из uA. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики. Кроме того, для LR(k) грамматики известно, когда допускается входная цепочка.

Основная разница между LL- и LR-грамматиками заключается в следующем. Чтобы грамматика была LR(k), необходимо распознавать вхождение правой части правила вывода, просмотрев все, что выведено из этой правой части и заглянув на k входных символов вперед. Это требование существенно менее строгое, чем требование для LL(k) грамматики, когда необходимо определить применимое правило, видя только первые k символов, выводимых из его правой части. Класс LL-грамматик является собственным подклассом LR. Рассмотрим теперь конструирование таблиц LR-анализатора.

LR(1) ситуацией называется пара [A->u.v,a], где A->uv - правило грамматики, а a - терминал или правый концевой маркер $. "1" указывает на длину второй компоненты ситуации, которая называется аванцепочкой ситуации. Аванцепочка не играет роли в ситуациях вида [A->u.v,a], где v не равно e, но ситуация вида [A->u.,a] ведет к свертке по правилу A->u только если следующим входным символом является a. Таким образом свертка по правилу A->u требуется только для тех входных символов a, для которых [A->u.,a] является LR(1) ситуацией в состоянии на верхушке магазина.

Будем говорить, что LR(1)-ситуация [A->u.v,a] допустима для активного префикса z, если существует вывод S=>*yAw=>yuvw, где z=yu и либо a - первый символ w, либо w равно e и a равно $ (рис. 3.18).

Характеристики

Список файлов лекций