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

   Таким образом, в исходной грамматике             недостижиыми символами
являются нетерминалы и .

   1.3. Алгоритм удаления -правил
   Определение: -правилами называются все правила грамматики вида               ,
где       .
   Определение: КС-грамматика                      называется грамматикой без -
правил, если в ней не существует правил                             и существует
только одно правило                , в том случае, когда          и при этом не
встречается в правой части ни одного правила.
   Для того, чтобы упростить построение распознавателей языка
грамматику часто целесообразно преобразовать к виду без -правил.
                         Алгоритм удаления -правил
   Шаг 1.                            ,      ;
   Шаг 2.                                                ;
   Шаг 3. Если              , то            и перейти к шагу 2, иначе перейти к
шагу 4;
   Шаг 4.        ,        , в входят правила из , кроме             ;
   Шаг 5. если                 и в цепочку входят символы из множества ,
тогда на основе цепочки строится множество цепочек              путем исключения
из всех возможных комбинаций символов                 , все правила вида
добавляются в         (при этом надо учитывать дубликаты правил и
бесcмысленные правила);
   Шаг 6. если         , то значит                и тогда в    добавляется новый
символ , который становится начальным символом грамматики , а в
добавляются два новых правила                 ; иначе       .
   Данный алгоритм часто ведет к увеличению количества правил грамматики,
но позволяет упростить построение распознавателя для данного языка.
   Пример удаления -правил
   Задана грамматика:




  Удалим -правила согласно алгоритму:
  1.        ,      (шаг 1);
  2.          ,         ,      (шаги 2 и 3);
  3.             ,          ,     (шаги 2 и 3);

                                       6