Слаборазделенные грамматики
Используя введенные понятия, можно дать определение слаборазделенной грамматики.
| Определение. КС-грамматика называется слаборазделенной, если выполняются следующие три условия: правая часть каждого правила представляет собой либо пустую цепочку $, либо начинается с терминального символа, если два правила имеют одинаковые левые части, то правые части правил должны начинаться разными символами, для каждого нетерминала 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
не является слаборазделенной.
Пред.Страница
След.Страница Раздел Содержание
