Основы трансляции - 9 стр.

   Определение: Если          и        , то рекурсия называется правой, а
грамматика - праворекурсивной.
   Определение: Если       и     , то рекурсия представляет собой цикл.
   Любая КС-грамматика может быть как леворекурсивной, так и
праворекурсивной, а также леворекурсивной и праворекурсивной
одновременно.
   Некоторые алгоритмы левостороннего разбора для КС-языков не работают с
леворекурсивными грамматиками, поэтому возникает необходимость
исключить левую рекурсию из правил грамматики.
   Любую КС-грамматику можно преобразовать к нелеворекурсивному виду
или неправорекурсивному виду.
                      Алгоритм устранения левой рекурсии
   Шаг 1. Обозначим нетерминальные символы грамматики так:
                                             ,     .
   Шаг 2. Рассмотрим правила для символа . Если эти правила не содержат
левой рекурсии, то перенесем их в множество правил          без изменений, а
символ добавим в множество нетерминальных символов .
   Иначе запишем правила для в виде
                                                           ,
   где ни одна из цепочек ,           не начинается с символов , таких, что
     .
   Вместо этого правила в множество запишем два правила вида:


   Символы и включаем в множество .
   Теперь все правила для        начинаются либо с терминального символа, либо
с нетерминального символа , такого, что          .
   Шаг 3. Если         , то грамматика      построена, перейти к шагу 6, иначе
         ,       и перейти к шагу 4.
   Шаг 4. Для символа         в множестве правил     заменить все правила вида
           , где              , на правила вида                        , причем
                      - все правила для символа .
   Так как правая часть правил                                уже начинается с
терминального символа или нетерминального символа           ,     , то и правая
часть правил для символа будет удовлетворять этому условию.
   Шаг 5. Если             , то перейти к шагу 2, иначе             и перейти к
шагу 4.
   Шаг 6. Целевым символом грамматики                  становится символ       ,
соответствующий символу исходной грамматики .
   Пример устранения левой рекурсии
   Рассмотрим в качестве примера грамматику для арифметических выражений
над символами и :                                          , где
                                       9