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

   Шаг 5.        ,       , в    входят правила из , кроме правил вида
       ,      .
   Шаг 6. Для всех правил               , если       ,      , то в
добавляются правила вида      .
   Данный алгоритм, так же как и алгоритм устранения -правил, ведет к
увеличению числа правил грамматики, но упрощает построение
распознавателей.
   Пример устранения цепных правил
   Задана грамматика:



  Устраним цепные правила согласно алгоритму:
  1.           ,        ;
  2.              ,            ,      ;
  3.                  ,           ,       ;
  4.                  ,           ,             ;
  5.           ,        ;
  6.               ,            ,      ;
  7.               ,            ,           ;
  8.            ,        ;
  9.            ,            ,          ;
  10. Получили:                     ,             ,          ,        . Построим
множества                  ,                        и множество правил ;
  11. Рассмотрим все правила из множества           - интерес представляют только
правила для символов и , так как                      и          :
  - для правил                            имеем новые правила                    ,
поскольку           ;
  - для правил                           имеем новые правила                    и
              , поскольку             и         .
  В итоге получим новую грамматику:




   1.5. Алгоритм устранения левой рекурсии
   Определение: Символ          в КС-грамматике              называется
рекурсивным, если для него существует цепочка вывода вида         , где
               .
   Определение: Если         и       , то рекурсия называется левой, а
грамматика - леворекурсивной.

                                        8