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

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

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

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

Например, рассмотри правила для нетерминала А

А®А А½ В А

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

1. Построение множества производящих нетерминалов N_R:
1. Строится множество N_R¹ = {A/ A®b_j,b_jÎV_T}
2. Последовательно строятся множества N_Rⁱ⁺¹={ A/ A®b_j,b_jÎ(N_RⁱÈV_T)*} до тех пор, пока получим N_Rⁱ⁺¹= N_Rⁱ или же N_Rⁱ= V_N. Тогда N_R = N_Rⁱ.
2. Исключаем из грамматики все правила, в правых частях которых нетерминалы из V_N\ N_R.
3. Исключаем из грамматики правые части правил, в которых присутствуют нетерминалы из 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_T,V_N, S, R>, строится эквивалентная грамматика без непроизводящих символов G’ =< V_T,V_N’, S, R’>.

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

2. Итерационное построение множества D: D_i+1= D_iÈ{A/B®aAbÎR&BÎ D_i}

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

R’={ R_i / R_i=(A®j), AÎ V_N’,jÎ(V_N’È V_T) * }

Построенная грамматика не содержит недостижимых нетерминалов.

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

S® A C ½B C

A® AD½ DF

D® aA ½ D A

F® b F½l

B® bB½a

С®сС½d

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

9.3. Устранение l - правил

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

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

1. Построить множество N_l = { A / A Þ⁺ l } - множество нетерминальных символов, из которых возможен вывод пустой цепочки. Множество N_l строится итерационно. На первом шаге строится N_l⁰.

N_l⁰ = { B / B ® l Î R}

Пусть построено N_l¹, N_l²,..., N_lⁱ, (i ³ 0). Тогда N_lⁱ⁺¹ = N_lⁱ È{ B / B ® j Î R & j Î (N_lⁱ)* }.

Если на очередном шаге N_lⁱ⁺¹ = N_lⁱ, то искомое множество N_l найдено (N_l = N_lⁱ ).

2. Построить R’ — множество правил эквивалентной грам­матики так, что:

a) Если A®a₀ B₁ a₁ B₂ ... B_k a_k Î R, k ³ 0 и B_i Î N_l для 0 £ i £ k, но ни один символ в цепочках a_j, 1 £ j £ k не содержит символа из N_l, то включить в R’ все правила вида

A ® a₀X₁a₁X₂...X_ka_k

X_i либо B_i, либо l (при этом правило A ® l не вклю­чать; это могло бы произойти, если все a_i = l).

b) если S Î N_l, включить в R’ также правило S’® S½l где S’ - новый начальный символ.

Таким образом, любая КС—грамматика может быть приве­дена к виду, когда R не содержит l -правил, либо есть точно одно правило S’ ® l и S’ не встречается в правых частях остальных правил из R. Такие грамматики будем называть неукорачивающими.

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

S®A B½ BC

A® aAb ½l

B® dB½c

C® CC½Ac½l

N_l⁰= {A, C}

N_l¹= {A, C}= N_l. Поскольку lÏL(G) (SÏ N_l), правила грамматики примут вид

S®A B ½B½ BC

A® aAb ½ab

B® dB½c

C® CC½Ac½a½ c

Б. Устранение правил А ® В (цепных правил)

Применение цепных правил приводит к увеличению длины ветвей синтаксического дерева, исключение цепных правил часто приводит к большей «прозрачности» грамматики и уменьшению длины выводов, которые можно построить. Алгоритм исключения цепных правил:

1. Для каждого AÎ V_N построить N_A = { B / A ® B },т.е. множество нетерминальных символов, выводимых из данного символа. Процедура построения следующая:

а) положить N_A⁰ ={A}.

б) пусть построены N_A⁰, N_A¹... N_Aⁱ . Тогда

N_Aⁱ⁺¹ = { C / B ® C Î R & B Î N_Aⁱ } È N_A⁰.

Если на очередном шаге N_Aⁱ⁺¹ = N_Aⁱ, то положить N_A = N_Aⁱ.

2. Построить R’ (множество правил эквивалентной грамматики) так: если B ® a Î R и не является цепным правилом, то включить в R’ правила A ® a. для всех таких A, что

B Î N_A.

Рассмотрим пример. Пусть множество правил грамматики имеет вид:

S®T+S½T

T® M*T½M

M® (S)½ i

Простроим для данной грамматики множества N_A

N_S ={S, T, M}

N_T = {T, M}

N_M = {M}

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

S®T+S½ M*T½(S)½ i

T® M*T ½(S)½ i

M® (S)½ i

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

Грамматика называется неукорачивающей, если для любого правила грамматики j®y выполняется½j½£½y½. Такое определение применимо как к КС-грамматикам, так и к КЗ-грамматикам. А-грамматика так же может быть неукорачивающей. Для КС и А-грамматик необходимым и достаточным условием принадлежности к классу неукорачивающих грамматик является отсутствие в них l-правил.

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

Поэтому, если lÏL(G), то существует приведенная грамматика G₁, такая, что L(G₁)=L(G).

В случае же lÎL(G), существует эквивалентная грамматика с единственным укорачивающим правилом.