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

Электрик сделает электроработы на даче Новосибирск и пригороде. Русский электрик. | У Вас есть gps? карта gps смоленской обл garmin.

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



 

Определение. Правило вида <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 (рассмотренную ранее), которая задана схемой: