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

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).

Будем говорить, что ситуация допустима, если она допустима для какого-либо активного префикса.

Пример 3.7. Рассмотрим грамматику

S -> BB
B -> aB | b

Существует правосторонний вывод S=>*aaBab=>aaaBab. Ситуация [B->a.B,a] допустима для активного префикса z=aaa, если в определении выше положить y=aa, A=B, w=ab, u=a, v=B. Существует также правосторонний вывод S*=>BaB=>BaaB. Из этого вывода видно, что для активного префикса Baa допустима ситуация [B->a.B,$].

S


A


y u v a...

z w
Магазин Непрочитанная часть
входной цепочки

Рис. 3.18

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

Для конструирования набора множеств допустимых LR(1)-ситуаций будут применяться пополненная грамматика G' и процедуры-функции closure и goto.

Рассмотрим ситуацию вида [A->u.Bv,a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S=>*yAax=>yuBvax, где z=yu. Предположим, что из vax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B->q имеется вывод S=>*zBbw=>zqbw. Таким образом [B->.q,b] также допустима для z и ситуация [A->uB.v,a] допустима для активного префикса zB. Здесь либо b может быть первым терминалом, выводимым из v, либо из v выводится e в выводе vax=>*bw и тогда b равно a. Т.е. b принадлежит FIRST(vax). Построение всех таких ситуаций для данного множества ситуаций, т.е. его замыкание, делает функция closure.

S S


y A ax y A ax


u B v u B v

z bw zB
.q
Рис. 3.13

Aлгоритм построения множеств LR(1)-ситуаций приведен ниже.

Алгоритм 3.8. Конструирование множеств LR(1)-ситуаций.

Алгоритм заключается в выполнении главной программы items, которая вызывает функции closure и goto.

SetOfItems closure(SetOfItems I)/*I - множество ситуаций*/
{do
{for (каждой ситуации [A->u.Bv,a] из I,
каждого правила вывода B->w из G',
каждого терминала b из FIRST(va),
такого, что [B->.w,b] нет в I
)
добавить [B->.w,b] к I;
}
while (к I можно добавить новые ситуации);
return I;
}

В анализаторах типа LR(0) при построении closure не учитываются терминалы из FIRST(va).

Если I - множество ситуаций, допустимых для некоторого активного префикса z, то goto(I,X) - множество ситуаций, допустимых для активного префикса zX.

SetOfItems goto(SetOfItems I,Symbol X)/*I - множество ситуаций;
X - символ грамматики*/
{ Пусть [A->u.Xv,a] принадлежит I;
Рассмотрим J - множество всех ситуаций вида
{[A-uX.v,a]};
return closure(J)
}

Работа алгоритма построения множества LR(1)-ситуаций начинается с того, что берется C - множество ситуаций {closure({[S'->.S,$]})}. Затем из имеющегося множества с помощью операции goto() строятся новые множества ситуаций. По-существу, goto(I,X) - переход конечного автомата из состояния I по символу X.

void items(Grammar G')
{ do
{C={closure({[S'->.S,$]})};
for (каждого множества ситуаций I из C,
каждого символа грамматики X такого,
что goto(I,X) не пусто и не принадлежит C
)
добавить goto(I,X) к C;
}
while (к C можно добавить множество ситуаций);
}

Пример 3.8. Рассмотрим пополненную грамматику примера 3.5.

E'-> E
1) E -> E + T
2) E -> T
3) T -> T * F
4) T -> F
5) F -> id

Множество ситуаций и переходов для этой грамматики приведены на рис. 3.19.

В каждый момент анализа в магазине находится активный префикс, который соответствует последовательности переходов из начального состояния (I₀) в текущее. Свертка - это замена суффикса префикса и переход в новое состояние, которое определяется из таблицы goto по символу левой части свернутого правила и предыдущему символу магазина, который соответствует состоянию после разбора префикса. Для определения этого нового состояния на верхушке хранится состояние, соответствующее активному префиксу без этого суффикса. Новое состояние определяется как goto[предыдущее состояние, новый нетерминал].

Рассмотрим теперь, как по множеству LR(1)-ситуаций строятся функции действия и переходов LR(1)-анализатора. Функции действия и переходов представляются таблицей.