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

Исключение леворекурсивных правил



 

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

, где A О VA

, a О(Vт

ИVA) * , называется праворекурсивным, а правило вида <A>  ® <A>a

- леворекурсивным.

 



Утверждение. Для каждой КС-грамматики Г, содержащей леворекурсивные правила, можно 
построить эквивалентную грамматику Г', не содержащую леворекурсивных правил.

Способ построения эквивалентной грамматики заключается в следующем. Допустим, что исходная грамматика Г содержит
правила:
                       <A> ®

<A>a 1 | <A>a

2 | ... |<A>a m| ,
где ни одна цепочка b не начинается с <A>

и a1, b1О(Vт ИVA) * .
Введем новый нетерминал <A'> и преобразуем правила так:

      <A> ®

      b 1 | b

      2 |...| b n | b

      1<A'> | b 2<A'>|...| b n<A'>,
      <A'> ®a

      1 | a 2 |...| a

      m| a 1<A'> |a

      2<A'>|...|a m<A'>.

    Заменяя все правила с левой рекурсией в Г описанным способом, получим грамматику Г',
    причем L(Г)=L(Г') , поскольку каждая цепочка, выведенная в грамматике Г, может быть
    построена в грамматике Г'. Рассмотрим построение выводов в Г и Г'. В грамматике Г вывод
    цепочки имеет вид:

        < A> Ю   <A>a 1 Ю

        <A>a 1a

        1 Ю   <A>a 1a

        1a 1 Ю   b 1a

        1a 1a

        1,

      в грамматике Г' эта же цепочка выводится так:
       

          <A> Ю

          b 1<A'> Ю

          b 1a 1<A'>

          Ю b

          1a 1a

          1<A'>  Ю

          b 1a

          1a 1a

          1.

        Чтобы показать технику преобразования, рассмотрим пример. Требуется преобразовать
        грамматику Г1. 9 (рассмотренную ранее), которая задана схемой:
         

            Г1. 9:   R={<E> ®  <E> + <T> | <T>,


                              < T> ®  <T> * <F> | <F>,


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


          Следуя описанному способу, правила  <E> 

          ®
          <E> + <T> | <T> преобразуем в правила
          <E>®

          <T> | <T><E'> и  <E'>  ®

          +<T> | +<T><E'> , а правила <T> ®

          <T> * <F> | <F> преобразуем в правила <T> 

          ®
          <F> | <F><T'> и  <T'>  ® *<

          F> | * <F><T'>.
          В результате получаем грамматику Г'1. 9, имеющую схему:


              Г'1. 9 :          R'= { <E> ®

              < T>,


                <E>  ®

                <T><E'>,


                < E'>® + <T>,

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

                <T>  ®

                <F>,


                <T>  ®

                <F><T'>,


                <T'> ® * <F>,

                <T'> ® * <F><T'>,

                < F> ® a,

                 <F> ®

                (<E>) },


                 


              не содержащую леворекурсивных правил.

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

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

               


              Содержание раздела