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

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

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

Рис. 4.7.

Рис. 4.8.

грамматика

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

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

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

.?, a], где A

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

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

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

, где + = ?

и либо a - первый символ w, либо w = e и a = $.

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

Пример 4.11. Дана грамматика G = ({S, B}, {a, b}, P, S) с правилами

aB | b

Существует правосторонний вывод

. Легко видеть, что ситуация [B

a.B, a] допустима для активного префикса + = aaa, если в определении выше положить ? = aa, A = B, w = ab,

= a, ? = B. Существует также правосторонний вывод

. Поэтому для активного префикса Baa допустима ситуация [B

a.B, $].

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

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

Чтобы не просматривать магазин на каждом шаге анализа, на верхушке магазина всегда хранится то состояние, в котором должен оказаться этот конечный автомат после того, как он прочитал символы грамматики в магазине от дна к верхушке. Рассмотрим ситуацию вида [A

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

, где z = y

. Предположим, что из ?ax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B

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

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

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

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

и тогда b равно a. То есть b принадлежит FIRST(? ax). Построение всех таких ситуаций для данного множества ситуаций, то есть его замыкание, делает приведенная ниже функция closure.

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

Алгоритм 4.10. Конструирование канонической системы множеств допустимых 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] \in I}; return closure(J); }

procedure items(G'){ /* G' - пополненная грамматика */ I' = 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.11. Построение LR(1)-таблицы.

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

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

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

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

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

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

(0) E'

E

(1) E

E + T

(2) E

T

(3) T

T * F

(4) T

F

(5) F

id.

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

Проследим последовательность создания этих множеств более подробно.

Вычисляем I0 = closure({[E'
.E, $]}).
1. Ситуация [E'
  .E, $] попадает в него по умолчанию как исходная.
2. Если обратиться к обозначениям функции closure, то для нее
  
  Значит, для терминала $ добавляем ситуации на основе правил со знаком E в левой части правила. Это правила
  
  и соответствующие им ситуации
3. Просматриваем получившиеся ситуации. Для ситуации [E
  .E + T, $] ? = +, поэтому first(?a) = first(+$) = {+}. На основе этого добавляем к I0
  
  [E
  E + .T, +] и [E
  .T, +].
4. Для ситуации [E
  .T, $] ? = e, first(?a) = {$}. Поэтому добавляем к I0
  
  [T
  . T * F, $] и [T
  .F, $].
5. Подобно этому для ситуации [E
  .T, +] ? = e, first(?a) = {+}. Поэтому добавляем к I0
  
  [T
  .T * F, +] и [T
  .F, +].
6. Из ситуации [T
  . T * F, +] ? = *, first(?a) = {*}: Поэтому добавляем к I0
  
  увеличить изображение
  Рис. 4.9.
  
  [T
  .T * F, *] и [T
  .F, *]
7. Далее из ситуации [T
  .F, *] получаем ситуацию [F
  . id, *]. из ситуации [T
  . F, $] - ситуацию [F
  . id, $], а из ситуации [T
  . F, +] - [F
  . id, *].

Таким образом, все 14 искомых ситуаций I0 получены.

Возвращаемся в головную функцию items, включаем I0 в множество C и исследуем непустые итоги применения функции goto(I0; X), где

.

Если посмотреть на вид правил в функции goto(I0; X), то видно, что X должен встретиться в правой части хотя бы одного правила. Для E0 таких правил у нас нет, поэтому значение функции goto(I0, E') пусто.

Возьм_м goto(I0; E). E встречается после точки в правых частях двух ситуаций из I0, значит бер_м эти два правила и переносим в них точки на один символ вправо (пока есть куда - не уперлись в запятую), получаем:

[E'

E., $]

и

[E

E. + T, $|+]

Вычислим от каждой из этих ситуаций функцию closure. Но, поскольку справа от точки здесь либо пустая цепочка, либо терминал, то никаких новых ситуаций не возникает. Дальше отслеживаем, может ли куда-то сдвинуться точка дальше на право и по какому символу. Если может, строим соответствующее множество (рис. 4.9). И т.д.

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