Формальные языки


Исключение цепных правил - часть 2



                   <F> ® ( <E> ) | a}.

    Вначале разобьем правила грамматики на два подмножества:
     
      R1 = { <E> ®

      <T>,<T> ®   <F> } ,
      R2 = { <E> ®

      <E>+<T>, <T> ®

      <T>*<F>, <F>® (<E>) | a }

    Для каждого правила из R1 построим соответствующее подмножество.
     

      S(<E>) = { <E> ®<

      T>*<F>, <E> ® (<E>) | a },
      S(<T>) = { <T> ®

      (<E>) | a}

    В результате получаем искомую схему грамматики без цепных правил в виде:

    R2 U S(<E>) U S(<T>) = { <E> ®

    --> <T>+<T> | <T>*<F> | (<E>) | a,

              <T> ®

              <T>*<F> | (<E>) | a,
              <F> ®

              (<E>) | a }

    Последний вид рассматриваемых преобразований связан с удалением из
    грамматики правил с пустой правой частью.

 

    Определение. Правило вида <A> ®

    $ называется аннулирующим правилом.

  •  

    Пред.Страница 

    След.Страница   Раздел   Содержание


  •  




    - Начало -  - Назад -  - Вперед -