Преобразование таблицы конфигураций в управляющую таблицу, страница 3

Mпосл( L) = { „ }

Mпосл( E) = { =, „ }

Mпосл( R) = { =, „ }


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

0

1

2

3

4

5

6

L

R

E

i

=

*

„

0

G(1)

G(3)

G(2)

S(5)

S(4)

1

Stop

2

S(6)

R(1,1)

3

R(1,0)

4

G(7)

G(8)

S(5)

S(4)

5

R(1,2)

R(1,2)

6

G(9)

G(8)

S(5)

S(4)

7

R(2,2)

R(2,2)

8

R(1,1)

R(1,1)

9

R(3,0)

Здесь недостаточно использовать только множества последователей нетерминалов из левых частей правил, по которым выполняется свертка. Введем понятие ожидаемого правого контекста (ОПК):

Z : ▼ S „, {„} – каноническая расширенная конфигурация. Здесь (и только здесь) подчеркнут ОПК.

 


При сравнении базовых подмножеств конфигураций две канонические конфигурации считаются одинаковыми тогда и только тогда, когда у них совпадают и маркированное правило и ОПК.

Образование новой базы (перенос маркера через символ)  НЕ ИЗМЕНЯЕТ  ожидаемый правый контекст.

При выполнении замыкания из каждой канонической конфигурации вида N : a ▼ M b , { t0 } образуются:

M : ▼γ 1 , { t1}      M : ▼γ 1 , { t2}                  M : ▼γ 1 , { tk}

M : ▼γ 2 , { t1}      M : ▼γ 2 , { t2}                  M : ▼γ 2 , { tk}

...                                   

M : ▼γ n , { t1}      M : ▼γ n , { t2}                 M : ▼γ n , { tk}

где t1, t2, … tk – символы из множества предшественников цепочки b t0

ГрамматикаG LALR

0

Z : L „

1

L : E = R

2

L : R

3

R : E

4

E : * R

5

E : ident

 

N : a ▼ M b , { t0 }         Þ      "i M : ▼γ i , { t1} M : ▼γ i , { t2}                                     M : ▼γ i , { tk}