Приведение грамматик

Для одного и того же формального языка могут существовать различные грамматики. Поэтому возникает проблема выбора грамматики, наиболее подходящей по тем или иным свойствам, иначе проблема эквивалентного преобразования грамматик к нужному виду. Желаемые свойства могут быть такими как:

* однозначность;

* минимальное число правил или нетерминальных символов;

* простота вывода.

Универсальных методов эквивалентных преобразований контекстно-свободных грамматик (КСГ) не существует из-за неразрешимости алгоритмических проблем распознавания эквивалентности контекстно-свободных грамматик и существенной неоднозначности контекстно-свободных языков. Однако, существуют некоторые преобразования, которые могут улучшать грамматику.

Определение. Назовем нетерминальный символ A выводимым (достижимым), если существует S ® * a A b и производящим, если A®*g, g Î V*, a и b - произвольные цепочки, g - терминальная цепочка.

Определение. Нетерминальный символ называется существенным, если он является достижимым и производящим. В противном случае, он называется несущественным (бесполезным).

Покажем, что для любой КСГ можно построить эквивалентную ей приведенную контекстно-свободную грамматику. Для этого рассмотрим алгоритм выделения достижимых символов:

1. Обозначим через M₁ множество всех нетерминальных символов, содержащихся в правых частях правил вида:

S ® a, a Î (V È W)*.

Очевидно, что все символы M₁ достижимы.

2. M_i = M₁.

3. Определим M_i-+1 = M_i È M_i’, как множество, состоящее из

объединения множеств M_i и M_i’, где M_i’ - множество всех

нетерминальных символов правых частей правил вида:

A ® a, A Î M_i, a Î (V È W)*.

4. M_i+1 ¹ M_i? Если - да, то M_i = M_i+1 и переход к п. 3.

5. Окончание алгоритма.

Массив M_i+1 - множество достижимых символов и его размерность

k £ êW ê.

Пример. Для заданной грамматики вида:

S ®a B a C ® b B

B ® a B C a C ® a C

B ® b

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

Решение. Найдем множества M_i для заданной грамматики в соответствии с представленным алгоритмом. Ими будут множества

M₁ = {B, S}, M₂ = M₁ È {C}, M₃ = M₂ = {B, S, С} - множество достижимых символов.

Пример. Для заданной грамматики вида:

S ®A B A C ® b b

B ® A B C A D ® D A

B ® b D ® C A

A ® a

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

Решение. Найдем множества M_i для заданной грамматики в соответствии с представленным алгоритмом. Ими будут множества M₁ = {A, B, S}, M₂ = M₁ È {C}, M₃ = M₂ = {A, B, S, С} - множество достижимых символов. D - недостижимый символ, а значит бесполезный.

Замечание. Нетерминальный символ, соответствующий аксиоме грамматики, всегда считается достижимым.

Рассмотрим алгоритм выделения производящих символов. Он работает с конца вывода.

1. Обозначим через Q₁ множество всех нетерминальных символов, для которых в G имеются правила вида:

A ® g, g Î V*, A Î W.

Все символы множества Q₁ - производящие.

2. Q_i = Q₁.

3. Q_i-+1 = Q_i È Q_i‘, где Q_i‘ - множество нетерминальных символов левых частей правил, для которых в грамматике имеются правила вида: A ® a, a Î (V È Q_i)*.

4. Если Q_i+1 ¹ Q_i, то Q_i = Q_i+1 и переход к пункту 3.

5. Окончание алгоритма.

Q_i+1 - множество производящих символов. Его мощность

m £ êW ê.

Пример. Для заданной грамматики вида:

S ®A D A C ® b b

S ® B A ® D C

D ® A B c A D ® D A

D ® C A A ® a.

определить множество производящих символов.

Решение. Найдем множества Q_i для заданной грамматики в соответствии с представленным алгоритмом. Ими будут множества Q₁ = {A, С}, Q₂ = Q₁ È{D, S}, Q₃ = Q₂ = {A, D, S, С} - множество производящих символов. B - непроизводящий символ, а значит бесполезный.

После преобразования грамматики по вышеописанным алгоритмам получаем грамматику, не содержащую бесполезные (несущественные) символы.

Удаление цепных правил

Цепные правила - это правила вида: A ® B, A, B Î W. Назначение процедуры удаления цепных правил состоит в сокращении памяти требуемой под дерево вывода. Эта процедура состоит из 2-х этапов:

1. Для каждого нетерминального символа A Î W составляется множество W_A, состоящее из нетерминальных символов, выводимых из A, причем A Î W_A .

2. В грамматике выделяют не цепные правила вида:

b ® a, a Ï W.

Они записываются в новую грамматику для каждого b Î W_A , для которого существует выводимость a из b.

Пример. Для заданной грамматики вида:

G = {V, W, A, P}; V={a}; W={A, B, C};

P = { A ® B, B ® C, C ® a }

удалить цепные правила, сохранив основные свойства грамматики.

Решение. Найдем множества W_i для заданной грамматики в соответствии с представленным алгоритмом. Ими будут множества:

W_A = {A, B, C}; W_B = { B, C }; W_C ={ C }_.

Что позволяет записать новые правила грамматики, в которых нет цепных правил, но сохраняется порождаемый формальный язык.

P’= {A®a, B®a, C®a}.

Пример. Для заданной грамматики вида:

G = {V, W, I, P}; V = {a, b}; W = { A, B, C, D, I };

P = { I ® A, A ® a C, I ® B, B ® C, C ® D, D ® b }

удалить цепные правила, сохранив основные свойства грамматики.

Решение. Найдем множества W_i для заданной грамматики в соответствии с представленным алгоритмом. Ими будут множества:

W_I = { I, A, B, C, D }; W_A = { C, D };

W_B ={ C, D }; W_C = { D }.

Что позволяет записать новые правила грамматики, в которых нет цепных правил, но сохраняется порождаемый формальный язык.

P’ = { I ® a C, A ® a C, I ® b, B ® b, C ® b, D ® b }.

Замечание. Достоинство грамматик без цепных правил состоит в отсутствии циклов в выводах и ни одна цепочка в выводе не повторяется.