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

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

Определение. КС-грамматика называется слаборазделенной, если выполняются  следующие три условия:  правая часть каждого правила представляет собой либо пустую цепочку $, либо начинается с терминального символа,   если два правила имеют одинаковые левые части, то правые части правил должны начинаться разными символами,   для каждого нетерминала A, такого что A ==>* $ множество начальных символов не должно пересекаться  с множеством символов, следующих за A.: ПЕРВ(A)  СЛЕД(A) = $

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

Г_{3. 3}  : 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.3является слаборазделенной. Проверка выполнения условия (3) для грамматики

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

       <A>  a | b }

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

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

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

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

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

Определение.КС-грамматика является LL(1) грамматикой тогда и  только тогда, когда                           выполняются следующие два условия:                     1 . Для каждого нетерминала, являющегося левой  частью нескольких правил:                         <A>   1 |  2 | ... | n, необходимо, чтобы пересечение функцийПЕРВ(i) и ПЕРВ( 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) грамматикой тогда  и только тогда,  когда множества ВЫБОР, построенные  для правил с одинаковой левой                          частью, не содержат одинаковых элементов.