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


Смотрите elobogrev.ru обогрев газопроводов. |

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



 

Определение. Правило вида <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}.




          Содержание  Назад  Вперед