Формальные языки


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


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