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

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

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

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

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

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

Определение. Назовем нетерминальный символ A выводимым (достижимым), если существует S  *  A  и производящим, если A*,   V* ,  и  - произвольные цепочки,  - терминальная цепочка.

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

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

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

S  ,   (V  W)*.

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

2. M_i = M₁.

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

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

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

A  , A  M_i ,   ( 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 имеются правила вида:

  ,   V*, A  W.

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

2. Q_i = Q₁ .

3. Q_i-+1 = Q_i  Q_i‘, где Q_i‘ - множество нетерминальных символов левых частей правил, для которых в грамматике имеются правила вида: 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. В грамматике выделяют не цепные правила вида:

  ,   W.

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

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

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 }.

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