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

Формулировка задания

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

Задание

5.2.3. ^ ^

Решение

1. ,

2. ,

3. ,

4. .

 

Определим множества FIRST и FOLLOW для всех нетерминальных символов

 

 

 

Построим управляющую таблицу для грамматики G.

	a	(	)	^	ε
S	aR,1	(S)R, 2	ОШИБКА	ОШИБКА	ОШИБКА
R	ОШИБКА	ОШИБКА	ОШИБКА	^aR, 3	ε, 4
a	ВЫБРОС	ОШИБКА	ОШИБКА	ОШИБКА	ОШИБКА
(	ОШИБКА	ВЫБРОС	ОШИБКА	ОШИБКА	ОШИБКА
)	ОШИБКА	ОШИБКА	ВЫБРОС	ОШИБКА	ОШИБКА
^	ОШИБКА	ОШИБКА	ОШИБКА	ВЫБРОС	ОШИБКА
┴	ОШИБКА	ОШИБКА	ОШИБКА	ОШИБКА	ДОПУСК

 

 

Контрольный пример – разбор цепочки “(a^a)^a”, порождаемой этим алгоритмом.

 

((a^a)^a, S┴ , ) -> M((S)R,2)

((a^a)^a,(S)R┴ ,2) ->ВЫБРОС

(а^а)^а, S)R┴ ,2) -> M(aR,1)

(a^a)^a, aR)R┴ , 21) ->ВЫБРОС

(^a)^a, R)R┴ , 21) -> M(^aR, 3)

(^a)^a, ^aR)R┴ , 213) ->ВЫБРОС

(a)^a, aR)R┴ , 213) ->ВЫБРОС

()^a, R)R┴ , 213) -> M( ,4)

()^a, )R┴ , 2134) ->ВЫБРОС

(^a, R┴ , 2134) -> M(^aR, 3)

(^a, ^aR┴ , 21343) ->ВЫБРОС

(a, aR┴ , 21343) ->ВЫБРОС

( , R┴, 21343) ->M( ,4)

( ,┴ , 213434) ->ДОПУСК

 

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

T = { a, b, c, d, e }, N = { S, A, B }, R = { S ® aAB, S ® bBS, S ® e, A ® cBS, A ® e, B ® dB, B ® e };

 

1. S ® aAB,

2. S ® bBS,

3. S ® e,

4.A ® cBS,

5.A ® e,

6.B ® dB,

7.B ® e

 

S® β

FIRST(β)={a,b,e}

A® β

FIRST(β)={c, e}

B® β

FIRST(β) = {d, e}

 

 

	A	b	c	d	e
S	aAB,1	bBS,2		e,3	e,3
A			сBS,4	e,5	e,5
B	e,7	e,7		dB,6	e,7
a	B
b		B
c			B
d				B
┴					Д

 

 

Контрольный пример – разбор цепочки, порождаемой этим алгоритмом

acdbd

 

(acdbd,S┴, e)->

(acdbd,aAB┴,1)->

(cdbd,AB┴,1)->

(cdbd,cBSB┴,14)->

(dbd,BSB┴,14)->

(dbd,dBSB┴,146)->

(bd,BSB┴,146)->

(bd,SB┴,1467)->

(bd,bBSB┴,14672)->

(d,BSB┴,14672)->

(d,dBSB┴,146726)->

(e,BSB┴,146726)->

(e,SB┴,1467267)->

(e,B┴,14672673)->

(e,┴,146726737)

M(S,a)=(aAB,1)

ВЫБРОС

M(A,c)=(cBS,4)

ВЫБРОС

M(B,d)=(dB,6)

ВЫБРОС

M(B,b)=(e,7)

M(S,b)=(bBS,2)

ВЫБРОС

M(B,d)=(dB,6)

ВЫБРОС

M(B, e)=(e,7)

M(S, e)=(e,3)

M(B, e)=(e,7)

ДОПУСК

 

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

Формулировка задания:

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

T = { a, b, c, d, e }, N = { S, A, B }, R = { S ® aAB, S ® bBS, S ® e, A ® cBS, A ® e, B ® dB, B ® e };

 

1. S ® aAB,

2. S ® bBS,

3. S ® e,

4.A ® cBS,

5.A ® e,

6.B ® dB,

7.B ® e

 

S® β

FIRST(β)={a,b,e}

A® β

FIRST(β)={c, e}

B® β

FIRST(β) = {d, e}

 

 

	A	b	c	d	e
S	aAB,1	bBS,2		e,3	e,3
A			сBS,4	e,5	e,5
B	e,7	e,7		dB,6	e,7
a	B
b		B
c			B
d				B
┴					Д

 

 

Контрольный пример – разбор цепочки, порождаемой этим алгоритмом

acdbd

 

(acdbd,S┴, e)->

