Грамматика называется леворекурсивной, если левый нетерминал правила совпадает с первым символом правой части правила.
Например:
A -> Aa
Многие алгоритмы требуют преобразование такой грамматика в эквивалентную.
Пример:
E -> E + T | T
T -> T * F | F
F -> (E) | i
Эквивалентно можно заменить так:
E -> TR
R -> +TR | $
Эквивалентно можно заменить так:
T -> FK
K -> *FK | $
Итак, можно заменить на следующие правила:
E -> TR
R -> +TR | $
T -> FK
K -> *FK | $
F -> (E) | i
Исключение онулирующих правил. Ряд алгоритмов построения синтаксических анализаторов требует наличие грамматики, не содержащее онулирующие правила. В таком случае можно заменить на эквивалентную грамматику. Эквивалентная грамматика строится за счет увеличение количество правил. Которое дополняется правилами, в которых нетерминал заменяется на пусто.
Пример:
E -> iR
R -> +iR | $
Эквивалентное правило:
E -> iR | i
R -> +iR | +i
