Пример 27

Построение таблицы разбора SLR-анализа

Рассмотрим, как построить функции action и goto SLR-анализа по детерминированному конечному автомату, распознающему активные префиксы. Грамматику G расширяем до грамматики G’, и на основе G’ строим каноническую систему множеств пунктов для G’. Строим action, функцию действий синтаксического анализа, и goto, функцию переходов. Потребуется множество FOLLOW(A) для каждого нетерминала А грамматики.

Алгоритм построение таблицы SLR-анализа

Вход. Расширенная грамматика G’.

Выход. Функции action и goto таблицы SLR-анализа для грамматики G’.

Метод.

1. Построим С = {I₀,I₁,...,I_n} — систему множеств LR(0)-пунктов для грамматики G’.

2. Состояние i строится на основе I_i. Действия синтаксического анализа для состояния i определяются следующим образом:

a) если [А → α • aβ]є I_i, и goto( I_i, a)=I_j, то определить action[i, а] как "перенос j"; здесь а – терминальный символ;

b) если [А → α • ]є I_i, то определить action[i, а] как "свертка А → α " для всех а из FOLLOW(A); здесь А не должно быть S’;

c) если [S’ → S•] є I_i, то определить action[i, $] как "допуск".

Если по этим правилам генерируются конфликтующие действия, то грамматика не является SLR(l). Алгоритм не в состоянии построить синтаксический анализатор для нее.

3. Переходы goto для состояния i и всех нетерминалов А строятся по правилу: если goto(I_i, A)= I_j, то goto[i, A]=j.

4. Все записи, не определенные по правилам (2) и (3), указываются как "ошибка".

5. Начальное состояние синтаксического анализатора представляет собой состояние, построенное из множества пунктов, содержащего [ S’ → S• ] [3].

Построим SLR-таблицу для грамматики (7.2).

Вначале рассматривается множество пунктов I₀:

Е’→ •E

Е → •Е+Т

Е → •Т

Т → •T*F

Т → •F

F → •(E)

F → • id

Пункт F → •(E) дает запись action[0, (] = "перенос 4", пункт F → •id — запись action[0, id]= "перенос 5". Другие пункты I₀ к записям action не приводят.

Рас­сматривается I₁:

Е^’→ E•

E → Е•+Т

Первый пункт дает action[1, $] - "допуск", а второй — action[1, +] - "перенос б". Переход к I₂ дает:

Е→ T•

T→ T•*F

Поскольку FOLLOW(E) ={$,+,)}, из первого пункта следует action[2, $] = action[2, +] = action[2,)] = "свертка E → T". Второй пункт дает action[2, *] = "перенос". Продолжая таким образом, рассмотрение множеств пунктов, получаем таблицу, показанную на рис. 39. В ней номера продукций в свертках те же, что и номера, под которыми продукции приведены в исходной грамматике, т.е. E → E+T имеет номер 1, E → Т — номер 2 и т.д.

СОСТОЯНИЕ	action	goto
id	+	*	(	)	$	E	T	F
	p5			p4				2
		p6				acc
		s2	s7		s2	s2
		s4	s4		s4	s4
	p5			p4				2
		s6	s6		s6	s6
	p5							9
	p5			p4
		s6		p4	p11
		s1	s7		s1	s1
		s3	s3		s3	S3
		s5	s5		s5	s5

Рис. 39. Таблица синтаксического анализа грамматики арифметических выражений

На рисунке использованы следующие обозначения действий:

1. pi означает перенос и i-е состояние на вершине стека,

2. sj означает свертку в соответствии с продукцией номер j,

3. acc означает допуск входной строки,

4. пустая ячейка означает ошибку.

Значение goto[s, а] для терминала а находится в поле action, связанном с переносом для входного символа а и состояния s. Поле goto дает значения goto[s, А] для нетерминалов А.

Для входной строки id*id+id последовательность содержимого стека и входной стро­ки показана на рис. 40. Например, в строке (1) LR-анализатор находится в состоянии 0 с первым входным символом id. Действие в строке 0 и столбце id таблицы action на рис. 39 — p5, означающее перенос и внесение в стек состояния 5. В строке (2) выпол­няется внесение в стек id и p5 и удаление id из входного потока.

После этого текущим входным символом становится *; действие длясостояния p5 и входного символа * — s6, т.е. свертка согласно продукции F → id. Co стека при этом снимаются два символа (символ состояния и символ грамматики), ина вершине стека появляется состояние 0. Поскольку goto[0, F] равно p3, в стек вносятся F и 3; получа­ется конфигурация, показанная в строке (3). Остальные строки на рис. 40 получены аналогично.

	Стек	Входной поток	Действие
(1)		id * id + id $	Перенос
(2)	0 id 5	* id + id $	Свертка по F → id
(3)	0 F 3	* id + id $	Свертка по T → F
(4)	0 Т 2	* id + id $	Перенос
(5)	0 Т 2 * 7	id + id $	Перенос
(6)	0 Т 2 * 7 id 5	+ id $	Свертка по F→ id
(7)	0 Т 2 * 7 F 10	+ id $	Свертка по T → T*F
(8)	0 Т 2	+ id $	Свертка по E → T
(9)	0 E 1	+ id $	Перенос
(10)	0 E 1 + 6	id $	Перенос
(11)	0 E 1 + 6 id 5	$	Свертка по F → id
(12)	0 E 1 + 6 F 3	$	Свертка по Т→ F
(13)	0 E 1 + 6 Т 9	$	E → E+T
(14)	0 E 1	$	Допуск

Рис. 40. Действия LR-анализатора no разбору строки id*id+id

Дата добавления: 2014-12-27