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

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

Определение. Правило вида <A>  ® a <A> , где A О VA , a О(Vт ИVA) * , называется праворекурсивным, а правило вида <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'>.

< A> Ю   <A>a ₁ Ю <A>a ₁a ₁ Ю   <A>a ₁a ₁a ₁ Ю   b ₁a ₁a ₁a ₁,

<A> Ю b ₁<A'> Ю b ₁a ₁<A'> Ю b ₁a ₁a ₁<A'>  Ю b ₁a ₁a ₁a ₁.

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

Г'_{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>) },
 

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