Приведение грамматик
Для одного и того же формального языка могут существовать различные грамматики. Поэтому возникает проблема выбора грамматики, наиболее подходящей по тем или иным свойствам, иначе проблема эквивалентного преобразования грамматик к нужному виду. Желаемые свойства могут быть такими как:
* однозначность;
* минимальное число правил или нетерминальных символов;
* простота вывода.
Универсальных методов эквивалентных преобразований контекстно-свободных грамматик (КСГ) не существует из-за неразрешимости алгоритмических проблем распознавания эквивалентности контекстно-свободных грамматик и существенной неоднозначности контекстно-свободных языков. Однако, существуют некоторые преобразования, которые могут улучшать грамматику.
Определение.Назовем нетерминальный символ A выводимым (достижимым), если существует S ® * a A b и производящим, если A®*g, g Î V* , a и b - произвольные цепочки, g - терминальная цепочка.
Определение. Нетерминальный символ называется существенным, если он является достижимым и производящим. В противном случае, он называется несущественным (бесполезным).
Покажем, что для любой КСГ можно построить эквивалентную ей приведенную контекстно-свободную грамматику. Для этого рассмотрим алгоритм выделения достижимых символов:
1. Обозначим через M1 множество всех нетерминальных символов, содержащихся в правых частях правил вида:
S ® a, a Î (V È W)*.
Очевидно, что все символы M1 достижимы.
2. Mi = M1.
3. Определим Mi-+1 = Mi È Mi’, как множество, состоящее из
объединения множеств Mi и Mi’ , где Mi’ - множество всех
нетерминальных символов правых частей правил вида:
A ® a, A Î Mi , a Î ( V È W )*.
4. Mi+1 ¹ Mi ? Если - да, то Mi = Mi+1 и переход к п. 3.
5. Окончание алгоритма.
Массив Mi+1 - множество достижимых символов и его размерность
k £ êW ê.
Пример.Для заданной грамматики вида:
S ®a B a C ® b B
B ® a B C a C ® a C
B ® b
определить множество достижимых символов.
Решение. Найдем множества Mi для заданной грамматики в соответствии с представленным алгоритмом. Ими будут множества
M1 = {B, S}, M2 = M1 È {C}, M3 = M2 = {B, S, С} - множество достижимых символов.
Пример. Для заданной грамматики вида:
S ®A B A C ® b b
B ® A B C A D ® D A
B ® b D ® C A
A ® a
определить множество достижимых символов.
Решение. Найдем множества Mi для заданной грамматики в соответствии с представленным алгоритмом. Ими будут множества M1 = {A, B, S}, M2 = M1 È {C}, M3 = M2 = {A, B, S, С} - множество достижимых символов. D - недостижимый символ, а значит бесполезный.
Замечание. Нетерминальный символ, соответствующий аксиоме грамматики, всегда считается достижимым.
Рассмотрим алгоритм выделения производящих символов. Он работает с конца вывода.
1. Обозначим через Q1 множество всех нетерминальных символов, для которых в G имеются правила вида:
A ® g, g Î V*, A Î W.
Все символы множества Q1 - производящие.
2. Qi = Q1 .
3. Qi-+1 = Qi È Qi‘, где Qi‘ - множество нетерминальных символов левых частей правил, для которых в грамматике имеются правила вида: A ® a, a Î (V È Qi)*.
4. Если Qi+1 ¹ Qi , то Qi = Qi+1 и переход к пункту 3.
5. Окончание алгоритма.
Qi+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.
определить множество производящих символов.
Решение. Найдем множества Qi для заданной грамматики в соответствии с представленным алгоритмом. Ими будут множества Q1 = {A, С}, Q2 = Q1 È{D, S}, Q3 = Q2 = {A, D, S, С} - множество производящих символов. B - непроизводящий символ, а значит бесполезный.
После преобразования грамматики по вышеописанным алгоритмам получаем грамматику, не содержащую бесполезные (несущественные) символы.
Удаление цепных правил
Цепные правила - это правила вида : A ® B, A, B Î W. Назначение процедуры удаления цепных правил состоит в сокращении памяти требуемой под дерево вывода. Эта процедура состоит из 2-х этапов:
1. Для каждого нетерминального символа A Î W составляется множество WA, состоящее из нетерминальных символов, выводимых из A, причем A Î WA .
2. В грамматике выделяют не цепные правила вида:
b ® a, a Ï W.
Они записываются в новую грамматику для каждого b Î WA , для которого существует выводимость a из b.
Пример.Для заданной грамматики вида:
G = {V, W, A, P}; V={a}; W={A, B, C};
P = { A ® B, B ® C, C ® a }
удалить цепные правила, сохранив основные свойства грамматики.
Решение. Найдем множества Wi для заданной грамматики в соответствии с представленным алгоритмом. Ими будут множества:
WA = {A, B, C}; WB = { B, C }; WC ={ 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 }
удалить цепные правила, сохранив основные свойства грамматики.
Решение.Найдем множества Wi для заданной грамматики в соответствии с представленным алгоритмом. Ими будут множества:
WI = { I, A, B, C, D }; WA = { C, D };
WB ={ C, D }; WC = { D }.
Что позволяет записать новые правила грамматики, в которых нет цепных правил, но сохраняется порождаемый формальный язык.
P’ = { I ® a C, A ® a C , I ® b, B ® b, C ® b, D ® b }.
Замечание. Достоинство грамматик без цепных правил состоит в отсутствии циклов в выводах и ни одна цепочка в выводе не повторяется.