В множестве Р правил грамматики G непродуктивным называют нетерминал из которого нельзя получить цепочку терминалов. Для поиска в множестве правил непродуктивных нетерминалов используется следующее свойство:
Свойство А: Если все символы правой части правила продуктивны, то продуктивен и символ, стоящий в его левой части.
Процедура поиска непродуктивных нетерминалов в множестве правил P грамматики G:
- составить список нетерминалов для которых найдется хотя бы одно правило, правая часть которого состоит только из терминалов;
- если найдется такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал стоящий в его левой части;
- если на предыдущем шаге список не пополняется, то уже получен исчерпывающий список всех продуктивных нетерминалов.
Hетерминалы грамматики не попавшие в список, построенный приведенному выше алгоритму, являются непродуктивными и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.
В множестве правил недостижимым называют нетерминал, который не может быть получен в процессе вывода. Для поиска недостижимых нетерминалов используется следующее свойство:
Свойство Б: Если нетерминал в левой части правила является достижимым, то достижимы все нетерминалы, стоящие в правой части этого правила.
Процедура поиска недостижимых нетерминалов в множестве правил P грамматики G:
- образовать одноэлементный список из начального нетерминала;
- если найдено правило, левая часть которого уже в списке,
то включить в список все нетерминалы из его правой части;
- если на предыдущем шаге список не пополняется, то уже получен исчерпывающий список всех достижимых нетерминалов.
Hетерминалы грамматики не попавшие в список, построенный по приведенному выше алгоритму, являются недостижимыми и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.
Hе нарушая эквивалентности,можно также исключить правила такого вида: A -> A
A -> B, B -> C, C -> A (циклический блок правил).
Пример : Задана грамматика G
P = { S -> aS, (1)
S -> aA, (2) VN = { S, A, B, C, D };
A -> bB, (3) VT = { a, b, c, d };
A -> bC, (4)
B -> d, (5) Начальный символ - S.
D -> c (6) };
Упростить исходную грамматику G.
Решение
1. Поиск непродуктивных нетерминалов :
Используя правила (5) и (6), заносим в список продуктивных нетерминалы B, D. Затем по правилу (3) - A, затем по правилу (2)
- S, далее список не пополняется. Получен полный список продуктивных нетерминалов - { B, D, A, S}. Hепродуктивный символ С (правило (4) можно исключить).
2. Поиск недостижимых нетерминалов :
Первым в список вносим начальный символ грамматики S, затемна основании правила (2) дополняем список нетерминалом A; правило(3) дает основания внести в список нетерминал В. Дальнейшие действия в соответствии с алгоритмом список нетерминалов не пополняют. Полученный список выглядит так {S,A,B}.
Hедостижимый нетерминал D. Правило (6) из множества правил грамматики S можно исключить.
В результате этих преобразований получаем эквивалентную грамматику S1: VN = {S, A, B}; VT = {a, b, d}; начальный символ S; P = { S -> aS (1)
S -> aA (2)
A -> bB (3)
B -> d }. (4)