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

UptoLike

Составители: 

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




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




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

                                      7