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




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


Если 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:

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

    1. если
      [A \rightarrow \alpha .a \beta , b] \in I_i
      (a - терминал) и goto(Ii, a)= Ij , то полагаем Action[i, a] = shift j;
    2. если
      [A \rightarrow \alpha; ., a] \in I_i
      , причем A
      S', то полагаем Action[i, a] = reduce A
      ;
    3. если
      [S' \rightarrow S., \$] \in I_i
      , то полагаем Action[i, $] = accept.

  2. Значения функции переходов для состояния i определяются следующим образом: если goto(Ii, A) = Ij , то Goto[i, A] = j (здесь A - нетерминал).
  3. Все входы в Action и Goto, не определенные шагами 2 и 3, полагаем равными error.
  4. Начальное состояние анализатора строится из множества, содержащего ситуацию [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.




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