Алгоритм 6.3. Функционирование распознавателя цепочек

для LL (1)-грамматик

Шаг 1. Помещаем в стек начальный символ грамматики S, а во входной буфер исходную цепочку символов.

Шаг 2.До тех пор пока в стеке и во входном буфере останется только пустая строка e либо будет обнаружена ошибка в алгоритме разбора, выполняем одно из следующих действий:

- если на верхушке стека находится нетерминальный символ А и очередной символ входной строки символ а, то выполняем операцию «свертка» по правилу А ® х при условии, что а Î FIRST (1, x), т.е. извлекаем из стека символ А и заносим в стек строку х, не меняя содержимого входного буфера;

- если на верхушке стека находится нетерминальный символ А и очередной символ входной строки символ а, то выполняем операцию «свертка» по правилу А ® e при условии, что а Î FOLLOW (1, A), т.е. извлекаем из стека символ А и заносим в стек строку e, не меняя содержимого входного буфера;

- если на верхушке стека находится терминальный символ а, совпадающий с очередным символом входной строки, то выполняем операцию «выброс», т.е. удаляем из стека и входного буфера данный терминальный символ;

- если содержимое стека и входного буфера пусто, то исходная строка прочитана полностью, и разбор завершен удачно;

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

 

Пример 6.1. Дана грамматика G ({ S, T, R }, {+, -, (,), a, b }, P, S), с правилами P: 1) S ® TR; 2) R ®e | + TR | - TR; 3) T ®(S) | a | b. Построить распознаватель для строки (a +(b - a)) языка грамматики G.

 

Этап 1. Преобразуем грамматику G в грамматику G ¢, не содержащую e -правил:

N ₀ = { R };

N ₁ = { R }, т.к. N ₀ = N ₁, то во множество P¢ войдут правила:

1) S ® TR | T;2) R® +TR | +T | -TR | -T; 3) T ®(S) | a | b.

 

Этап 2. Построение множеств FIRST (1, A) для каждого нетерминала А представлено в таблице 6.1.

 

Таблица 6.1 – Построение множеств FIRST (1, A)

 

FIRSTi (1, A)				FIRST (1, A)
S	T	T, (, a, b	T, (, a, b	(, a, b
R	+, -	+, -	+, -	+, -
T	(, a, b	(, a, b	(, a, b	(, a, b

 

Этап 3. Построение множеств FOLLOW (1, A) для каждого нетерминала А представлено в таблице 6.2.

 

Таблица 6.2 – Построение множеств FOLLOW (1, A)

 

Шаг	Нетерминалы	FOLLOWi (1, A)	FOLLOWi^’ (1, A)	FOLLOWi^’’ (1, A)
	S	)	), e	), e
R	Æ	Æ	Æ
T	R	R, +, -	R, +, -
	S	), e	), e	), e
R	), e	), e	), e
T	R, +, -	R, +, -	R, +, -,), e
	S	), e	), e	), e
R	), e	), e	), e
T	R, +, -,), e	R, +, -,), e	R, +, -,), e
FOLLOW (1, S)	), e
FOLLOW (1, R)	), e
FOLLOW (1, T)	+, -,), e

 

Этап 4. Множества FIRST (1, A) и FOLLOW (1, A) для каждого нетерминала А сведены в таблицу 6.3.

 

Таблица 6.3 – Множества FIRST (1, A) и FOLLOW (1, A)

 

A	FIRST (1, A)	FOLLOW (1, A)
S	(, a, b	), e
R	+, -	), e
T	(, a, b	+, -,), e

 

Грамматика G является LL (1) - грамматикой, т.к. для каждого нетерминала А, имеющего альтернативные выводы, множества FIRST (1, A) попарно не пересекаются, а для нетерминала R они также не пересекаются со множеством FOLLOW (1, R).

 

Шаг 5. Разбор строки (a +(b - a)) для грамматики G показан в таблице 6.4.

Таблица 6.4 - Разбор строки (a +(b - a)) для грамматики G

 

Стек	Входной буфер	Действие
S	(a +(b - a))	свертка S ® TR, т.к. (Î FIRST (1, TR)
TR	(a +(b - a))	свертка T ®(S), т.к. (Î FIRST (1, (S))
(S) R	(a +(b -a))	выброс
S) R	a +(b - a))	свертка S ® TR, т.к. a Î FIRST (1, TR)
TR) R	a +(b - a))	свертка T ® a, т.к. a Î FIRST (1, a)
aR) R	a +(b - a))	выброс
R) R	+(b - a))	свертка R ®+ TR, т.к. +Î FIRST (1, TR)
+ TR) R	+(b - a))	выброс
TR) R	(b - a))	свертка T ®(S), т.к. (Î FIRST (1, (S))
(S) R) R	(b - a))	выброс
S) R) R	b - a))	свертка S ® TR, т.к. b Î FIRST (1, TR)
TR) R) R	b - a))	свертка T ® b, т.к. b Î FIRST (1, b)
bR) R) R	b - a))	выброс
R) R) R	- a))	свертка R ®- TR, т.к. -Î FIRST (1, - TR)
- TR) R) R	- a))	выброс
TR) R) R	a))	свертка T ® a, т.к. a Î FIRST (1, a)
aR) R) R	a))	выброс
R) R) R	))	свертка R ®e, т.к.) Î FOLLOW (1, R)
) R) R	))	выброс
R) R	)	свертка R ®e, т.к.) Î FOLLOW (1, R)
) R	)	выброс
R	e	свертка R ®e, т.к. eÎ FOLLOW (1, R)
e	e	строка принята полностью

Шаг 6. Получили следующую цепочку вывода:

 

S Þ TR Þ(S) R Þ(TR) R Þ(aR) R Þ(a + TR) R Þ(a +(S) R) R Þ(a +(TR) R) R Þ

Þ(a +(bR) R) R Þ(a +(b - TR) R) R Þ(a +(b - aR) R) R Þ(a +(b - a) R) R Þ(a +(b - a)) R

Þ(a +(b - a)).

 

Нисходящее дерево разбора цепочки представлено на рисунке 6.1.