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

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

Страницы работы

11 страниц (Word-файл)

Скачать файл

Содержание работы

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

Шаг 1. Строится заготовка управляющей таблицы (13 строк – от 0 до 12; 10 колонок – 3 нетерминала, 6 терминалов и ), в клетку строки 1 колонки заносится знак операции Stop.

Шаг 2. По первым трем колонкам таблицы конфигураций (Состояние, Из, Через) формируются знаки операций Go (если в колонке «Через» нетерминал) и Shift (если в этой колонке терминал) – в клетку строки, номер которой взят из колонки «Из», находящуюся на пересечении с колонкой, озаглавленной символом из колонки «Через» пишется G или S с номером, взятым из колонки «Состояние», в скобках.

Шаг 3. Во все клетки строк, состояниям которых соответствуют конфигурации вида M : b ▼, а колонки озаглавлены терминалами (в том числе ) пишется знак операции R[educe] с двумя параметрами в скобках:

– первый параметр – это длина правой части правила (количество состояний, сбрасываемых со стека);

– второй параметр – номер колонки, озаглавленной нетерминалом из левой части правила (из этой колонки на следующем такте будет выбрана операция Go).

В результате получится такая УТ:

	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)	R(1,0)	R(1,0)	R(1,0)
3				R(1,1)	R(1,1)	R(1,1)	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)	R(1,2)	R(1,2)	R(1,2)
6				R(1,2)	R(1,2)	R(1,2)	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)	R(3,0)	R(3,0)	R(3,0)
11				R(3,1)	R(3,1)	R(3,1)	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)	R(3,2)	R(3,2)	R(3,2)

Разрешение конфликтов путем использования
множеств последователей нетерминальных символов

Текущий уровень дерева разбора выглядит так: Выполнение операции свертки приведет к:

для конфликта в состоянии 2: … T * … … S * …

для конфликта в состоянии 10: … S+ T * … … S * …

Однако, терминал * НЕ принадлежит множеству последователей нетерминала S.

Разрешать этот конфликт в пользу знака операции свертки, формирующего нетерминал S при наличии на входе терминала * нельзя. Этот конфликт должен быть разрешен в пользу знака операции сдвига.

Более того, знак ЛЮБОЙ операцию свертки имеет смысл заносить только в те клетки, колонки которых помечены терминалами из множества последователей нетерминала, образующегося в результате свертки. Теперь управляющая таблица будет выглядеть так: