Необходимое и достаточное условие 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

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться:

Популярное:

1. В которых не соблюдается условие джечаб
2. Восприимчивость к эмоциональным состояниям партнера -профессионально необходимое качество для тех, кто работает с людьми.
3. Глава I. Развитие памяти младших школьников с ЗПР как условие полноценного обучения
4. Главное условие — признать Папу.
5. Назовите основное условие начала ГНВП
6. Необходимое количество жидкости для промывания желудка ребенку старше года
7. Необходимое новое «культурное преображение»
8. Необходимое условие локального безусловного экстремума во внутренних точках
9. Необходимым условием жизнеспособности ТС является согласование ритмики (частоты колебаний, периодичности) работы подсистем ТС, а также процессов, происходящих в ТС и её надсистемах.
10. Оператор цикла с постусловием
11. Понятие о давлениях. Основное условие равновесия. Понятие о репрессии и депрессии.