Алгоритм 4. Устранение цепных правил

Чтобы устранить цепные правила, для каждого нетерминального символа X ÎV_N последовательно строится специальное множество цепных символов N ^X ={B½XÞ^*B} а затем на основании построенных множеств выполняются преобразования правил P.

1. Шаги 2–5 выполнить для всех нетерминальных символов X ÎV_N.

2. N ^X ₀={X}, i:=1.

3. N ^X _i= N ^X _i–1È{B½(A®B)ÎP, AÎ N ^X _i–1}.

4. Пока N ^X _i¹ N ^X _i–1, выполняется i:=i+1 и снова шаг 3.

5. Когда станет N ^X _i=N ^X _i–1, строим N ^X = N ^X _i\{X} и переходим к шагу 2 – к очередному нетерминальному символу, до тех пор, пока они не будут рассмотрены все.

6. Новая грамматика: V_T¢=V_T, V_N¢=V_N, S¢=S, в P¢ входят все правила из P, кроме правил вида A®B.

7. Для всех правил (B®a)ÎP¢, если BÎN ^A, то в P¢ добавляются правила вида A®a.

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

Пример:

Рассмотрим устранение цепных правил для грамматики, построенной в предыдущем примере. Грамматика G({a,b,c},{A,B,C,S},P,S), где P:

S®AaB½aB½cC½Aa½a½c

A®AB½a½b½B

B®Ba½a

C®AB½A½B½c.

Устраним цепные правила. Рассмотрим все нетерминальные символы, начиная с целевого.

1. N ^S ₀={S}, i:=1.

2. N ^S ₁={S}, N ^S ₁=N ^S ₀. N ^S =N ^S ₁\{S}=Æ.

3. N ^A ₀={A}, i:=1.

4. N ^A ₁={A,B}, N ^A ₁¹N ^A ₀, i:=2.

5. N ^A ₂={A,B}, N ^A ₂=N ^A ₁, N ^A =N ^A ₂\{A}={B}.

6. N ^B ₀={B}, i:=1.

7. N ^B ₁={B}, N ^B ₁=N ^B ₀, N ^B =N ^B ₁\{B}=Æ.

8. N ^C ₀={C}, i:=1.

9. N ^C ₁={C,A}, N ^C ₁¹N ^C ₀, i:=2.

10. N ^C ₂={C,A,B}, N ^C ₂¹N ^C ₁, i:=3.

11. N ^C ₃={C,A,B}, N ^C ₃=N ^C ₂, N ^C =N ^C ₃\{C}={A,B}.

Получили: N ^S =Æ, N ^A ={B}, N ^B =Æ, N ^C ={A,B}, S¢=S. Построим множество правил P¢:

S®AaB½aB½cC½Aa½a½c

A®AB½a½b

B®Ba½a

C®AB½c.

Поскольку элементами множеств N ^X  являются только нетерминалы A и B, требуется рассматривать правила только для символов A и B:

A®AB½a½b. Поскольку AÎN ^C ={A,B}, необходимо добавить правило C®AB½a½b. Но C®AB уже есть, следовательно, добавляем только C®a½b.

B®Ba½a. Поскольку BÎN ^C ={A,B} и BÎN ^A ={B}, необходимо добавить правила C®Ba½a и A®Ba½a. После всех добавлений и устранения дублирующих правил получим новые правила грамматики:

S®AaB½aB½cC½Aa½a½c

A®AB½a½b½Ba

B®Ba½a

C®AB½c½a½b½Ba.

Итоговое множество правил не содержит пустых и цепных правил. Хотя количество правил и увеличилось, но при построении распознавателя с таким множеством работать проще.

4.2.2.3. Контрольные вопросы

1. С какой целью выполняются преобразования грамматик?

2. Может ли результатом преобразований грамматики являться усложнение вида её правил?

3. Какого вида преобразования грамматик выполняются для упрощения процесса построения распознавателя?

4. Какие грамматики называются приведёнными?

5. Может ли терминальный символ быть недостижимым?

6. Какой символ называется бесплодным? Какой символ может быть бесплодным – терминальный или нетерминальный?

7. Какая грамматика называется грамматикой без e-правил? Допустимо ли наличие пустых правил в такой грамматике?

8. Какие преобразования необходимо выполнить, чтобы привести КС-грамматику к каноническому виду? К какому виду относятся эти преобразования – они упрощают правила грамматики или усложняют их?

9. Какое множество строится при удалении недостижимых символов – сразу нужное или сначала противоположное ему множество?

10. Какое множество строится при удалении бесплодных символов?

КС-грамматики в нормальной форме

Нормальная форма Хомского

Нормальная форма Хомского, или бинарная нормальная форма – одна из предопределённых форм для правил КС-грамматики. В нормальную форму Хомского можно преобразовать любую КС-грамматику, но сначала её необходимо привести к каноническому виду.

КС-грамматика G(V_T,V_N,P,S) называется грамматикой в нормальной форме Хомского, если в её множестве правил P присутствуют только правила следующего вида:

