Информатика и выч. техника \ Системное программное обеспечение

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

	0	1	2	3	4	5	6	7	8	9
	S	T	F	+	*	(	)	i	c
0	G(1)	G(2)	G(3)			S(4)		S(5)	S(6)
1				S(7)						Stop
2				R(1,0)	S(8)		R(1,0)			R(1,0)
3				R(1,1)	R(1,1)		R(1,1)			R(1,1)
4	G(9)	G(2)	G(3)			S(4)		S(5)	S(6)
5				R(1,2)	R(1,2)		R(1,2)			R(1,2)
6				R(1,2)	R(1,2)		R(1,2)			R(1,2)
7		G(10)	G(3)			S(4)		S(5)	S(6)
8			G(11)			S(4)		S(5)	S(6)
9				S(7)			S(12)
10				R(3,0)	S(8)		R(3,0)			R(3,0)
11				R(3,1)	R(3,1)		R(3,1)			R(3,1)
12				R(3,2)	R(3,2)		R(3,2)			R(3,2)

Грамматика G_a1 называется SLR(1) – грамматикой.

LR(0)- и SLR(1)- грамматики и автоматы

Существуют LR(0) – грамматики:

ГрамматикаG_a0
0	Z : S
1	S : T
2	S : S + T
3	T : ( S )
4	T : i
5	T : c

При построении УТ восходящего синтаксического акцептора по этой грамматике конфликтов не возникнет вообще, поэтому не понадобится ни один символ (0 символов) для их разрешения.

К классу SLR(1)-грамматик относятся такие грамматики, для которых все конфликты при построении управляющей таблицы удается предупредить (иногда говорят – разрешить) путем использования множеств последователей нетерминалов, образующихся в результате свертки.

LR(1)-грамматики и автоматы

ГрамматикаG _LALR
0	Z : L
1	L : E = R
2	L : R
3	R : E
4	E : * R
5	E : ident

Таблица конфигураций:

Состояние	Образовано		База	Конфигурация	Символ	Отм.
Состояние	Из	Через	База	Конфигурация	Символ	Отм.
0			Да	Z : ▼ L	L	1
				L : ▼ E = R	E	2
				L : ▼ R	R	3
				E : ▼ * R	*	4
				E : ▼ i	i	5
				R : ▼ E	E	2
1	0	L	Да	Z : L ▼
2	0	E	Да	L : E ▼ = R	=	6
2	0		Да	R : E ▼
3	0	R	Да	L : R ▼
4	0, 4, 6	*	Да	E : * ▼ R	R	7
				R : ▼ E	E	8
				E : ▼ * R	*	9
				E : ▼ i	i	10
5	0, 4, 6	i	Да	R : i ▼
6	2	=	Да	L : E = ▼ R	R	11
				R : ▼ E	E	12
				E : ▼ * R	*	13
				E : ▼ i	i	14
7	4	R	Да	E : * R ▼
8	4, 6	E	Да	R : E ▼
9	6	R	Да	L : E = R ▼

1 2 3 4 5 6

Скачать файл