Удаление или добавление бесполезных

(непродуктивных и недостижимых) нетерминалов

В множестве Р правил грамматики G непродуктивным называют нетерминал, из которого нельзя получить цепочку терминалов. Для поиска в множестве правил непродуктивных нетерминалов используется следующее свойство.

Свойство А: Если все символы правой части правила продуктивны, то продуктивен и символ, стоящий в его левой части.

Алгоритм поиска непродуктивных нетерминалов в множестве правил P грамматики G:

– составить список нетерминалов для которых найдется хотя бы одно правило, правая часть которого состоит только из терминалов;

– если найдется такое правило, что все нетерминалы, стоящие

в его правой части уже занесены в список, то добавить в список нетерминал стоящий в его левой части;

– если на предыдущем шаге список не пополняется, то получен исчерпывающий список всех продуктивных нетерминалов.

Hетерминалы грамматики не попавшие в список, построенный по приведенному выше алгоритму, являются непродуктивными и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.

В множестве правил грамматики недостижимым называют нетерминал, который не участвует в процессе вывода. цепочек. Для поиска недостижимых нетерминалов используется следующее свойство.

Свойство Б Если нетерминал в левой части правила является достижимым, то достижимы все нетерминалы, стоящие в правой части этого правила.

Алгоритм поиска недостижимых нетерминалов в множестве правил P грамматики G:

– образовать одноэлементный список из начального нетерминала грамматики;

– если в множестве Р найдено правило, левая часть которого уже в списке, то включить в список все нетерминалы из его правой части;

– если на предыдущем шаге список не пополняется, то получен исчерпывающий список всех достижимых нетерминалов.

Hетерминалы грамматики не попавшие в список, построенный по приведенному выше алгоритму, являются недостижимыми и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.

Не нарушая эквивалентности, можно также исключить правила такого вида:

A à A или A à B, B à C, C à A (циклический блок правил).

Пример: Задана грамматика G[S]: VN = {S, A, B, C, D};

VT = {a, b, c, d}; P = {S à aS (1), S à aA (2), A à bB (3),

A à bC (4), B à d (5) D à c (6) }.

Упростить заданную грамматику.