11. Реализовать управляющую таблицу m для lr(k) анализатора.

Дана грамматика G(V, T, P, S):

V = {S, F, L},

T={i, * , :,(,)},

P = {S→(F: L), F→ L*, F→ i, L→F}

LR(k) – анализатор.

Таблица кодирования магазинных символов.

Символ грамматики	Магазинный символ	Кодируемая цепочка
S	S1	┴S
F	F1	(F
	F3	F
L	L1	(F:L
	L2	L
i	i3	i
:	:1	(F:
*	*2	L*
(	(1	(
)	)1	(F:L)

12. Построить множество lr(0)-таблиц не содержащих ε-правила.

Построим управляющую таблицу LR(0) – анализатора для грамматики, имеющей следующие правила:

1. S→(F:L)

2. F→ L*

3. F→ i

4. L→F

Расширенная грамматика: если G – грамматика со стартовым символом S, то расширенная грамматика G’ имеет стартовый символ S’ и продукцию S’→S.

CLOSURE(I) – замыкание множества пунктов I. Если в I входит пункт A→α•Bβ, то в замыкании надо взять все пункты вида B→γ. (Всё, что может быть достигнуто левыми порождениями).

GOTO(I,X) – замыкание множества продукций I вида A→α X•β, где A→α•X β входит в I.

Определим множества А₀ =CLOSURE({S’→•S}) ={S’→•S, S→•(F:L)}. Включим его в систему в качестве «неотмеченного» множества. Затем должны отметить множество А₀ и определить множества GOTO(A₀, X).

A₁=GOTO(A₀, S)=GOTO({S’→•S }, S) = {S’→S• }

A₂= GOTO(A₀, ( )=GOTO({S→•(F:L)}, ( ) = {S→(•F:L), F→•L*, F→•i, L→•F }

A₃=GOTO(A₂, F)=GOTO( {S→(•F:L), L→•F}, F)= {S→(F•:L), L→F• }

A₄= GOTO(A₂, L)=GOTO({F→•L*}, L) = {F→L•*}

A₅= GOTO(A₂, i)=GOTO({F→•i}, i ) = {F→i•}

A₆=GOTO(A₃,:)=GOTO( {S→(F•:L)}, :)= {S→(F: •L), L→•F}

A₇=GOTO(A₄,*)=GOTO( { F→L•*}, *)= {F→L*•}

A₈=GOTO(A₆, L)=GOTO( {S→(F: •L)}, L)= {S→(F:L•)}

A₉=GOTO(A₆, F)=GOTO( { L→•F}, F)= {L→F•}

A₁₀=GOTO(A₈, ) )=GOTO( {S→(F: L•)}, ) )= {S→(F:L) •}

A0	S’→•S S→•(F:L)
A1	S’→•S
A2	S→(•F:L) F→•L* F→•i L→•F
A3	S→(F•:L) L→F•
A4	F→L•*
A5	F→i•
A6	S→(F: •L) L→•F
A7	F→L*•
A8	S→(F:L•)
A9	L→F•
A10	S→(F:L) •

13. Для LR(k) -грамматики cпроектировать матрицу oblow Вычисление отношения OBLOW для грамматических вхождений грамматики G’ . Матрица отношения OBLOW имеет вид:

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

OFIRST(Y_j)=( Y_j)

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

X_i OBLOW Y_j – это множество и Y_j OFIRST(Z_i)}

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

Отношение OBLOW будем задавать с помощью матрицы, содержащей n столбцов и (n+1) строк.

(0) S’→S₀

1. S→(₁ F₁ :₁ L₁ )₁

2. F→ L₂ *₂

3. F→ i₃

4. L→F₄

	S’	S0	(1	F1	:1	L1	)1	L2	*2	i3	F4
S’
S0
(1				1				1		1	1
F1					1
:1						1		1		1	1
L1							1
)1
L2									1
*2
i3
F4
┴	1	1	1