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

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

Способ построения эквивалентной грамматики заключается в следующем. Допустим, что исходная грамматика Г содержит правила:

<A> <A>α1 | <A>α2 | ... |<A>αm|,

где ни одна цепочка β не начинается с <A> и α1, β1 (Vт VA) *
Введем новый нетерминал <A'> и преобразуем правила так:

<A> β1 | β2 |...| βn | β1<A'> | β2<A'>|...| βn<A'>
<A'> α1 | α2 |...| αm | α1<A'> | α2<A'>|...| αm<A'>

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

<A> <A> α1 <A>α1α1 <A>α1α1α1 β1α1α1α1,

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

<A> β1<A'> β1α1<A'> β1α1α1<A'> β1α1α1α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>) }