Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 51 стр.

                                                                        51
     S → Aa                                   C → Dd
     A → Bb                                   C→e
     B → Cc                                   D → Az
     которая имеет левый рекурсивный цикл, вовлекающий A, B, C, D.
Чтобы   заменить    этот   цикл   прямой   левой   рекурсией,   упорядочим
нетерминалы следующим образом: S, A, B, C, D.
     Рассмотрим все порождающие правила вида
     Xi → Xj γ,
     где Xi и Xj – нетерминалы, а γ – строка терминальных и
нетерминальных символов. В отношении правил, для которых j ≥ i, никакие
действия не производятся. Однако это неравенство не может выдерживаться
для всех правил, если есть левый рекурсивный цикл. При выбранном нами
порядке мы имеем дело с единственным правилом:
     D → Az
     так как A предшествует D в этом упорядочении. Теперь начнем
замещать A, пользуясь всеми правилами, имеющими A в левой части. В
результате получаем
     D → Bbz
     Поскольку B предшествует D в упорядочении, процесс повторяется,
что дает правило:
     D → Ccbz
     Затем он повторяется еще раз и дает два правила:
     D → ecbz
     D → Ddcbz
     Теперь преобразованная грамматика выглядит следующим образом:
     S → Aa                                   C→e
     A → Bb                                   D → Ddcbz
     B → Cc                                   D → ecbz
     C → Dd