Применение приведенных рекомендаций рассмотрим на следующем примере.
Требуется построить грамматику для языка 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>,
получаем правило, определяющее общий вид цепочки:
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>* | * | ** Ю * | * | * |
**.
Построенный вывод иллюстрирует возможность порождения цепочек заданного
языка с помощью построенной грамматики.
Одной из основных областей применения формальных грамматик является
описание языков программирования. Учитывая широкое использование подобных
описаний в литературе и их важное значение для создания компиляторов, рассмотрим
построение грамматик для основных конструкций языков программирования.
Чтобы сократить размеры грамматик, на рассматриваемые конструкции накладываются
некоторые, иногда существенные, ограничения.
-
Пред.Страница
След.Страница
Раздел
Содержание