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

Определение. Правило вида <A>   <A>, где A  VA, (Vт VA) *, называетсяправорекурсивным, а правило вида<A>   <A>- леворекурсивным.

 

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

Способ построения эквивалентной грамматики заключается в следующем. Допустим, что исходная грамматика Г содержит правила:                        <A> <A>₁ | <A>₂ | ... |<A>_m| , где ни одна цепочкане начинается с <A> и _ _(Vт V_A) ^*. Введем новый нетерминал <A'> и преобразуем правила так:

<A> ₁ |₂ |...|_n|₁<A'> |₂<A'>|...|_n<A'>, <A'> ₁ |₂ |...|_m|₁<A'> |₂<A'>|...|_m<A'>.

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

< A> <A> ₁ <A> ₁ ₁ <A> ₁ ₁ ₁  ₁ ₁ ₁₁,

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

<A> ₁<A'> ₁₁<A'> ₁ ₁₁<A'> ₁ ₁ ₁₁.

Чтобы показать технику преобразования, рассмотрим пример. Требуется преобразовать грамматику Г_{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>) },

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

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

 

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

 

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

 

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

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>, где- цепочка словаря(V_т V_A)^*, то в S(<A_i>) включим правило <A_i>  . Построим новую схему 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>$ называетсяаннулирующим правилом.