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

---

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 не является  слаборазделенной.

---

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