Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 33 стр.

      4.5.5. Удаление правил с терминальной правой частью

    Пусть в грамматике G имеется с терминальной правой частью A→β, где β ∈ V*T. Тогда
любой вывод с использованием этого правила имеет вид: S →* xAy → xβy. Здесь
нетерминал А в сентенциальной форме xAy появился на предыдущем шаге вывода B → uAv.
Если в это правило вместо А подставить β, получим правило B → uβv. Тогда длина вывода
некоторой цепочки сократится на один шаг. Следовательно, для того чтобы удалить
терминальное правило грамматики A→β, необходимо учесть следующие правила:
    а) если для нетерминала А больше нет правил, тогда во всех правых частях А заменяется
на β;
    б) если для нетерминала А есть другие правила, тогда добавляются новые правила, в
которых А заменяется на β.
    Пример. Пусть дана КС-грамматика G:
    S → aSb | bAa | B; A → ABa | b | ε; B → ab | ba.
    Удалим правила для нетерминала В. Тогда эквивалентная грамматика G1 будет включать
следующие правила:
     S → aSb | bAa | ab | ba; A → Aaba | Abaa| b | ε.

    4.5.6. Построение эквивалентной праворекурсивной КС-грамматики
    Некоторые специальные методы грамматического разбора неприменимы к
леворекурсивным или праворекурсивным грамматикам, поэтому рассмотрим устранение
левой или правой рекурсии. В общем случае избавиться от рекурсии в правилах грамматики
невозможно, т.к. бесконечные языки порождаются грамматиками с конечным числом правил
только благодаря рекурсии. Поэтому можно говорить лишь о преобразовании одного вида
рекурсии в другой. Рассмотрим, как для любой леворекурсивной КС-грамматики построить
эквивалентную праворекурсивную КС-грамматику.
    Пусть нетерминал А - леворекурсивен, т.е. для него имеются правила следующего вида:
    A → Ax1 | Ax2 | . . . | Axp | w1| . . . | wk, где xi и wj - цепочки над множеством VT ∪ VN.
    Введем дополнительные нетерминалы B и D и указанные правила заменим на
эквивалентные им:
    A → AB | D;
    B → x1 | x2 | . . . | xp;
    D → w1| w2 | . . . | wk.
    В результате замены получим вывод, который имеет вид:
    A → AB→ ABB → ABBB → . . . → AB* → DB*.
    Таким образом, для нетерминала А можно определить эквивалентные правила:
    A → DK;
    K → BK | ε.
    Выполняя подстановку D и B в эти правила, получим следующие праворекурсивные
правила:
    A → w1K| w2K | . . . | wkK;
    K → x1K | x2K | . . . | xpK | ε.
    Пример. Пусть задана грамматика G со следующими правилами вывода: S → Sa | ba.
Требуется построить эквивалентную ей праворекурсивную грамматику.
    Для решения задачи воспользуемся рассмотренным выше алгоритмом. В исходной
грамматике один леворекурсивный нетерминал S. Построим для него вывод:

    S → SB | D;
    B → a; D → ba. Вывод из S имеет вид: S → SB→ SBB→ . . . →DB*.
    Запишем эквивалентные правила для S: