Преобразование таблицы конфигураций в управляющую таблицу, страница 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 , { t₀ } образуются:

M : ▼γ ₁ , { t₁}      M : ▼γ ₁ , { t₂}         …         M : ▼γ ₁ , { t_k}

M : ▼γ ₂ , { t₁}      M : ▼γ ₂ , { t₂}         …         M : ▼γ ₂ , { t_k}

...                                   

M : ▼γ _n , { t₁}      M : ▼γ _n , { t₂}        …         M : ▼γ _n , { t_k}

где t₁, t₂, … t_k – символы из множества предшественников цепочки b t₀

Грамматика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 , { t₀ }         Þ      "_i M : ▼γ _i , { t₁} M : ▼γ _i , { t₂}                         …            M : ▼γ _i , { t_k}