-
Пред.Страница
След.Страница
Раздел
Содержание
3.8.2
Выделение общих частей.
Второй вид преобразований, который называют выделением общих частей,
применяют для устранения правил с одинаковыми левыми частями, правые части
которых начинаются одинаковыми последовательностями символов.
Например, рассмотрим грамматику с правилами
Эта грамматика не является LL(1) грамматикой, т.к. значения функций ПЕРВ(a<I>)
и ПЕРВ(a) совпадают. Введем дополнительный нетерминал A и преобразуем грамматику
так:
В этой грамматике отсутствуют правила с одинаковой левой частью, поэтому
для нее выполняется первое условие определения LL(1) грамматики. В общем
случае, если заданная грамматика содержит правила
<A>
® a
µ1 | a µ2 | ... | a
µn ,
то, вводя дополнительный нетерминал <A'>, их можно преобразовать к виду:
<A>
® a
<A'>
<A'>
® µ1
| µ2 | ... | µn.
Полученные правила могут быть использованы для построения LL(1) грамматики.
Покажем возможность применения этого вида преобразования на следующем
примере. Пусть дана грамматика .
Г3. 6:
R = { <I> ®
b<A><I><B>,
<I> ®
b<A>,
<A>
® d<I>ca,
<A>
® f,
<B>
®c<A>a,
<B>
® c }.
Эта грамматика не является LL(1) грамматикой, поскольку нарушено первое
условие. Воспользуемся способом выделения общих частей: введем нетерминалы
D, E и построим правила:
<D>
® <I><B>
| $
<E>
® <A>a |
$ .
В результате включения этих правил в схему грамматики получаем:
<I>
® b<A><D>
<D> ®
<I><B>
<D> ®
$
<A> ®
d<I>ca
<A> ®
f
<B> ®
c<E>
<E> ®
<A>a
<E> ®
$
Для этой грамматики первое условие принадлежности грамматики к классу LL(1)
выполняется. Чтобы проверить второе условие, найдем функции ПЕРВ и СЛЕД
для аннулирующих правил.
СЛЕД(<D>) = СЛЕД(<I>) = ПЕРВ(<B>) И
ПЕРВ(ca) = {c},
ПЕРВ(<D>) = ПЕРВ(<I>) = {b},
СЛЕД(<E>) = СЛЕД(<B>) = СЛЕД(<D>) = {c},
ПЕРВ(<E>) = ПЕРВ(<A>) = {d,f}.
Полученные значения показывают, что второе условие выполняется, и что построенная
грамматика является грамматикой типа LL(1).
Преобразование для грамматики Г 3. 6
закончилось удачно, но так бывает не всегда. Часто исключение правил, нарушающих
первое условие, приводит к появлению аннулирующих правил, для которых нарушается
второе условие.
Третий вид преобразования предполагает исключение аннулирующих правил
и построение неукорачивающей грамматики. Такие преобразования могут оказаться
полезными, если нарушается второе условие принадлежности грамматики к классу
LL(1).
-
Пред.Страница
След.Страница
Раздел
Содержание