(acdbd,aAB┴,1)->

(cdbd,AB┴,1)->

(cdbd,cBSB┴,14)->

(dbd,BSB┴,14)->

(dbd,dBSB┴,146)->

(bd,BSB┴,146)->

(bd,SB┴,1467)->

(bd,bBSB┴,14672)->

(d,BSB┴,14672)->

(d,dBSB┴,146726)->

(e,BSB┴,146726)->

(e,SB┴,1467267)->

(e,B┴,14672673)->

(e,┴,146726737)

M(S,a)=(aAB,1)

ВЫБРОС

M(A,c)=(cBS,4)

ВЫБРОС

M(B,d)=(dB,6)

ВЫБРОС

M(B,b)=(e,7)

M(S,b)=(bBS,2)

ВЫБРОС

M(B,d)=(dB,6)

ВЫБРОС

M(B, e)=(e,7)

M(S, e)=(e,3)

M(B, e)=(e,7)

ДОПУСК

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

Пусть Х_iи Z_i – грамматические вхождения символов Х и Z в правую часть i-го правила, a Y_j – грамматическое вхождение символа Yв правую часть j-го правила. Определим множество OFIRST (Y_i) (входит первым), в которое включим Y_jи все грамматические вхождения, которыми могут начинаться цепочки, выводимые из Y.

OFIRST(Y_i) = {Y_j } È {X_i | Y Þ^* Ab Þ Xab и Xi – самое левое грамматическое вхождение в правую часть правила A à X}.

Замечание

Если в грамматике есть правила с пустой правой частью, то на последнем шаге вывода они не применяются.

Используя множества OFIRST, определим отношение OBLOW (входит под) следующим образом:

9. X_i OBLOW Y_j – это множество {(X_i, Y_j) | A à aX_iZ_ib Î P и Y_j OFIRST (Z_i) }.

^ OBLOW Y_j – это множество {(^,Y_j) | Y_j OFIRST (S₀) }, где S₀ – начальное вхождение.

Отношение X_i OBLOW Y_j определяет множество Qграмматических вхождений X_i, для которых представляющиеих магазинные символы могут встретиться в магазине непосредственно под символом, представляющим Y_j.

Отношение OBLOW будем задавать с помощью матрицы, содержащей n столбцов и n+1 строк, где n – число грамматических вхождений пополненной грамматикиG¢. Первые n строк и столбцы матрицы отмечены грамматическими вхождениями, а последняя строка – маркером дна магазина. Если X_i OBLOW Y_j, то элемент матрицы, расположенный в строке X_i и столбце Y_j, равен 1.

Построим матрицу отношения OBLOW для грамматикис правилами:

(1)	S	à	aAb		(4)	A	à	Bb
(2)	S	à	c		(5)	B	à	aA
(3)	A	à	bS		(6)	B	à	c

Непосредственно из правил вывода грамматики (1) и (4) получим:

A₁ OBLOW b₁ и B₄ OBLOW b₄.

Из определения отношения OBLOW следует, что ^ OBLOW Yj тогда и только тогда, когда Yj Î OFIRST(S₀). Из S можно вывести цепочки S Þ a₁A₁b₁ и S Þ c₂. Следовательно, OFIRST(S₀) = {a₁, c₂, S₀} и ^ OBLOW а₁, ^ OBLOW c₂ и ^ OBLOW S₀.

Рассмотрим правило грамматики с номером (1). Из определения отношения OBLOW следует, что

a₁ OBLOW Y_j для всех Y_j Î OFIRST(A₁).

Из А можно вывести цепочки:

A Þ b₃S₃, A Þ B₄b₄ Þ c₆b₄, A Þ B₄b₄ Þ a₅A₅b₄.

Следовательно, OFIRST(А₁) = {a₅, b₃, c₆, A₁, B₄} и a₁ OBLOW a₅, a₁ OBLOW b₃, a₁ OBLOW c₆, a₁ OBLOW A₁, a₁ OBLOW B₄.

Поступая подобным образом для правил (3) и (6), получим матрицу отношения OBLOW:

S0

a1

A1

b1

c2

b3

S3

B4

b4

a5

A5

c6

S0

a1

A1

b1

c2

b3

S3

B4

b4

a5

A5

c6

^

Опишем алгоритм построения управляющей таблицы T LR(0)-анализатора (множества LR(0)-таблиц) для LR(0)-грамматики, не содержащей правил с пустой правой частью. Этот алгоритм можно также использовать для проверки принадлежности КС-грамматики классу LR(0).

Алгоритм 8.2.Построение множества LR(0)-таблиц.

Вход. LR(0)-грамматика G = (N, S, Р, S), не содержащая e-правил.

Выход. Множество T LR(0)-таблиц для грамматики G или сообщение о том, что грамматикаGне является LR(0)-грамматикой.