1. A®BC, где A, B, CÎV_N.

2. A®a, где AÎV_N, aÎV_T.

3. S®e, если eÎL(G) и S не должно встречаться в правых частях других правил.

Никакие другие правила не могут встречаться среди правил грамматики в нормальной форме Хомского.

Грамматика в нормальной форме Хомского называется также грамматикой в бинарной нормальной форме (БНФ), т.к. на каждом шаге нетерминальный символ может быть заменен только на два других нетерминальных символа.

Для преобразования грамматики к БНФ сначала требуется преобразовать её к приведенному виду. Соответствующий алгоритм был рассмотрен выше, поэтому будем считать, что КС-грамматика уже находится в каноническом виде.

Алгоритм 5. Преобразование грамматики к БНФ (Хомского).

Сначала множество нетерминальных символов новой грамматики строится на основе множества нетерминальных символов исходной грамматики: V_N¢=V_N.

Затем алгоритм работает с правилами P исходной грамматики и в зависимости от их вида строит множество правил P¢ и пополняет множество нетерминальных символов V_N¢.

1. Правила вида A®a, A®BC, S®e, где A, B, CÎV_N, aÎV_T, переносятся во множество P¢ без изменений.

2. Если встречается правило вида (A®aB)ÎP, где A, BÎV_N, aÎV_T, то во множество правил P¢ добавляются правила A®<AaB>B и <AaB>®a, а новый символ <AaB> добавляется во множество нетерминальных символов V_N¢.

3. Если встречается правило вида (A®Ba)ÎP, выполняется аналогичное действие: во множество правил P¢ добавляются правила A®B<ABa> и <ABa>®a, а новый символ <ABa> добавляется во множество нетерминальных символов V_N¢.

4. Если встречается правило вида (A®ab)ÎP, где AÎV_N, a, bÎV_T, то во множество правил P¢ добавляются правила A®<Aa><Ab> и <Aa>®a, <Ab>®b, а новые символы <Aa>, <Ab> добавляются во множество нетерминальных символов V_N¢.

5. Если встречается правило вида (A®X₁X₂…X_k)ÎP, где k>2, AÎV_N, "i X_iÎV_TÈV_N, то во множество правил P¢ добавляются правила A®X₁¢<X₂¢…X_k¢>,
<X₂¢…X_k¢>®X₂¢<X₃¢…X_k¢>,
…
<X_k–1¢X_k¢>®X_k–1¢X_k¢,
где все новые нетерминальные символы <…> добавляются во множество нетерминальных символов V_N¢. Что касается символов X_i¢, то их вид зависит от того, чем являлся исходный символ X_i. Если для некоторого i X_iÎV_N, то X_i¢ºX_iÎV_N¢; если X_iÎV_T, то X_i¢ – новый нетерминальный символ, т.е. X_i¢ÎV_N¢ и в P¢ нужно добавить правило X_i¢®X_i.

Проиллюстрируем данный алгоритм на примере.

Пример 6. Преобразование КС-грамматики к БНФ.

Дана грамматика G({a,b,c},{A,B,C,S},P,S) в каноническом виде, где P:

S®AaB½Aa½bc

A®AB½a½aC

B®Ba½b

C®AB½c

Первоначально множество нетерминальных символов V_N¢={A,B,C,S}, затем оно может пополняться. Последовательно рассматриваем правила P и анализируем каждое из них.

1) S®AaB – относится к пункту 5 алгоритма. Следовательно, в P¢ включаем S®A<aB>, <aB>®<a>B, <a>®a, а в множество V_N¢ добавляем <aB>,<a>.

2) S®Aa – относится к 3 пункту алгоритма. Следовательно, в P¢ нужно включить S®A<a¢>, <a¢>®a, а в множество V_N¢ добавить <a¢>. Но ранее уже появился нетерминал <a>, из которого выводился символ a, поэтому можно использовать его, тогда можно ограничиться правилом S®A<a>.

3) S®bc – относится к 4 пункту. Следовательно, в P¢ нужно включить S®<b><c>, <b>®b, <c>®c, а в множество V_N¢ добавить <b>, <c>.

4) A®AB и A®a – в соответствии с первым пунктом алгоритма включается в P¢ без изменений.

5) A®aC – относится ко 2 пункту. Следовательно, в P¢ нужно включить A®<a>C, причем замечание из (2) справедливо и в данном случае.

6) B®Ba – аналогично (2), добавляется правило B®B<a>.

7) B®b, а также C®AB, C®c соответствуют требуемому виду правил и переносятся в грамматику без изменений.

Таким образом, получаем грамматику G¢({a,b,c},{A,B,C,<aB>,<a>, <b>,<c>,S},P¢,S) в нормальной форме Хомского, где P¢:

S®A<aB>½A<a>½<b><c>

A®AB½a½<a>C

B®B<a>½b

C®AB½c

<aB>®<a>B

<a>®a

<b>®b

<c>®c

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