Теория и реализация языков программирования



         

Преобразования КС-грамматик


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

Назовем символ

X \in (N \cup T)
недостижимым в КС- грамматике G = (N, T, P, S), если X не появляется ни в одной выводимой цепочке этой грамматики. Иными словами, символ X является недостижимым, если в G не существует вывода S
*
X? ни для каких
\alpha, \; \beta \in (N \cup T)^*
.

Назовем символ

X \in (N \cup T)
несводимым (бесплодным) в той же грамматике, если в ней не существует вывода вида 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 есть A

X? и
A \in V_{i-1} \} \cup V_{i-1}
,

(3) Если Vi

Vi-1, положить i = i + 1 и перейти к шагу 2, в противном случае перейти к шагу 4,

(4) Положить N' = Vi

N, T' = Vi
T. Включить в 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) Положить

N_i = \{A \! \mid \!A \rightarrow \alpha \in P \; \text{и} \; \alpha \in (N_{i-1})^*\} \cup N_{i-1}
,

(3) Если Ni

Ni-1, положить i = i + 1 и перейти к шагу 2, в противном случае положить Ne = Ni и перейти к шагу 4,




Содержание  Назад  Вперед