Удаление из грамматики бесполезных нетерминалов

В произвольно заданной грамматике могут присутствовать такие нетерминалы (и порождающие правила, где эти нетерминалы присутствуют), которые бесполезны: они или никогда не могут появиться при любом процессе порождения, начинающегося с начального нетерминала, или никогда не могут породить терминальной цепочки. Назовем их в первом случае бесполезными 1-го типа, а во втором – бесполезными 2-го типа.

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

Для того чтобы избавиться от бесполезных нетерминалов 2-го типа, просмотрим порождающие правила, у которых правая часть пуста или состоит только из терминалов. Пометим нетерминалы в левой части этих правил, как полезные. Далее для всех порождающих правил, у которых в правой части имеются только полезные нетерминалы и (возможно) терминальные символы, пометим все нетерминалы в левой части, как полезные. Процесс продолжаем, пока не останется непросмотренных порождающих правил. Все нетерминалы, оставшиеся непомеченными, являются бесполезными 2-го типа, их следует удалить вместе с теми правилами грамматики, где они встречаются.

Очищенная от бесполезных нетерминалов грамматика называется приведенной. Заметим, что рассмотренный способ удаления бесполезных нетерминалов можно применить не только к А-грамматикам, но и к КС-грамматикам.

Дата добавления: 2015-07-26; просмотров: 163; Нарушение авторских прав

Мы поможем в написании ваших работ!