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

      Комментарии к записи Конструирование lr(1)-таблицы отключены

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

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

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

т.е. эквивалентная грамматика, в которой введен новый начальный символ S’ и новое правило вывода S’ Конструирование lr(1)-таблицы S.

Это дополнительное правило вводится для того, чтобы определить, когда анализатор должен остановить разбор и зафиксировать допуск входа. Таким образом, допуск имеет место тогда и только тогда, когда анализатор готов осуществить свертку по правилу S’ Конструирование lr(1)-таблицы S.

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

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

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

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

S Конструирование lr(1)-таблицы BB
B Конструирование lr(1)-таблицы aB | b

Существует правосторонний вывод S Конструирование lr(1)-таблицы r*aaBab Конструирование lr(1)-таблицы raaaBab. Легко видеть, что ситуация [B Конструирование lr(1)-таблицы a.B, a] допустима для активного префикса Конструирование lr(1)-таблицы = aaa, если в определении выше положить Конструирование lr(1)-таблицы = aa, A = B, w = ab, Конструирование lr(1)-таблицы = a, Конструирование lr(1)-таблицы = B. Существует также правосторонний вывод S Конструирование lr(1)-таблицы r*BaB Конструирование lr(1)-таблицы rBaaB. Поэтому для активного префикса Baa допустима ситуация [B Конструирование lr(1)-таблицы a.B, $].

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

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

Рассмотрим ситуацию вида [A Конструирование lr(1)-таблицы Конструирование lr(1)-таблицы .B Конструирование lr(1)-таблицы , a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S Конструирование lr(1)-таблицы r*yAax Конструирование lr(1)-таблицы ry Конструирование lr(1)-таблицы B Конструирование lr(1)-таблицы ax, где z = y Конструирование lr(1)-таблицы . Предположим, что из Конструирование lr(1)-таблицы ax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B Конструирование lr(1)-таблицы q имеется вывод S Конструирование lr(1)-таблицы r*zBbw Конструирование lr(1)-таблицы rzqbw. Таким образом [B Конструирование lr(1)-таблицы .q, b] также допустима для z и ситуация [A Конструирование lr(1)-таблицы Конструирование lr(1)-таблицы B. Конструирование lr(1)-таблицы , a] допустима для активного префикса zB. Здесь либо b может быть первым терминалом, выводимым из Конструирование lr(1)-таблицы , либо из Конструирование lr(1)-таблицы выводится e в выводе Конструирование lr(1)-таблицы ax Конструирование lr(1)-таблицы r*bw и тогда b равно a. Т.е. b принадлежит FIRST( Конструирование lr(1)-таблицы 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 Конструирование lr(1)-таблицы Конструирование lr(1)-таблицы .B Конструирование lr(1)-таблицы , a] из I,

каждого правила вывода B Конструирование lr(1)-таблицы Конструирование lr(1)-таблицы из G’,

каждого терминала b из FIRST( Конструирование lr(1)-таблицы a),

такого, что [B Конструирование lr(1)-таблицы . Конструирование lr(1)-таблицы , b] нет в I)

добавить [B Конструирование lr(1)-таблицы . Конструирование lr(1)-таблицы , b] к I;

}

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

return I;

}

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

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

Пусть J = {[A Конструирование lr(1)-таблицы Конструирование lr(1)-таблицы X. Конструирование lr(1)-таблицы , a] | [A Конструирование lr(1)-таблицы Конструирование lr(1)-таблицы .X Конструирование lr(1)-таблицы , a] Конструирование lr(1)-таблицы I};

return closure(J);

}

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

I0 = closure({[S’ Конструирование lr(1)-таблицы .S, $]});

C = {I0};

do{

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

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

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

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

}

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

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

Работа алгоритма построения системы C множеств допустимых LR(1)-ситуаций начинается с того, что в C помещается начальное множество ситуаций I0 = closure({[S’ Конструирование lr(1)-таблицы .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 Конструирование lr(1)-таблицы Конструирование lr(1)-таблицы .a Конструирование lr(1)-таблицы , b] Конструирование lr(1)-таблицы Ii (a — терминал) и goto(Ii, a) = Ij, то полагаем Action[i, a] = shift j;
  • если [A Конструирование lr(1)-таблицы Конструирование lr(1)-таблицы ., a] Конструирование lr(1)-таблицы Ii, причем A Конструирование lr(1)-таблицы S’, то полагаем Action[i, a] = reduce A Конструирование lr(1)-таблицы Конструирование lr(1)-таблицы ;
  • если [S’ Конструирование lr(1)-таблицы S., $] Конструирование lr(1)-таблицы Ii, то полагаем Action[i, $] = accept.
  • Значения функции переходов для состояния i определяются следующим образом: если goto(Ii, A) = Ij, то Goto[i, A] = j (здесь A — нетерминал).
  • Все входы в Action и Goto, не определенные шагами 2 и 3, полагаем равными error.
  • Начальное состояние анализатора строится из множества, содержащего ситуацию [S’ Конструирование lr(1)-таблицы .S, $].
  • Таблица на основе функций Action и Goto, полученных в результате работы алгоритма 4.10, называется канонической LR(1)-таблицей. LR(1)-анализатор, работающий с этой таблицей, называется каноническим LR(1)-анализатором.

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

    (0) E’ Конструирование lr(1)-таблицы E
    (1) E Конструирование lr(1)-таблицы E + T
    (2) E Конструирование lr(1)-таблицы T
    (3) T Конструирование lr(1)-таблицы T * F
    (4) T Конструирование lr(1)-таблицы F
    (5) F Конструирование lr(1)-таблицы id

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

    Конструирование lr(1)-таблицы
    Рис. 4.11:

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

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

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

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

    1. S’ Конструирование lr(1)-таблицы r*uAw Конструирование lr(1)-таблицы ruvw,

    2. S’ Конструирование lr(1)-таблицы r*zBx Конструирование lr(1)-таблицы ruvy,

    3. FIRST(w) = FIRST(y)

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

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

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

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

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

    (1) S Конструирование lr(1)-таблицы ru1 Конструирование lr(1)-таблицы r… Конструирование lr(1)-таблицы run Конструирование lr(1)-таблицы rw, и

    (2) S Конструирование lr(1)-таблицы rv1 Конструирование lr(1)-таблицы r… Конструирование lr(1)-таблицы rvm Конструирование lr(1)-таблицы rw.

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

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

    S Конструирование lr(1)-таблицы if E then S | if E then S else S | a
    E Конструирование lr(1)-таблицы b

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

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

    S Конструирование lr(1)-таблицы M | U
    M Конструирование lr(1)-таблицы if E then M else M | a
    U Конструирование lr(1)-таблицы if E then S | if E then M else U
    E Конструирование lr(1)-таблицы b

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

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

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

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

    Дополнительные материалы:

    LR(1) & LALR(1) Parsing Automaton


    Похожие статьи: