Пред.Страница След.Страница   Раздел   Содержание

---

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

Исключение леворекурсивных правил.

Определение. Правило вида <A>  ® a <A> , где A Î V_A , a Î(V_т ÈV_A) ^* , называется праворекурсивным, а правило вида <A>  ® <A>a - леворекурсивным.

Утверждение. Для каждой КС-грамматики Г, содержащей леворекурсивные правила, можно 
построить эквивалентную грамматику Г', не содержащую леворекурсивных правил.

Способ построения эквивалентной грамматики заключается в следующем. Допустим, что исходная грамматика Г содержит
правила:
                       <A> ® <A>a ₁ | <A>a ₂ | ... |<A>a _m| ,
где ни одна цепочка b не начинается с <A> и a_1, b₁Î(Vт ÈV_A) ^* .
Введем новый нетерминал <A'> и преобразуем правила так:

<A> ® b ₁ | b ₂ |...| b _n | b ₁<A'> | b ₂<A'>|...| b _n<A'>,
<A'> ®a ₁ | a ₂ |...| a _m| a ₁<A'> |a ₂<A'>|...|a _m<A'>.

Заменяя все правила с левой рекурсией в Г описанным способом, получим грамматику Г',
причем L(Г)=L(Г') , поскольку каждая цепочка, выведенная в грамматике Г, может быть
построена в грамматике Г'. Рассмотрим построение выводов в Г и Г'. В грамматике Г вывод
цепочки имеет вид:

< A> Þ   <A>a ₁ Þ <A>a ₁a ₁ Þ   <A>a ₁a _{1a 1} Þ b ₁a _{1a 1a 1},

в грамматике Г' эта же цепочка выводится так:

<A> Þ b ₁<A'> Þ b ₁a ₁<A'> Þ b ₁a _{1a 1}<A'>  Þ b ₁a _{1a 1a 1}.

Чтобы показать технику преобразования, рассмотрим пример. Требуется преобразовать
грамматику Г_{1. 9} (рассмотренную ранее), которая задана схемой:

Г_{1. 9}:   R={<E> ®  <E> + <T> | <T>,
                  < T> ®  <T> * <F> | <F>,
                   <F> ® ( <E> ) | a}.

Следуя описанному способу, правила  <E>  ® <E> + <T> | <T> преобразуем в правила
<E>® <T> | <T><E'> и  <E'>  ® +<T> | +<T><E'> , а правила <T> ® <T> * <F> | <F> преобразуем в правила <T>  ® <F> | <F><T'> и  <T'>  ® *< F> | * <F><T'>.
В результате получаем грамматику Г'_{1. 9}, имеющую схему:

Г'_{1. 9 :}          R'= { <E> ® < T>,

<E>  ® <T><E'>,
< E'>® + <T>,
<E'> ® + <T><E'>,
<T>  ® <F>,
<T>  ® <F><T'>,
<T'> ® * <F>,
<T'> ® * <F><T'>,
< F> ® a,
 <F> ® (<E>) },

не содержащую леворекурсивных правил.

Исключение цепных правил.

Определение. Правило грамматики вида <A> ® <B>,  где <A>,<B> ÎV_A, 
                         называется цепным.

Утверждение. Для КС-грамматики Г, содержащей цепные правила , можно 

                 построить эквивалентную ей грамматику Г', не содержащую цепных правил.

Идея доказательства заключается в следующем. Если схема грамматики имеет вид

R = {...,<A> ® <B>,...,<B> ® <C>, ... , <C> ® a<X> },

то такая грамматика  эквивалентна грамматике со схемой

R' = {...,<A> ® a<X>,...},

поскольку вывод в грамматике со схемой R цепочки a<X> :

<A> Þ< B> Þ <C> Þ a<X>

может быть получен  в грамматике со схемой R' с помощью правила <A> ® a<X>.
В общем случае доказательство последнего утверждения можно выполнить так.
Разобьем R на два подмножества R₁ и R₂, включая в R₁ все правила вида <A> ® < B>.
Для каждого правила из R₁ найдем множество правил S(<A_i>), которые строятся так:
если <A_i> Þ * <A_j> и в R₂ есть правило <A_j> ® a , где a - цепочка словаря (V_т ÈV_A)^* ,
то в S(<A_i>) включим правило <A_i> ® a .
Построим новую схему R' путем объединения правил R₂ и всех построенных
множеств S(<A_i>). Получим грамматику Г' = {V_т ,V_a , I , R'}, которая эквивалентна
заданной и не содержит правил вида <A> ® <B>.
В качестве примера выполним исключение цепных правил из грамматики Г_{1. 9}
со схемой :

Г_{1. 9}:     R={<E> ®   <E> + <T> | <T>,
                  < T> ® < T> * <F> | <F>,
                   <F> ® ( <E> ) | a}.

Вначале разобьем правила грамматики на два подмножества:

R₁ = { <E> ® <T>,<T> ®   <F> } ,
R₂ = { <E> ® <E>+<T>, <T> ® <T>*<F>, <F>® (<E>) | a }

Для каждого правила из R1 построим соответствующее подмножество.

S(<E>) = { <E> ®< T>*<F>, <E> ® (<E>) | a },
S(<T>) = { <T> ® (<E>) | a}

В результате получаем искомую схему грамматики без цепных правил в виде:

R2 U S(<E>) U S(<T>) = { <E> ® --> <T>+<T> | <T>*<F> | (<E>) | a,

<T> ® <T>*<F> | (<E>) | a,
<F> ® (<E>) | a }

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

Определение. Правило вида <A> ® $ называется аннулирующим правилом.

Преобразование неукорачивающих грамматик.

Определение. Грамматика называется неукорачивающей или грамматикой без аннулирующих правил, если либо 
1)схема грамматики не содержит аннулирующих правил, 
2)либо схема грамматики содержит только одно правило вида <I> ® $, где <I> - начальный символ грамматики, и символ I не встречается в правых частях остальных правил грамматики.

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

Утверждение. Для каждой КС-грамматики Г', содержащей аннулирующие правила, можно 
построить эквивалентную ей неукорачивающую грамматику Г, такую что L(Г')=L(Г).

Построение неукорачивающей грамматики предполагает увеличение числа правил заданной
грамматики путем построения дополнительных правил, получаемых в результате исключения
нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо
выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики. Если же в грамматике есть правило вида <I> ® $ и символ <I> входит в правые части других правил грамматики, то следует ввести новый начальный символ <I'> и заменить правило <I> ® $ двумя новыми правилами: <I'> ® $ и <I'>® <I> .
В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие  правила из следующей грамматики:

                                                       Г_{3. 3} :       R = { <I> ® a<I>b<I>,
                                                                                <I> ® b<I>a<I>,
                                                                                <I> ®   $ }
Выполняя все возможные замены символа I в первом правиле грамматики, получаем четыре
правила вида:

<I> ® a<I>b<I>,   <I> ® ab<I>,    <I>® a<I>b,    <I>® ab .

Поступая аналогично со вторым правилом, имеем:

<I> ® b<I>a<I>,    <I> ® ba<I>,    <I> ® b<I>a,    <I> ® ba.

Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части
других правил грамматики, заменим правило <I> ® $ правилами вида <I'>® $  и  <I'>® <I> .
Построенная совокупность правил образует схему искомой неукорачивающей грамматики. Все
приведенные выше преобразования грамматик могут быть использованы и оказаться полезными при построении как конечных, так и магазинных автоматов.

---

Пред.Страница След.Страница   Раздел   Содержание