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

   1. АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ ГРАММАТИК
   Можно выделить две основные цели преобразований: упрощение правил
грамматик и облегчение создания распознавателя языка.
   Все преобразования условно можно разбить на две группы:
   - преобразования, связанные с исключением из грамматики избыточных
правил и символов, без которых она может существовать (именно эти
преобразования позволяют выполнить упрощения правил);
   - преобразования, в результате которых изменяется вид и состав правил
грамматики, при этом грамматика может дополнятся новыми правилами, а её
словарь нетерминальных символов – новыми символами (преобразования не
связаны с упрощениями).
   В результате преобразований мы получаем новую грамматику,
эквивалентную исходной, то есть определяющую тот же самый язык.
   Формально, преобразование можно определить следующим образом:
                                                           .

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




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

                                      4