Исключение леворекурсивных правил
| Определение. Правило вида <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>) },
не содержащую леворекурсивных правил.
Пред.Страница
След.Страница Раздел Содержание