Преобразования КС-грамматик
Рассмотрим ряд преобразований, позволяющих "улучшить" вид контекстно-свободной грамматики без изменения порождаемого ею языка.
Назовем символ недостижимым в КС- грамматике G = (N, T, P, S), если X не появляется ни в однойвыводимой цепочке этой грамматики. Иными словами, символ X является недостижимым, если в G не существует вывода ни для каких .
Назовем символ несводимым (бесплодным) в той же грамматике, если в ней не существует вывода вида X =>* xwy, где w, x, y принадлежат T*.
Очевидно, что каждый недостижимый и/или несводимый символ является бесполезным, как и все правила, его содержащие.
При внимательном изучении вышеприведенных определений становится понятным, что а) целесообразно искать не непосредственно сами недостижимые (или несводимые) символы, а последовательно определять множество достижимых (или сводимых) символов, начиная с тех, которые по определению являются достижимыми (аксиома) и сводимыми (терминалы) - все остальные символы оказываются бесполезными, б) одновременное определение достижимых и сводимых символов невозможно, так как соответствующие процессы идут в противоположных направлениях (от корня к листьям и наоборот).
Алгоритм 4.1. Устранение недостижимых символов.
Вход. КС-грамматика G = (N, T, P, S).
Выход. КС-грамматика G' = (N', T', P', S) без недостижимых символов, такая, что L(G') = L(G).
Метод. Выполнить шаги 1-4:
(1) Положить V0 = {S} и i = 1,
(2) Положить Vi = {X | в P есть и ,
(3) Если , положить i = i + 1 и перейти к шагу 2, в противном случае перейти к шагу 4,
(4) Положить . Включить в P' все правила из P, содержащие только символы из Vi.
Алгоритм 4.2. Устранение несводимых символов.
Вход. КС-грамматика G = (N, T, P, S).
Выход. КС-грамматика G' = (N', T', P', S) без несводимых символов, такая, что L(G') = L(G).
Метод. Выполнить шаги 1-4:
(1) Положить N' = T и i = 1,
(2) Положить ,
(3) Если , положить i = i + 1 и перейти к шагу 2, в противном случае положить Ne = Ni и перейти к шагу 4,
(4) Положить , где P1 состоит из правил множества P, содержащих только символы из ,
Чтобы устранить все бесполезные символы, необходимо применить к исходной грамматике сначала Алгоритм 4.2, а затем Алгоритм4.1.
Пример. Все символы следующей грамматики
S -> AS | b
A -> AB
B -> a
являются достижимыми. Поэтому нарушение предложенного порядка применения к ней алгоритмов приведет лишь к частичному решению задачи.
КС-грамматика без бесполезных символов называется приведенной. Легко видеть, что для любой КС-грамматики существует эквивалентная приведенная. В дальнейшем будем предполагать, что все рассматривамые грамматики - приведенные.
Дата добавления: 2016-06-13; просмотров: 963;