Главная | Обратная связь

Построение недетерминированного расширенного МП-автомата по КС-грамматике

 

Построить недетерминированный расширенный МП-автомат по КС- грамматике

T = { a, b, с, d }, N = { S, A }, R = { S ® aA, S ® Ab, A ® Sc, A ® d };

 

P=({q, r}, {a, b, c, d}, {a, b, c, d, S, A,Z}, d, q, Z, {r})

 

d(q, t, e)=(q, t), t €{ a, b, с, d }

 

d(q, e, аA)= (q, S)

d(q, e, Ab)= (q, S)

d(q, e, Sc)= (q, A)

d(q, e, d)= (q, A)

d(q, e, ZS)= (r, e)

Построить управляющую таблицу и промоделировать работу LL(1)-анализатора для КС-грамматики G = < T, N, S, R >

Определение. Множество ПЕРВЫЙ (FIRST) — множество терминальных символов, которыми начинаются цепочки, выводимые из нетерминала A:

FIRST(A) = {a Î S | A Þ_l⁺ ab, где b Î (N È S)^*}.

Определение. Множество СЛЕДУЮЩИЙ (FOLLOW) — множество терминальныхсимволов,которые могут встретиться непосредственно справа от нетерминала A в некоторой сентенциальной форме:

FOLLOW(А) = {a Î S | S Þ_l^* aAg и a Î FIRST (g)}.

Пример 7.1

Для рассмотренной выше грамматики с правилами

(1)	S	à	aAS		(3)	A	à	cAS
(2)	S	à	b		(4)	A	à	e

множество FIRST(A) = {c}, а множество FOLLOW(A) = {a, b}, так как непосредственно справа от нетерминала A в сентенциальных формах может находиться символ S и FIRST(S) = {a, b}.

Определение. КС-грамматика G = (N, S, P, S) является LL(1)-грамматикой тогда и только тогда, когда для каждого A-правила грамматики

A à a₁ | a₂ | … | a_n, n ³ 1

выполняются следующие условия:

1. Множества FIRST(a₁), FIRST (a₂), …, FIRST (a_n) попарно не пересекаются.

2. Если a_i Þ^* e, то FIRST (a_j) ∩ FOLLOW(A) = Æ для 1 £ j £ n, i ¹ j.

Важным следствием этого определения является то, что леворекурсивная грамматика не может быть LL(1)-грамматикой.

Другое важное свойство LL(1)-грамматики – ее однозначност.

 

Алгоритм 7.1.Алгоритм построения управляющей таблицы М для LL(1)-грамматики.

Вход. LL(1)-грамматики G = (N, S, Р, S).

Выход. Корректная управляющая таблица M для грамматики G.

Описание алгоритма.

Таблица M определяется на множестве (N È S È {^}) ´ (S È {e}) по следующим правилам:

3. ЕслиA à b – правило вывода грамматики с номером i, то М(А, а) = (b, i) для всех a ¹ e , принадлежащих множеству FIRST(b).

Если e Î FIRST(b), то М(А, b) = (b, i) для всех b Î FOLLOW(A).

4. М(a, a) = ВЫБРОС для всех aÎS.

5. М(^, e) = ДОПУСК.

6. В остальных случаях M(X, a) = ОШИБКА для X Î (N È S È {^}) и a Î S È {e}.

Конец алгоритма

Рассмотрим,как строится управляющая таблица М для грамматики G₁ с правилами:

(1)	E	à	TE¢		(5)	T¢	à	*PT¢
(2)	E¢	à	+TE¢		(6)	T¢	à	e
(3)	E¢	à	e		(7)	P	à	i
(4)	T	à	PT¢		(8)	P	à	(E)

Управляющая таблица должна содержать 11 строк, помеченных символами из множества (N È S È {^}), и 6 столбцов, помеченных символами из множества (S È {e}).

Заполнение таблицы начнем с выполнения шага 1 алгоритма.

Шаг 1. Будем строить таблицу построчно, для чего последовательно рассматриваем все нетерминальные символы.

7. Нетерминал E.

Этому символу соответствует правило вывода грамматики

(1) E à TE¢. Так как FIRST(TE¢) = { (, i}, то следовательно,

M(E, ( ) = M(E, i) = ( TE¢, 1).

8. Для нетерминала E¢ в грамматике имеется два правила вывода: (2) и (3).

· Для правила (2) E¢ à + TE¢ множество FIRST(+TE¢) = {+} и, следовательно, M(E¢, +) = (+TE¢, 2).

· Правило (3) имеет пустую правую часть, поэтому необходимо вычислить множество символов, следующих за нетерминалом E¢ в сетенциальных формах. Построив левый вывод E Þ TE¢ Þ PT¢E¢ Þ (E)T¢E¢ Þ (TE¢)TE¢…, получим FOLLOW(E¢) = { ), e).

Таким образом, M(E¢, ) ) = M(E¢, e) = (e, 3).

· Выполняя шаг 1 алгоритма для нетерминалов Т, T¢’ и Р,получим:

Правило грамматики	Множество	Значение M
(4)	T	à	PT¢	FIRST(PT¢)	=	{ (, i)}	M(T¢, ( ) = M(T¢, i) = (PT¢, 4)
(5)	T¢	à	*PT¢	FIRST(*PT¢)	=	{*}	M(T¢, *) = (*PT¢, 5)
(6)	T¢	à	e	FOLLOW(T¢)	=	{+, ), e}	M(T¢,+) = M(T¢, )) = M(T¢,e) = (e,6)
(7)	P	à	i	FIRST(i)	=	{i}	M(P, i ) = (i, 7)
(8)	P	à	(E)	FIRST((E))	=	{(}	M(P, ( ) = ((E), 8)

Шаг 2. Далее всем элементам таблицы, находящимся на пересечении строки и столбца, отмеченным одним и тем же терминальным символом, присвоим значение ВЫБРОС.

Шаг 3. Элементу таблицы М(^, e) припишем значение ДОПУСК.

Шаг 4. Остальным элементам таблицы присвоим значение ОШИБКА.

В заключение, можно сравнить таблицу, построенную при помощи алгоритма 7.1, с управляющей таблицей, приведенной на рис. 7.5 и убедиться, что они совпадают. В [3] доказано, что алгоритм 7.1 строит корректную управляющую таблицу.