Автомат для грамматики

Для определенной нами грамматики автомат получится следующим:

x

x S

S (x (

,

S L

)

где состояния определяются следующим образом:

0: {[S'.S], [S →. x], [S →. (L)]}

1: {[S → x.]}

2: {[S → (.L)], [L →. L,S], [L →. S], [S →. (L)], [S →. x]}

3: {[S' → S.]

4: {[S → (L.)], [L → L., S]}

5: {[S → (L).]}

6: {[L → S.]}

7: {[L → L,.S], [S →. (L)], [S →. x]}

8: {[L → L,S.]}

Управляющая таблица

Теперь мы можем вычислить множество сверток R:

R = empty set;

for (each state I in T)

{

for (each item [A->w.] in I)

{

R+={(I, A->w)};

}

}

Таким образом, алгоритм построения управляющей таблицы автомата состоит из следующих шагов:

· Пополнение грамматики

· Построение множества состояний

· Построение множества переходов

· Построение множества сверток

Для того, чтобы построить таблицу анализатора для грамматики, поступим следующим образом:

1. для каждого ребра I→^X J мы поместим в позицию [ I, X ] таблицы

· shift J, если X – терминал,

· goto J, если X – нетерминал.

2. для каждого состояния I, содержащего ситуацию [ S'→S. ] мы поместим accept в позицию [ I, $ ]

3. для состояния, содержащего ситуацию [ A→w. ] (правило номер n с точкой в конце правила), поместим reduce n в позицию [ I, Y ] для каждого терминала Y.

4. пустая ячейка означает ошибочную ситуацию

Приведем управляющую таблицу для грамматики G₀:

LR(1)-анализатор

LR(1)-анализатор использует для принятия решения один символ входной цепочки. Алгоритм построения управляющей таблицы LR(1)-анализатора подобен уже рассмотренному алгоритму для LR (0)-анализатора, но понятие ситуации в LR(1)-анализаторе более сложное: LR(1)-ситуация состоит из правила грамматики, позиции правой части (представляемой точкой) и одного символа входной строки (lookahead symbol). LR(1)-ситуация выглядит следующим образом: [ A→w₁. w₂, a ], где a – терминальный символ. Ситуация [ A→w₁ .w₂, a ] означает, что цепочка w₁ находится на вершине магазина, и префикс входной цепочки выводим из цепочки w₂ x. Как и прежде, состояние автомата определяется множеством ситуаций. Для построения управляющей таблицы необходимо переопределить базовые операции closure и goto.

closure (I) {

do {

I_old=I;

for (каждой ситуации [A->w₁.Xw₂, z] из I)

for (любого правила X->u)

for (любой цепочки w, принадлежащей FIRST (w₂ z))

I+=[X->.u, w];

} while (I!= I_old);

return I;

}

goto (I, X) {

J = {};

for (каждой ситуации [A->w₁.Xw₂, z] из I)

J+=[A->w₁ X.w₂, z];

return closure (J);

}

Естественно, операция reduce также зависит от символа входной цепочки:

R=[]

foreach (I из T)

foreach ([A->w., z] из I)

R+={(I, z, A->w)}

Тройка (I, z, A→w) означает, что в состоянии I для символа z входной цепочки анализатор будет осуществлять свертку по правилу A→w.

Управляющая таблица LR(1)-анализатора

Пример. Рассмотрим грамматику:

(1) E → T

(2) E → T

(3) T → T*F

(4) T → F

(5) F → (E)

(6) F → id

Управляющая таблица для такой грамматики выглядит следующим образом:

Как обычно,

si – перенос и переход в состояние i

ri – свертка по правилу i

i – переход в состояние i

LALR(1)-анализатор

Таблицы LR(1)-анализатора могут оказаться очень большими, ведь даже маленькая грамматика нашего примера привела к автомату с двенадцатью состояниями. Таблицы меньшего размера можно получить путем слияния любых двух состояний, которые совпадают с точностью до символов входной строки (lookahead symbols).

Пример. Рассмотрим грамматику G₁ с правилами:

S → AA

A → aA

A → b

Пополним эту грамматику правилом S' → S.

Для этой грамматики мы получим следующие состояния:

0: { [S'→.S, $], [S→.AA, $], [A→.aA, a], [A→.aA, b], [A→.b, a], [A→.b, b] }

1: { [S'→S., $] }

2: { [S'→A.A, $], A→.aA, $], [A→.b, $] }

3: { [A→a.A, a], [A→a.A, b], [A→.a.A, a], [A→.a.A, b], [A→.b, a], [A→.b, b] }

4: { [A→b., a], [A→b., b] }

5: { [S→AA. $] }

6: { [A→a.A, $], [A→.aA, $], [A→.b, $] }

7: { [A→b., $] }

8: { [A→aA.,a], [A→aA.,b] }

9: { [A→aA.,$] }

Граф переходов выглядит так:

Таблица LALR-анализатора для грамматики G₁

Теперь можно построить таблицу LR-анализатора:

Нетрудно заметить, что пары состояний 3 и 6, 4 и 7, 8 и 9 различаются только вторыми компонентами, определяющих их ситуаций. Поэтому мы можем «склеить» эти пары. В результате получится таблица LALR-анализатора: