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

---

3.6. Слаборазделенные и LL(1) - грамматики. Преобразование грамматик к виду LL(1)

Слаборазделенные грамматики

Используя введенные понятия,  можно дать определение слаборазделенной грамматики.

Определение. КС-грамматика называется слаборазделенной, если выполняются  следующие три условия: 

· правая часть каждого правила представляет собой либо пустую цепочку $, либо начинается с терминального символа, 

· если два правила имеют одинаковые левые части, то правые части правил должны начинаться разными символами, 

· для каждого нетерминала A, такого что A ==>* $ множество начальных символов не должно пересекаться  с множеством символов, следующих за A.:

ПЕРВ(A) Ç СЛЕД(A) = $

Используя приведенное определение, выясним, является ли следующая грамматика слаборазделенной:

Г_{3. 7} : R = {(1) <I>  ® a<A> ,

         (2) <I>  ® b ,
         (3) <A> ® c<I>a ,
         (4) <A> ® $ }.

Эта грамматика не содержит правил с одинаковой левой  частью, начинающихся одинаковыми терминалами, поэтому нужно проверить только условие (3) для правила (4). Вычисляя функции

ПЕРВ(<A>) = {c} и СЛЕД(<A>) = СЛЕД(<I>) = {a},

находим, что множество значений функции ПЕРВ(<A>) и множество значений функции СЛЕД(<A>) не имеют общих элементов. Следовательно, грамматика Г_3.7 является слаборазделенной.
Проверка выполнения условия (3) для грамматики

Г_{3. 8}: R = { <I>  ® a<I><A> | $ ,

       <A> ® a | b }

дает следующие результаты:

ПЕРВ(<I>) = {a} и СЛЕД(<I>) = ПЕРВ(<A>) = {a,b},

которые показывают, что пересечение множеств ПЕРВ(<I>) и СЛЕД(<I>) не пусто. Следовательно грамматика Г_3.8 не является  слаборазделенной.

LL(1) - грамматики.

Разделенные и слаборазделенные грамматики представляют собой подклассы грамматик более общего вида, которые называются LL(1) грамматиками, и которые определяются следующим образом.

Определение. КС-грамматика является LL(1) грамматикой тогда и  только тогда, когда 
                         выполняются следующие два условия: 
                   1 . Для каждого нетерминала, являющегося левой  частью нескольких правил: 
                         <A>  ®a ₁ | a ₂ | ... | a_n, 
                        необходимо, чтобы пересечение функций ПЕРВ(a_i) и ПЕРВ(a _j) было 
                        пусто для всех i =/= j. 
                   2 . Для каждого аннулирующего нетерминала <A>,такого что <A> ==>* $,
                        необходимо, чтобы пересечение  множеств ПЕРВ(<A>) и СЛЕД(<A>) было 
                        пустым. 

Из определения следует, что грамматики LL(1), в отличие от разделенных грамматик и слаборазделенных, могут содержать правила, начинающиеся нетерминальными символами. Проверим относится ли рассмотренная ранее грамматика Г₄₃  к классу LL(1).
Для этого необходимо вначале проверить наличие одинаковых значений функций ПЕРВ для правил с одинаковой левой частью. Для правил (1) и (2) имеем

ПЕРВ(<B><C>a) = ПЕРВ(<B>) È ПЕРВ(<C>) = {a,b,d,c},
ПЕРВ(g<D><B>) = {g},

а для правил (5) и (6) имеем

ПЕРВ(<D>a<B>) = ПЕРВ(<D>) È ПЕРВ(a<B>) = {a,d},
ПЕРВ(ca) = {c}.

Полученные результаты показывают, что первое условие LL(1) грамматики выполняется.
Второе условие необходимо проверить для правил (3) и (7) рассматриваемой грамматики. Вычисляя функции ПЕРВ и СЛЕД для правила (8), имеем:

ПЕРВ(<B>) = {b} и СЛЕД(<B>) = {a,c,d,g,f}.

Эти функции не имеют одинаковых значений, следовательно грамматика Г₄₃ является грамматикой LL(1).
Рассматриваемый класс грамматик можно определить также с помощью множеств выбора следующим образом:

Определение. КС-грамматика называется LL(1) грамматикой тогда  и только тогда, 
когда множества ВЫБОР, построенные  для правил с одинаковой левой                          частью, не содержат одинаковых элементов. 

Преобразование грамматик к виду LL(1). Исключение леворекурсивных правил.

Возможность построения для LL(1) грамматики детерминированного автомата определяет значение этих грамматик для практических применений. Однако, при построении грамматики для заданного языка не всегда удается получить грамматику, принадлежащую классу LL(1). Это может случиться потому, что неудачно выбраны правила грамматики, или потому, что для заданного языка принципиально нельзя построить LL(1) грамматику. В первом случае полученную грамматику можно попытаться  преобразовать таким образом, чтобы она удовлетворяла условиям LL(1) грамматики. Известно несколько приемов преобразований, которые в некоторых случаях, но не всегда, позволяют получить грамматику требуемого вида.
Первый вид преобразований заключается в исключении правил, содержащих левую рекурсию. Необходимость исключения таких  правил можно показать с помощью следующих рассуждений.

• Допустим, что в схеме заданной грамматики имеются правила: <A>  ® <B> | <A><B>. Первое условие определения LL(1) грамматики говорит о том, что функции ПЕРВ для правил с одинаковой левой частью не должны иметь одинаковых элементов, но для заданной грамматики это не так, поскольку

ПЕРВ(<A><B>) = ПЕРВ(<A>) = ПЕРВ(<B>).

Следовательно, грамматика, содержащая рассматриваемые правила, не является LL(1) грамматикой.

• Возьмем другие правила, обеспечивающие получение такого же множества цепочек, что и в первом случае : <A>  ® <A><B> | $.
  Первое условие выполняется, но имеем:
  СЛЕД ( <A> ) = ПЕРВ (<B>) и ПЕРВ (<A>) = ПЕРВ (<B>),
  поскольку A можно заменить $.
  Эти равенства показывают, что нарушается второе условие из определения LL(1) грамматики.
  Из приведенных рассуждений можно сделать вывод о том, что LL(1) грамматика не должна содержать леворекурсивных правил. Конечно, лучше не использовать леворекурсивные правила еще на этапе построения грамматики, но если уж они появились, то их можно исключить, пользуясь приемом, описанным в предыдущем разделе.

Выделение общих частей. 

Второй вид преобразований, который называют выделением общих частей, применяют для устранения правил с одинаковыми левыми частями, правые части которых  начинаются одинаковыми последовательностями символов.
Например, рассмотрим грамматику с правилами

<I>  ® a<I>,
<I>  ® a.

Эта грамматика не является LL(1) грамматикой, т.к. значения функций ПЕРВ(a<I>) и ПЕРВ(a) совпадают. Введем дополнительный нетерминал A и преобразуем грамматику так:

<I>  ® a<A>,
<A> ® <I>|$.

В этой грамматике отсутствуют правила с одинаковой левой частью, поэтому для нее выполняется первое условие определения LL(1) грамматики. В общем случае, если заданная грамматика содержит правила

<A>  ® a µ₁ | a µ₂ | ... | a µ_n ,

то, вводя дополнительный нетерминал <A'>, их можно преобразовать к виду:

<A>  ® a <A'>
<A'>  ® µ₁ | µ₂ | ... | µ_n.

Полученные правила могут быть использованы для построения LL(1) грамматики.
Покажем возможность применения этого вида преобразования на следующем примере. Пусть дана грамматика .

Г_{3. 9}:    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. 9}  закончилось удачно, но так бывает не всегда. Часто исключение правил, нарушающих первое условие, приводит к появлению аннулирующих правил, для которых нарушается второе условие.
Третий вид преобразования предполагает исключение аннулирующих правил и построение неукорачивающей грамматики. Такие преобразования могут оказаться полезными, если нарушается второе условие принадлежности грамматики к классу LL(1).

---

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