Определение. Правило грамматики вида <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 на два подмножества R1 и R2, включая в R1 все правила вида
<A> <B>
Для каждого правила из R1 найдем множество правил S(<Ai>), которые строятся так:
если <Ai> *<Aj> и в R2 есть правило <Aj> α, где α - цепочка словаря (Vт VA)*, то в S(<Ai>) включим правило <Ai> α.
Построим новую схему R' путем объединения правил R2 и всех построенных множеств S(<Ai>). Получим грамматику Г' = {Vт, VA, I, R'}, которая эквивалентна заданной и не содержит правил вида <A> <B>.

В качестве примера выполним исключение цепных правил из грамматики Г1.9 со схемой:
Г1.9:
R={<E> <E>+<T>|<T>,
<T> <T>*<F>|<F>,
<F> (<E>)|a }

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

R1 = { <E> <T>,<T> <F> },
R2 = { <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> $ называется аннулирующим правилом.