Конструирование LR(1)-таблицы

Рассмотрим теперь алгоритм конструирования таблицы, управляющей LR(1)-анализатором.

Пусть G = (N, T, P, S) - КС-грамматика. Пополненной грамматикой для данной грамматики G называется КС-грамматика

т.е. эквивалентная грамматика, в которой введен новый начальный символ S' и новое правило вывода S' S.

Это дополнительное правило вводится для того, чтобы определить, когда анализатор должен остановить разбор и зафиксировать допуск входа. Таким образом, допуск имеет место тогда и только тогда, когда анализатор готов осуществить свертку по правилу S' S.

LR(1)-ситуацией называется пара [A . , a], где A - правило грамматики, a - терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

Будем говорить, что LR(1)-ситуация [A . , a] допустима для активного префикса , если существует вывод S _r^* Aw _r w, где = и либо a - первый символ w, либо w = e и a = $.

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

Пример 4.9. Рассмотрим грамматику G = ({S, B}, {a, b}, P, S) с правилами

	S BB
	B aB | b

Существует правосторонний вывод S _r^*aaBab _raaaBab. Легко видеть, что ситуация [B a.B, a] допустима для активного префикса = aaa, если в определении выше положить = aa, A = B, w = ab, = a, = B. Существует также правосторонний вывод S _r^*BaB _rBaaB. Поэтому для активного префикса Baa допустима ситуация [B a.B, $].

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

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

Рассмотрим ситуацию вида [A .B , a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S _r^*yAax _ry B ax, где z = y . Предположим, что из ax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B q имеется вывод S _r^*zBbw _rzqbw. Таким образом [B .q, b] также допустима для z и ситуация [A B. , a] допустима для активного префикса zB. Здесь либо b может быть первым терминалом, выводимым из , либо из выводится e в выводе ax _r^*bw и тогда b равно a. Т.е. b принадлежит FIRST( ax). Построение всех таких ситуаций для данного множества ситуаций, т.е. его замыкание, делает приведенная ниже функция closure.

Система множеств допустимых LR(1)-ситуаций для всевозможных активных префиксов пополненной грамматики называется канонической системой множеств допустимых LR(1)-ситуаций. Алгоритм построения канонической системы множеств приведен ниже.

Алгоритм 4.9. Конструирование канонической системы множеств допустимых LR(1)-ситуаций.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Каноническая система C множеств допустимых LR(1)-ситуаций для грамматики G.

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

function closure(I){ /* I - множество ситуаций */

do{

for (каждой ситуации [A .B , a] из I,

каждого правила вывода B из G',

каждого терминала b из FIRST( a),

такого, что [B . , b] нет в I)

добавить [B . , b] к I;

}

while (к I можно добавить новую ситуацию);

return I;

}

function goto(I,X){ /* I - множество ситуаций;

X - символ грамматики */

Пусть J = {[A X. , a] | [A .X , a] I};

return closure(J);

}

procedure items(G'){ /* G' - пополненная грамматика */

I₀ = closure({[S' .S, $]});

C = {I₀};

do{

for (каждого множества ситуаций I из системы C,

каждого символа грамматики X такого,

что goto(I, X) не пусто и не принадлежит C)

добавить goto(I, X) к системе C;

}

while (к C можно добавить новое множество ситуаций);

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

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

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

Алгоритм 4.10. Построение LR(1)-таблицы.

Вход. Каноническая система C = {I₀, I₁, ..., I_n} множеств допустимых LR(1)-ситуаций для грамматики G.

Выход. Функции Action и Goto, составляющие LR(1)-таблицу для грамматики G.

Метод. Для каждого состояния i функции Action[i, a] и Goto[i, X] строятся по множеству ситуаций I_i:

• Значения функции действия (Action) для состояния i определяются следующим образом:
• если [A .a , b] I_i (a - терминал) и goto(I_i, a) = I_j, то полагаем Action[i, a] = shift j;
• если [A ., a] I_i, причем A S', то полагаем Action[i, a] = reduce A ;
• если [S' S., $] I_i, то полагаем Action[i, $] = accept.
• Значения функции переходов для состояния i определяются следующим образом: если goto(I_i, A) = I_j, то Goto[i, A] = j (здесь A - нетерминал).
• Все входы в Action и Goto, не определенные шагами 2 и 3, полагаем равными error.
• Начальное состояние анализатора строится из множества, содержащего ситуацию [S' .S, $].

Таблица на основе функций Action и Goto, полученных в результате работы алгоритма 4.10, называется канонической LR(1)-таблицей. LR(1)-анализатор, работающий с этой таблицей, называется каноническим LR(1)-анализатором.

Пример 4.10. Рассмотрим следующую грамматику, являющуюся пополненной для грамматики из примера 4.8:

	(0) E' E
	(1) E E + T
	(2) E T
	(3) T T * F
	(4) T F
	(5) F id

Множества ситуаций и переходы по goto для этой грамматики приведены на рис. 4.11. LR(1)-таблица для этой грамматики приведена на рис. 4.9.

Рис. 4.11:

LR(1)-грамматики

Если для КС-грамматики G функция Action, полученная в результате работы алгоритма 4.10, не содержит неоднозначно определенных входов, то грамматика называется LR(1)-грамматикой.

Язык L называется LR(1)-языком, если он может быть порожден некоторой LR(1)-грамматикой.

Иногда используется другое определение LR(1)-грамматики. Грамматика называется LR(1), если из условий

1. S' _r^*uAw _ruvw,

2. S' _r^*zBx _ruvy,

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(1)-условие означает, что в FIRST(w) содержится информация, достаточная для определения того, что uv за один шаг выводится из uA. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики.

Можно доказать, что эти два определения эквивалентны.

Если грамматика не является LR(1), то анализатор типа сдвиг-свертка при анализе некоторой цепочки может достигнуть конфигурации, в которой он, зная содержимое магазина и следующий входной символ, не может решить, делать ли сдвиг или свертку (конфликт сдвиг/свертка), или не может решить, какую из нескольких сверток применить (конфликт свертка/свертка).

В частности, неоднозначная грамматика не может быть LR(1). Для доказательства рассмотрим два различных правых вывода

(1) S _ru_{1 r}... _ru_{n r}w, и

(2) S _rv_{1 r}... _rv_{m r}w.

Нетрудно заметить, что LR(1)-условие (согласно второму определению LR(1)-грамматики) нарушается для наименьшего из чисел i, для которых u_n-i v_m-i.

Пример 4.11. Рассмотрим вновь грамматику условных операторов:

	S if E then S | if E then S else S | a
	E b

Если анализатор типа сдвиг-свертка находится в конфигурации, такой что необработанная часть входной цепочки имеет вид else...$, а в магазине находится ...if E then S, то нельзя определить, является ли if E then S основой, вне зависимости от того, что лежит в магазине ниже. Это конфликт сдвиг/свертка. В зависимости от того, что следует на входе за else, правильной может быть свертка по S if E then S или сдвиг else, а затем разбор другого S и завершение основы if E then S else S. Таким образом нельзя сказать, нужно ли в этом случае делать сдвиг или свертку, так что грамматика не является LR(1).

Эта грамматика может быть преобразована к LR(1)-виду следующим образом:

	S M | U
	M if E then M else M | a
	U if E then S | if E then M else U
	E b

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

Справедливы также следующие утверждения [2].

Теорема 4.5. Каждый LR(1)-язык является детерминированным КС-языком.

Теорема 4.6. Если L - детерминированный КС-язык, то существует LR(1)-грамматика, порождающая L.