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

Исключение бесполезных символов

Исключение бесполезных символов

Алгоритм 3.7.1.1. Определение множества производящих нетерминальных символов КС-грамматики.

Вход.КС-грамматика G = (N, S, P, S).

Выход.Множество производящих нетерминальных символов N_p = {A | A Þ⁺ x, A Î N, x Î S⁺}.

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

Построить рекурсивно множества производящих нетерминалов N⁰_p, N¹_p, … , Nⁱ_p, … следующим образом:

1. Положить N⁰_p = Æ, i = 1.

2. Положить Nⁱ_p = N^i-1_p È {A | A à a Î P, a Î (N^i-1_p È S)⁺}

3. Если Nⁱ_p ¹ N^i-1_p, положить i = i + 1 и перейти к шагу 2.

4. Положить N_p = Nⁱ_p.

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

Алгоритм3.7.1.2. Определение множества достижимых символов КС-грамматики.

Вход.КС-грамматика G = (N, S, P, S).

Выход.Множество достижимых символов N_r = {X | S Þ^* aXb, X Î (S È N), a, b Î (S È N)^*}.

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

Построить рекурсивно множества достижимых символов N⁰_r, N¹_r, … , Nⁱ_r, … , следующим образом:

1. Положить N⁰_r = {S}, i = 1.

2. Положить Nⁱ_r = N^i-1_r È {X | A à aXb Î R и A Î N^i-1_r }.

3. Если Nⁱ_r ¹ N^i-1_r, положить i = i + 1 и перейти к шагу 2.

4. Положить N_r = Nⁱ_r.

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

Алгоритм 3.7.1.3. Устранение бесполезных символов.

Вход.КС-грамматика G = (N, S, P, S), для которой L(G) ¹ Æ.

Выход.КС-грамматика G = (N¢, S¢, P¢, S), у которой L(G) ¹ Æ и в S¢ È N¢ нет бесполезных символов.

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

1. Построить множество N_p производящих нетерминалов грамматики G.

2. Положить G₁ = (N_p, S, P_1, S,), где P₁ состоит из правил множества P, содержащих только символы из S È N_p.

3. Построить множество N_r достижимых символов грамматики G₁.

4. Положить G¢= (N¢, S¢, P¢, S,) , где S¢ = S Ç N_r, N¢ = N_r Ç N, а P¢ состоит из правил множества P₁ , содержащих только символы из множества N_r.

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

Пример 3.7

Исключить из грамматики G = (N, S, P, S), где N = {А, В. С. S}, S = {a, b, c}, P = {S à аС, S à А, А à сАВ, В à b, С à а}, бесполезные символы.

После выполнения шага 1 алгоритма 3.7.1.3 множество N_p = {В, С, S}.

После исключения непроизводящих нетерминалов получим новую грамматику G₁ = ({В, С, S}, {a, b, с}, P, S), где P = { S à аС, В à b, С à а}.

Множество достижимых символов грамматики G₁ N_r = {a, C, S}.

После исключения множества недостижимых символов из грамматики G₁ получим грамматику G¢ = ({С, S}, {a}, {S à аС, С à а}, S), L(G¢) = {aa}.

Если применить к исходной грамматике сначала алгоритм 3.7.1.2, то получим, что все символы достижимы. Множество производящих символов грамматики G₁ = {В, С, S }. После исключения непроизводящих символов из грамматики G₁ имеем G¢ = ({В, С, S}, {a, b, с}, P¢, S ), где P¢ = {S à аС, В à b, С à а}, L(G¢) = L(G) = {aa}, но грамматика G¢ содержит бесполезные символы B и b.

Исключение бесполезных символов

Задание.

2.2.1.3. T = { a, b, c, d, e, f }, N = { A, B, C, S }, R = { S ® b, S ® C, S ®cCB, A ® e, A ®Ab, B ® Bb, B ®cB, C ®Ca, C ® Bf, C ® d };

Решение:

1. Построим множество N_Pпроизводящих нетерминалов грамматики G.

2. Определим множество достижимых символов.

Новая грамматика, эквивалентная исходной имеет следующий вид:

G’ = <T’, N’, S, R’>

T’= { a, b, c, d, f}; N’ = { S, B, C}; R’= {S ® b, S ® C, S ®cCB, B ® Bb, B ®cB, C ®Ca, C ® Bf, C ® d }

 

 

Исключение бесполезных символов

 

Преобразовать КС-грамматику G = < T, N, S, R > в эквивалентную грамматику, не содержащую бесполезных символов:

2.2.1.3. T = { a, b, c, d, e, f }, N = { A, B, C, S }, R = { S ® b, S ® C, S ® cCB, A ® e, A ® Ab, B ® Bb, B ® cB, C ® Ca, C ® Bf, C ® d };

 

1. множество производящих нетерминалов N_p={C,A,S}

- N⁰ = 0

- A ® e, C ® d , S ® b -> значит N¹={S,A,C}

- N² = {S,A,C}, т.к. больше нет правил вывода X®a,aÎ{ a, b, c, d, e, f ,S,A,C}

- N_p={C,A,S}

2. Искючим из грамматики правила, содержащие непроизводящие нетерминалы

R’={ S ® b, S ® C, A ® e, A ® Ab, C ® Ca, C ® d }

G1=( T, N_p, S, R’)

3. Множество достижимых символов N_r = {d,a,b,S,C}

- N⁰={S}

- N¹={S,b,C}, из правил S ® b, S ® C

- N²={S,b,C,a,d} из правил C ® Ca, C ® d

- N³={S,C,b,a,d}.

- N_r = {d,a,b,S,C}

4. Исходная грамматика без бесполезных символов будет выглядеть следующим образом.

N’={S,C}, T’={a, b, d}, R’’={ S ® b, S ® C, C ® Ca, C ® d }

G = < T’, N’, S, R’’ >