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