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

  4.                   ,       ,      (шаг 2 и 3);
  5.                     ,       ,        (шаг 2 и 3);
  6.                     ,         (шаг 2 и 3);
  7. Строим множества                         ,            и    (шаг 4);
  В итоге получили грамматику:




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

   1. 2. Алгоритм удаления недостижимых символов
   Определение: Символ               называется недостижимым, если он не
встречается ни в одной сентенциальной форме грамматики              .
   Т.е. символ недостижимый, если он не участвует ни в одной цепочке вывода
из начального символа грамматики. Очевидно, что такой символ грамматике не
нужен.
                  Алгоритм удаления недостижимых символов
   Шаг 1.          ,     ;
   Шаг 2.

   Шаг 3. Если        , то        и перейти к шагу 2, иначе перейти к шагу 4;
   Шаг 4.             ,           , в      входят правила из , которые
содержат только символы из множества ,        .
   Пример удаления недостижимых символов
   Задана грамматика:




  Удалим недостижимые символы согласно алгоритму:
  1.         ,     (шаг 1);
  2.             ,        ,      (шаги 2 и 3);
  3.                ,       ,       (шаги 2 и 3);
  4.                ,         (шаги 2 и 3);
  5. Строим множества                    ,        и        (шаг 4);
  В итоге получили грамматику:
                                      5