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

  4.              ,           (шаги 2 и 3);
  5. Строим множества                    ,            и    (шаг 4);




  6. Рассмотрим все правила из множества (шаг 5):
  - из правил                     исключим все комбинации                и
получим новые правила                          , добавим их в   , исключая
дубликаты, получим:                               ;
  - из правил                    исключим все комбинации                 и
получим новые правила               ; в    их добавлять не надо, поскольку
правило        там уже есть, а правило        бессмысленно;
  - из правил           исключим все комбинации                  и получим
новое правило       , добавим его в , получим:            ;
  - из правил                 исключим все комбинации                    и
получим новые правила                      добавим их в       , получим:
                  ;
  7.        , поэтому в грамматику      не надо добавлять новый начальный
символ ,         (шаг 6).
  В итоге получили грамматику:




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

                                      7