Для построения распознавателей в правилах грамматики не должно быть левосторонней рекурсии, т.е. правил вида A -> Ax. Пусть в исходной грамматике есть следующее правило: A -> Ax1¦ Ax2¦...¦Axk¦y1¦y2¦....¦ys (знак ¦ означает "или", т.е. в этом правиле объединено несколько правил с одинаковыми левыми частями; xi,yi цепочки терминалов и нетерминалов и yi не начинаются с А). Исходная грамматика не содержит нетерминала В. Тогда возможна эквивалентная замена такого составного правила на два не содержащих левосторонней рекурсии:
A -> y1¦y2¦....¦ys¦y1B¦y2B¦....¦ysB
B -> x1¦x2¦....¦xk¦x1B¦x2B¦....¦xkB
Пример: Пусть в исходной грамматике G имеется правило с левосторонней рекурсией A -> Abc ¦ b. Устраним левостороннюю рекурсию.
Введем обозначения: х1=bc; y1=b. После замены получим:
A -> b ¦ bB;
B -> bc ¦ bcB.