Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 24 стр.

              Алгоритм 4.7. Устранение прямой левой рекурсии
      Вход: КС-грамматика G = (VT , VN , P, S ) .
      Выход: Эквивалентная КС-грамматика G ′ = (VT , V N′ , P′, S ′) без прямой
левой рекурсии, т.е. без правил вида A → Aα , A ∈V N , α ∈V *.
      Шаг 1. Вывести из грамматики все правила для рекурсивного нетермина-
ла X :
      X → Xα1 | Xα 2 | K | Xα m   ( X ∈ VN ; α1, α 2 ,K , α m ∈ V * )

      X → β1 | β 2 | K | β n ( β1, β 2 , K , β n ∈ V * ).
     Шаг 2. Внести новый нетерминал Y так, чтобы он описывал любой
«хвост» строки, порождаемой рекурсивным нетерминалом X :
     Y → α1Y | α 2Y | K | α mY
     Y → α1 | α 2 | K | α m .
     Шаг 3. Заменить в рекурсивном правиле для X правую часть, используя
новый нетерминал и все нерекурсивные правила для X так, чтобы генерируе-
мый язык не изменился:
      X → β1Y | β 2Y | K | β nY
      X → β1 | β 2 | K | β n
      Y → α1Y | α 2Y | K | α mY
     Y → α1 | α 2 | K | α m .
     Шаг 4. Пополнить множество нетерминалов грамматики новым нетерми-
налом Y . Пополнить множество правил грамматики правилами, полученными
на шаге 3.
     Шаг 5. Повторить действия шагов 1-4 для всех рекурсивных нетермина-
лов грамматики, после чего полученные множества нетерминалов и правил
принять в качестве V N′ и P′.

      Пример 4.7. Дана грамматика G = ({a, b, c, d , z}, {S , A, B, C}, P, S ) с пра-
вилами P : 1) S → Aa; 2) A → Bb; 3) B → Cc | d ; 4) C → Ccbz | dbz . После
устранения прямой левой рекурсии получим эквивалентную грамматику
G′ = ({a, b, c, d , z}, {S , A, B, C , Z }, P′, S ) с правилами P′ :
      1) S → Aa; 2) A → Bb; 3) B → Cc | d ; 4) C → dbzZ | dbz; 5) Z → cbzZ | cbz.

                Постановка задачи к лабораторной работе № 4
      Разработать программное средство, автоматизирующее процесс эквива-
лентного преобразования КС-грамматик. Программное средство должно вы-
полнять следующие функции:
      1) организация ввода грамматики и проверка ее на принадлежность к
классу КС-грамматик;
      2) проверка существования языка КС-грамматики;


24