Восходящий синтаксический акцепт. Эквивалентные преобразования грамматик

Восходящий синтаксический акцепт

(Повторение)

Основная идея:

Конфликты в процессе синтаксического акцепта, невозможность их разрешения.

Стековый автомат с несколькими состояниями

 

Движение по правилу:

Операции восходящего синтаксического акцептора:

1.  Сдвиг ( Shift ) S_n:

1.1.1.  чтение следующего входного символа;

1.1.2.  занесение номера состояния n в стек состояний;

1.1.3.  переключение автомата в состояние n.

1.2.  Переход ( Go ) G_n:

1.2.1.  занесение номера состояния n в стек состояний;

1.2.2.  переключение автомата в состояние n.

2.  Свертка ( Reduce ) R_k,m:

2.1.  Со стека состояний сбрасывается k номеров состояний;

2.2.  Текущим устанавливается состояние, номер которого оказался на верхушке стека;

2.3.  В качестве текущей колонки УТ устанавливается колонка m.

3.  Операция Stop.

4.  Операция останова по ошибке.

Понятие конфигурации.

Связь конфигураций с состояниями восходящего акцептора.

Построение таблицы конфигураций:

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

…

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

Занесение знаков операций S (сдвиг) и G (переход)

Занесение знаков операций R (свертка)

Возможность возникновения конфликтов на этапе построения автомата.

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

Понятия LR(0)- и SLR(1)- грамматик

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

Понятие ожидаемого правого контекста (ОПК) и канонической расширенной конфигурации.

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

Понятие LR(1)-грамматик.

Понятие расширенной конфигурации. Построение таблицы расширенных конфигураций.

Построение таблицы расширенных конфигураций и управляющей таблицы восходящего автомата.

Понятие LALR(1)- грамматик.

Эквивалентные преобразования грамматик

Ликвидация нетерминального символа

Грамматика G a2
1	S : U R
2	R : + S
3	R :
4	U : V W
5	W : * U
6	W :
7	V : ( S )
8	V : i <идентификатор>
9	V : c <константа>

Грамматика G a2-1
1	S : U + S
2	S : U
3	U : V W
4	W : * U
5	W :
6	V : ( S )
7	V : i <идентификатор>
8	V : c <константа>

Грамматика G a2-2
1	S : U + S
2	S : U
3	U : V * U
4	U : V
5	V : ( S )
6	V : i <идентификатор>
7	V : c <константа>

Факторизация: образование нового нетерминального символа

U : V * U

U : V

Цепочка V является общим фактором двух правил

Обозначим остатки этих правил новым нетерминалом W, напишем для него правила:

W : * U

W :

И теперь вместо двух исходных правил напишем одно:

U : V W

Преобразование косвенной рекурсии в прямую

Грамматика G x
1	X : N M
2	N : i Y
3	M : ; X
4	M :
5	Y : , Z
6	Y :
7	Z : * N

	X	N	M	Y	Z
X		1	1
N				1
M	1
Y					1
Z		1

	X	N	M	Y	Z
X	2	1	1	2	3
N		3		1	2
M	1	2	2	3	4
Y		2		3	1
Z		1		2	3

Грамматика G x-2
1	X : N M
2	N : i , * N
3	N : i
4	M : ; X
5	M :

Грамматика G x-1
1	X : N M
2	N : i Y
3	M : ; X
4	M :
5	Y : , * N
6	Y :

Грамматика G x-3
1	X : N ; X
2	X : N
3	N : i , * N
4	N : i

Изменение стороны рекурсии

Простейший случай:

N : N β                                                                                                        N : γ M

N : γ,                                                                                                        M : β M

                                      M : ε

γ

γ β

γ β β

γ β β β

…

Произвольный случай:

N : N β 1	N : γ 1
N : N β 2	N : γ 2
…
N : N β k	…
	N : γ r

N : γ 1 M	M : β 1 M
N : γ 2 M	M : β 2 M
...
N : γ r M	…
	M : β k M
	M : ε