Необходимое и достаточное условие LL(1)-грамматики

Для того чтобы грамматика G(V_N, V_T, P, S) была LL(1)-грамматикой необходимо и достаточно, чтобы для каждого символа АÎV_N, у которого в грамматике существует более одного правила вида А®a₁ | a₂ |…| a_n, выполнялось требование:

FIRST(1, a_iFOLLOW(1, A)) Ç FIRST(1, a_jFOLLOW(1, A)) = Æ,

" i¹j,0<i£n, 0<j£n.

Т.е. если для символа А отсутствует правило вида А®e, то все множества FIRST(1, a₁), FIRST(1, a₂),…, FIRST(1, a_n) должны попарно не пересекаться, если же присутствует правило А®e, то они не должны также пересекаться с множеством FOLLOW(1, A).

Для построения распознавателей для LL(1)-грамматик необходимо построить множества FIRST(1, x) и FOLLOW(1, A). Причем, если строка х будет начинаться с терминального символа а, то FIRST(1, x)=a, и если она будет начинаться с нетерминального символа А, то FIRST(1, x)=FIRST(1, A). Следовательно, достаточно рассмотреть алгоритмы построения множеств FIRST(1, A) и FOLLOW(1, A) для каждого нетерминального символа А.

3.4.2.3 Построение множества FIRST(1, A)

Для выполнения алгоритма необходимо предварительно преобразовать исходную грамматику G в грамматику G¢, не содержащую e-правил (см. лабораторную работу № 4). Алгоритм построения множества FIRST(1, A) использует грамматику G¢.

Шаг 1. Первоначально внести во множество первых символов для каждого нетерминального символа А все символы, стоящие в начале правых частей правил для этого нетерминала, т.е.

" АÎV_N FIRST₀(1, A) = {X | A®Xa ÎP, XÎ(V_TÈV_N),aÎ(V_TÈV_N)^*}.

Шаг 2.Для всех АÎV_N положить:

FIRST_i+1(1, A) = FIRST_i(1, A) È FIRST_i(1, B), " ВÎ(FIRST(1, A)ÇV_N).

Шаг 3. Если существует АÎV_N, такой что FIRST_i+1(1, A) ¹ FIRST_i(1, A), то присвоить i=i+1 и вернуться к шагу 2, иначе перейти к шагу 4.

Шаг 4.Исключить из построенных множеств все нетерминальные символы, т.е.

" AÎV_N FIRST(1, A) = FIRST_i(1, A) _{\ N}.

3.4.2.4 Построение множества FOLLOW(1, A)

Алгоритм основан на использовании правил вывода грамматики G.

Шаг 1.Первоначально внести во множество последующих символов для каждого нетерминального символа А все символы, которые в правых частях правил вывода встречаются непосредственно за символом А, т.е.

" AÎV_N FOLLOW₀(1, A) = {X | $ B ® aAXb Î P, B Î V_N, X Î (V_TÈV_N),

a, bÎ(V_TÈV_N)^*}.

Шаг 2.Внести пустую строку во множество FOLLOW(1, S), т.е.

FOLLOW(1, S) = FOLLOW(1, S)È{e}.

Шаг 3.Для всех АÎV_N вычислить:

FOLLOW¢_i(1,A)=FOLLOW_i(1,A)ÈFIRST(1,B),"BÎ(FOLLOW_i(1,A)ÇV_N).

Шаг 4.Для всех АÎV_N положить:

FOLLOW²_i(1, A)=FOLLOW¢_i(1, A)ÈFOLLOW¢_i(1, B),

"BÎ(FOLLOW¢_i(1, A)ÇV_N), если $ правило B®e.

Шаг 5.Для всех АÎV_N определить:

FOLLOW_i+1(1, A) = FOLLOW²_i(1, A)ÈFOLLOW²_i(1, B),

для всех нетерминальных символов BÎV_N, имеющих правило вида

B®aA, aÎ(V_TÈV_N)^*.

Шаг 6.Если существует AÎV_N такой, что FOLLOW_i+1(1,A)¹FOLLOW_i(1,A), то положить i:=i+1 и вернуться к шагу 3, иначе перейти к шагу 7.

Шаг 7.Исключить из построенных множеств все нетерминальные символы, т.е. " AÎV_N FOLLOW(1, A) = FOLLOW_i(1, A)_{\ N}.

3.4.2.5 Алгоритм «сдвиг-свертка» для LL(1)-грамматик

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

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

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

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

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

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

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

ПримерДана грамматика 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) для каждого нетерминала А представлено в таблице 3.3.

 

Таблица 3.3 – Построение множеств 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) для каждого нетерминала А представлено в таблице 3.4.

Таблица 3.4 – Построение множеств 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) для каждого нетерминала А сведены в таблицу 3.5.

 

Таблица 3.5 – Множества 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 показан в таблице 3.6.

 

Таблица 3.6 - Разбор строки (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)).

 

Рисунок 3.3 – Дерево вывода для цепочки (a+(b-a)) в грамматике G