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

Построение управляющей таблицы

Дополним исходную грамматику правилом S’ ®S, тем самым получим пополненную грамматику G’ = <T, N’, S’, R’ >:

T { a, (, ), , }, N’ = { S’, S, R}, R = { S’®S, S ® a, S ® (SR, R ® ,SR, R ® )};

Пронумеруем правила:

0. S’®S

1. S ® a

2. S ® (SR

3. R ® ,SR

4. R ® )

Рассмотрим правило с №2: (₂OBLOWY_jдля всех Y_jϵ OFIRST(S₂).

Из Sможно вывести цепочки S®a; S® (SR.

Следовательно, OFIRST(S₂) = { a₁, (₂, S₂} и(₂OBLOW a₁, (₂OBLOW (₂, (₂OBLOW S₂.

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

 

	S0	a1	(2	S2	R2	,3	S3	R3	)4
S0
a1
(2		+	+	+
S2					+	+			+
R2
,3		+	+				+
S3						+		+	+
R3
)4
┴	+	+	+

 

 

Определим функцию переходов g(X): используя отношение OBLOW, построим таблицу переходов конечного автомата.

g(X)	S	R	a	(	)	,
S0
a1
(2	S2		a1	(2
S2		R2			)4	,3
R2
,3	S3		a1	(2
S3		R3			)4	,3
R3
)4
┴	S0		a1	(2

 

Получившаяся таблица переходов соответствует детерминированному автомату, тогда множеству магазинных символов соответствует первый столбец таблицы.

Определим функции действия f(a). Построим таблицу, содержащую по одной строке для каждого магазинного символа и по одному столбцу для каждого символа aϵ (T˅ {ε})

f(a)	a	(	)	,	ε
S0					Д
a1	С,1	С,1	С,1	С,1	С,1
(2	П	П	П	П
S2	П	П	П	П
R2	С,2	С,2	С,2	С,2	С,2
,3	П	П	П	П
S3	П	П	П	П
R3	С,3	С,3	С,3	С,3	С,3
)4	С,4	С,4	С,4	С,4	С,4
┴	П	П	П	П

 

Контрольный пример –разбор цепочки «(а, а, а)» принадлежащей языку.

(┴, (a,a,a) ,ε)

(┴(₂ , a,a,a),ε)

(┴(₂a₁, ,a,a), ε)

(┴(₂S₂, ,a,a), 1)

(┴(₂S₂,₃ , a,a), 1)

(┴(₂S₂,₃a₁, , a), 1)

(┴(₂S₂,₃S₃, ,a), 11)

(┴(₂S₂,₃S₃,₃ ,a), 11)

(┴(₂S₂,₃S₃,₃a₁, ), 11)

(┴(₂S₂,₃S₃,₃S₃, ), 111)

(┴(₂S₂,₃S₃,₃S₃), ε, 111)

(┴(₂S₂,₃S₃,₃S₃R₃, ε, 1114)

(┴(₂S₂,₃S₃R₃, ε, 11143)

(┴(₂S₂R₂, ε, 111433)

(┴S₀, ε, 1114332)

ДОПУСК.

 

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

Усовершенствуем алгоритм 8.2 построения управляющей таблицы так, чтобы получить анализатор для некоторого класса грамматик, не принадлежащих классу LR(0)-грамматик. Этот класс грамматик является подклассом LR(1)-грамматик и получил название SLR(1)-грамматик без e-правил. Буква Sв названии грамматики является сокращением английского слова Simple (простой).

Начнем с рассмотрения примера.

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

(0)	E¢	à	E
(1)	E	à	E + T		(4)	T	à	P
(2)	E	à	T		(5)	P	à	(E)
(3)	T	à	T*P		(6)	P	à	i

В процессе построения анализатора получаем:

q матрицу отношения OBLOW, определенную на множестве грамматических вхождений пополненной грамматики:

E0

E1

+1

T1

T2

T3

*3

P3

P4

(5

E5

)5

i6

E0

E1

+1

T1

T2

T3

*3

P3

P4

(5

E5

)5

i6

^

 

 

таблицу переходов недетерминированного конечного автомата:

	+	*	(	)	i	E	T	P
^			(5		i6	E0, E1	T2, T3	P4
E0
E1	+1
+1			(5		i6		T1, T3	P4
T1
T2
T3		*3
*3			(5		i6			P3
P3
P4
(5			(5		i6	E1, E5	T2, T3	P4
E5
)5				)5
i6

q таблицу переходов детерминированного конечного автомата:

	+	*	(	)	i	E	T	P
{^}			{(5}		{i6}	{E0, E1}	{T2, T3}	{P4}
{(5}			{(5}		{i6}	{E1, E5}	{T2, T3}	{P4}
{i6}
{E0, E1}	{+1}
{T2, T3}		{*3}
{P4}
{E1, E5}	{+1}			{)5}
{+1}			{(5}		{i6}		{T1, T3}	{P4}
{*3}			{(5}		{i6}			{P3}
{)5}
{T1, T3}		{*3}
{P3}

q таблицу кодирования магазинных символов:

{Eo,E1}

{E1,E5}

{T2,T3}

{T1,T3}

{P3}

{P4}

{+1}

{*3}

{(5}

{)5}

{i6}

{^}

Vp

Ex

Ey

Tx

Ty

P3

P4

+1

*3

(5

)5

i6

^

 

 

q таблицу функций переходов g(X):

g(X)	+	*	(	)	i	E	T	P
^			(5		i6	Ex	Tx	P4
(5			(5		i6	Ey	Tx	P4
i6
Ex	+1
Tx		*3
P4
Ey	+1			)5
+1			(5		i6		Ty	P4
*3			(5		i6			P3
)5
Ty		*3
P3

Выполняя шаг 4 алгоритма, обнаруживаем, чтоG_o не принадлежит классу LR(0)-грамматик, так как множества грамматических вхождений, соответствующие магазинным символам Т_x и T_y, содержат самые правые вхождения символа Т и не являются одноэлементными.

Покажем, как, сделав некоторый дополнительный анализ, можно определить функции действия f(a) для данной грамматики. Анализ выполняется для каждого элемента отроки таблицы отдельно и использует текущий входной символ (k = 1).

Рассмотрим, например, элемент управляющей таблицы для магазинного символа Т_x, которому соответствует множество грамматических вхождений {Т₂, Т₃}. Наличие в Т_x самого правого вхождения Т₂ в правило вывода (2) говорит о том, что необходимо выполнить операцию (СВЕРТКА, 2), а тот факт, что в Т_x содержится T₃, свидетельствует в пользу операции ПЕРЕНОС.

Допустим, что входным символом является символ «+». Для магазинного символа Т_x функция g(+) = ОШИБКА, поэтому втолкнуть его в магазин невозможно, и, следовательно, для допустимых входных цепочек в строке Т_x функции действий должно быть значение f(+) = (СВЕРТКА, 2).

Для входного символа «*» функция переходов g(*) = *₃, значит, при анализе допустимых входных цепочек перенос в магазин символа «*» будет правильным действием. Выполнение операции (СВЕРТКА, 2) в этом случае привело бы к тому, что в магазин был бы помещен магазинный символ, представляющий нетерминал Е. Так как входным символом при этом остается «*», то на следующем шаге был бы выработан сигнал об ошибке, поскольку символ «*» не может непосредственно следовать за Е («*» не принадлежит множеству Follow(Е)). Таким образом, операция (СВЕРТКА, 2) исключается, и в строке управляющей таблицы, помеченной Т_x , f(*) = ПЕРЕНОС.

Принципы, продемонстрированные при выполнении данного примера, позволяют на основе алгоритма 8.2 сформулировать алгоритм построения управляющей таблицы для SLR(1)-грамматик.

Алгоритм 8.3.Построение множества SLR(1)-таблиц.

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

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