Алгоритм 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.

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2015-07-12