Теория и реализация языков программирования




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


Функцией переходов этого конечного автомата является функция переходов LR-анализатора.

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

.B?, a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод
S \Rightarrow^*_r yAax \Rightarrow_r y \alpha B \beta ax
, где z = y
. Предположим, что из ?ax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B
q имеется вывод
S \Rightarrow^*_r zBbw \Rightarrow_r zqbw
. Таким образом [B
.q, b] также допустима для z и ситуация [A
B.?, a] допустима для активного префикса zB. Здесь либо b может быть первым терминалом, выводимым из ?, либо из ? выводится e в выводе
\beta ax \Rightarrow^*_r bw
и тогда 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 можно добавить новое множество ситуаций);




Содержание  Назад  Вперед