Алгоритм восходящего восстановления дерева разбора. Понятие конфигурации. Связь между конфигурациями, состояниями и операциями восходящего акцептора, страница 3

4.  Если в некоторой конфигурации данного состояния маркер находится перед нетерминалом, например

P : m▼ L h

то автомат (оказавшийся в этом состоянии в результате выполнения операции свертки в этот нетерминал) должен выполнить операцию перехода в строго определенное другое состояние БЕЗ чтения следующего терминала со входа. Естественно, это означает, что состоянию, в которое осуществляется переход, соответствует конфигурация P : m L ▼ h.

5.  Если в совокупности конфигураций данного состояния есть конфигурация вида

M : b ▼

то автомат, оказавшийся в этом состоянии, должен выполнить операцию свертки R_k,m, где k – длина цепочки b, а m – номер колонки управляющей таблицы, озаглавленной нетерминалом M.

6. Если автомат оказался в состоянии, которому соответствует конфигурация Z : S ▼ „ и текущим входным символом является „, то должна быть выполнена операция Stop.

Преобразование грамматики в управляющую таблицу восходящего синтаксического анализатора

Этап 1. Построение таблицы конфигураций

Шаг 1. Формирование базы начального состояния:

Состояние	Образовано		База	Конфигурация	Символ	Отм.
	Из	Через
0			Да	Z : ▼ S „	S

Шаг 2. Определение замыкания базового множества конфигураций.

Состояние	Образовано		База	Конфигурация	Символ	Отм.
	Из	Через
0			Да	Z : ▼ S „	S
				S : ▼ S + T	S
				S : ▼ T	T
				T : ▼ T * F	T
				T : ▼ F	F
				F : ▼ ( S )	(
				F : ▼ i	i
				F : ▼ c	c

Шаг 3. Образование новой базы.

Берется первая не отмеченная строка, в которой не пуста клетка «Символ» (если таких нет – построение таблицы закончено). Берутся все конфигурации данного состояния, в которых маркер находится перед этим символом, в колонку «отметка» этих строк заносится что-нибудь. Маркеры в этих конфигурациях переносятся через один символ (образуется новая база):

Z : ▼ S „          =>     Z : S ▼„

S : ▼ S + T       =>     S : S ▼+ T

Шаг 4. Проверка наличия состояния с только что образованной базой.

4.1.  Если такое состояние есть, то в колонку «Из» этого состояния добавляется номер того состояния, из конфигураций которого была образована новая база. Возврат к шагу 3.

4.2.  Если такого состояния нет, то оно добавляется:

Состояние	Образовано		База	Конфигурация	Символ	Отм.
	Из	Через
0			Да	Z : ▼ S „	S	1
				S : ▼ S + T	S	1
				S : ▼ T	T
				T : ▼ T * F	T
				T : ▼ F	F
				F : ▼ ( S )	(
				F : ▼ i	i
				F : ▼ c	c
1	0	S	Да	Z : S ▼„	„
		S	Да	S : S ▼+ T	+