9. Преобразования кс-грамматик

В данном разделе приводятся такие преобразования грамматик, которые не выводят нас из класса эквивалентности, т.е. грамматика G₁ таким образом преобразуется в грамматику G₂, чтобы L(G₁)=L(G₂).

9.1 Устранение непроизводящих правил

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

Например, пусть правила для нетерминала А имеют следующий вид и других правил для А нет:

АА А В А

В этом случае, появившись в цепочке, нетерминал А никогда не будет заменен терминальной цепочкой. Естественно, в реальности ситуации бывают не столь простые.

Алгоритм устранения непроизводящих нетерминалов.

Пусть дана грамматика G = < V_N, V_T,S, R>, строится эквивалентная грамматика без непроизводящих символов G’ = < V_N’, V_T, S, R’>.

1. Построение множества производящих нетерминалов N_R:

   1. Строится множество N_R¹ = {A/ A_j, _jV_T*}

   2. Последовательно строятся множества N_Rⁱ⁺¹={ A/ A_j, _j(N_RⁱV_T)*}

   3. Построение продолжается до тех пор, пока не получим N_Rⁱ⁺¹= N_Rⁱ или же N_Rⁱ= V_N. Тогда N_R = N_Rⁱ.

2. Исключаем из грамматики все правила, в которых присутствуют нетерминалы из V_N\ N_R.

Н апример, рассмотрим грамматику G₁₄ с множеством правил

S ABBC;

A AAAB;

B bBa;

СсСd AC.

Построим множество N_R. N_R¹={B,C}, N_R²={S, B, C}, N_R³= N_R²= =N_R.

Правила преобразованной грамматики:

S BC;

B bBa;

СсСd .

9.2. Устранение недостижимых нетерминалов

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

Следует отметить, что такие нетерминалы в грамматиках встречаются в основном тогда, когда исключены некоторые непроизводящие символы, т.е. недостижимым нетерминал становится чаще всего после исключения некоторых непроизводящих символов. Например, если в грамматике правила для нетерминала А: АА А В А, и нетерминал В не встречается в других правых частях правил грамматики, то в этом случае, после устранения нетерминала А нетерминал В становится недостижимым, и, следовательно, его можно исключить из грамматики без изменения порождаемого ей языка. Построение множества недостижимых нетерминалов похоже на построение множества непроизводящих нетерминалов: строится множество всех достижимых нетерминалов, а затем исключаются все остальные нетерминалы грамматики.

Алгоритм преобразования грамматики.

Строится грамматика, в которой используются только достижимые нетерминалы (множество достижимых нетерминалов – D) , выглядит следующим образом:

Пусть дана грамматика G=< V_N, V_T, S, R>, строится эквивалентная грамматика без недостижимых нетерминалов G’ =< V_N’, V_T, S, R’>.

1. Построение множества достижимых нетерминалов:

   1. Начальное значение D₀=S.

   2. Итерационное построение множества D:

D_i+1= D_i  { A/B  AR B D_i}

3. Построение продолжается до тех пор, пока D_i+1= D_i или D_i+1= =V_N, в обоих случаях V_N’= D_i+1,

1. Построение множества правил преобразованной грамматики:

R’={ R_i / R_i=(A), A V_N’, ( V_N’ V_T)*}. Построенная грамматика не содержит недостижимых нетерминалов.

Например, рассмотрим грамматику G₁₅ с множеством правил

S A C B C;

A  AD DF;

D aA  D A;

F b F;

B bBa;

СсСd.

Тогда здесь A и D непроизводящие нетерминалы, после их устранения нетерминал F становится недостижимым, поэтому нетерминалы A, D и F могут быть исключены из грамматики с сохранением языка, порождаемого грамматикой.

Правила преобразованной грамматики:

S  B C

B bBa

СсСd