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

	L	R	E	id	=	*	„
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(10)	S(12)		S(11)
7					R(2,2)		R(2,2)
8					R(1,1)		R(1,1)
9							R(3,0)
10							R(1,1)
11		G(13)	G(10)	S(12)		S(11)
12							R(1,2)
13							R(2,2)

Для сравнения:

	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)

Использование канонических расширенных конфигураций позволило построить управляющую таблицу так называемого LR(1) – анализатора, при этом все конфликты оказались предупреждены, но возросло количество состояний автомата (для рассмотренного очень простого примера – с 10 до 14).

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

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

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

Строить таблицу расширенных конфигураций можно двумя способами:

1.  Построить таблицу канонических конфигураций, потом:

–  в каждом состоянии объединить в одну конфигурации с одинаковым маркированным правилом (см. состояние 4, из конфигураций E : * ▼ R ,{=} и E : * ▼ R ,{ „} получится E : * ▼ R ,{= „};

–  объединить в одно каждые 2 таких состояния, у которых базовые подмножества конфигураций совпадают по маркированным правилам (например, состояния 8 и 10 можно объединить, останется 8, удаляется 10); после объединения нужно:

  a.  все переходы в удаленное состояние заменить переходами в оставленное состояние;

  b.  перенумеровать все состояния, номера которых больше номера удаленного состояния и соответственно изменить все переходы на такие состояния;

  c.  и главное – пересчитать ОПК всех дочерних конфигураций (в том числе у всех дочерних состояний) если у оставленного состояния в результате объединения изменился ОПК хотя бы одной базовой конфигурации.

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