Пример построения грамматик

Применение приведенных рекомендаций рассмотрим на следующем примере. Требуется построить грамматику для языка L ,терминальный словарь которого Vт = {*, |}, а цепочки, образующие язык, имеют следующую структуру:
а) каждая цепочка начинается буквой * и заканчивается двумя буквами **.
b) между началом и концом цепочек могут быть:
b1) либо непустая последовательность палочек
b2) либо несколько таких последовательностей, разделенных символами *.

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

* |**,
* |*|*|**,
* **|** ,
* |*|**** .

2. Рассматривая приведенные цепочки, можно выделить следующие их структурные компоненты:

начало цепочки (символ * ),

конец цепочки (символы ** ),

непустая группа палочек,

последовательность групп палочек, разделенных звездочками.

3. Обозначим группу палочек символом <A>, а последовательность групп палочек символом <B>.
4. Выделенные структуры можно рассматривать как списки. Так последовательность палочек представляет собой список без разделителей, элементом которого является палочка. Правила грамматики, задающей такой список, имеют вид:

<A> ® | <B>,


<B> ® | <B>,


<B> ® $.

Последовательность групп палочек, разделенных звездочкой, представляет собой список с разделителем, элементом такого списка является группа палочек






<A>, а разделителем - звездочка. Правила грамматики, задающей такой список, можно записать так:

<C> ® <A><E>,


<E> ® *<A><E>,


<E> ® $.

Учитывая, что каждая цепочка языка должна иметь начало и конец, и , выбирая в качестве начального символа грамматики <I>, получаем правило, определяющее общий вид цепочки:

<I> ® *<C>**.

5. Объединяя построенные правила, окончательно получаем схему искомой грамматики в виде:

 

Г1. 19:    R = { <I> ® *<C>**,
<C> ® <A><E>,


<E> ® *<A><E>,



<E> ® $,

<A> ® | <B>,

<B> ® | <B>,

<B> ® $ }

6. С помощью правил построенной грамматики может быть получена, например, следующая цепочка:
 
<I> Ю *<C>** Ю *<A><E>** Ю *<A>*<A><E>**
Ю

 *<A>*<A>*<A><E> Ю *<A>*<A>*<A>**
Ю

 *<A>*<A>* | <B>** Ю *<A>*<A>* | ** Ю

 *<A>* | <B>* | ** Ю *<A>* | * | ** Ю

 * | <B>* | * | ** Ю * | * | * | **.

 

Построенный вывод иллюстрирует возможность порождения цепочек заданного языка с помощью построенной грамматики.
Одной из основных областей применения формальных грамматик является описание языков программирования. Учитывая широкое использование подобных описаний в литературе и их важное значение для создания компиляторов, рассмотрим построение грамматик для основных конструкций языков программирования. Чтобы сократить размеры грамматик, на рассматриваемые конструкции накладываются некоторые, иногда существенные, ограничения.
 

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

 


Содержание раздела






---