Лабораторная работа № 6 Моделирование фу. Лабораторная работа 6 Тема работы Моделирование функционирования распознавателя для ll (1) грамматик

• Название: Лабораторная работа 6 Тема работы Моделирование функционирования распознавателя для ll (1) грамматик
• Дата: 11.12.2022
• Размер: 0.58 Mb.
• Имя файла: Лабораторная работа № 6 Моделирование фу.doc
• Тип: Лабораторная работа; #838399
• страница: 3 из 5

Алгоритм 6.3. Функционирование распознавателя цепочек для LL(1)-грамматик

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

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

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

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

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

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)	0	1	2	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)
0	S	)	), 	), 
	R			
	T	R	R, +, -	R, +, -
1	S	), 	), 	), 
	R	), 	), 	), 
	T	R, +, -	R, +, -	R, +, -, ), 
2	S	), 	), 	), 
	R	), 	), 	), 
	T	R, +, -, ), 	R, +, -, ), 	R, +, -, ), 
FOLLOW(1, S)		), 
FOLLOW(1, R)		), 
FOLLOW(1, T)		+, -, ), 

Этап 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	), 
R	+, -	), 
T	(, a, b	+, -, ), 

Грамматика 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, т.к. )  FOLLOW(1, R)
)R)R	))	выброс
R)R	)	свертка R, т.к. )  FOLLOW(1, R)
)R	)	выброс
R		свертка R, т.к.  FOLLOW(1, R)
		строка принята полностью

Шаг 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.