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

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

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

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

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

только тогда, когда анализатор готов осуществить свертку по правилу S'

LR(1)-ситуацией называется пара [A

, a], где A

- правило грамматики, a - терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

Будем говорить, что LR(1)-ситуация [A

, a] допустима для активного префикса

, если существует вывод S

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

, a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S

r*yAax

ax, где z = y

. Предположим, что из

ax выводится

терминальная строка bw. Тогда для некоторого правила вывода вида B

q имеется вывод S

r*zBbw

rzqbw. Таким образом [B

.q, b] также допустима для z и ситуация [A

, a] допустима для активного префикса zB. Здесь либо b может быть первым терминалом, выводимым из

, либо из

выводится e в выводе

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

, 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

, a] | [A

, a]

I};

return closure(J);

}

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

I0 = closure({[S'

.S, $]});

C = {I0};

do{

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

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

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

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

}

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

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

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

X.

Работа алгоритма построения системы C множеств допустимых

LR(1)-ситуаций начинается с того, что в C помещается начальное множество ситуаций I0 = closure({[S'

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

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

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

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

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

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

Значения функции действия (Action) для состояния i определяются следующим образом:
если [A

.a
, b]
Ii (a - терминал) и goto(Ii, a) = Ij, то полагаем Action[i, a] = shift j;

если [A

., a]
Ii, причем A
S', то полагаем Action[i, a] = reduce A

;

если [S'
S., $]
Ii, то полагаем Action[i, $] = accept.

Значения функции переходов для

состояния i определяются следующим образом: если goto(Ii, A) = Ij, то 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:

Содержание раздела