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


Рекомендации по построению грамматик


    Основой создания правил грамматики является способ выделения структуры заданного множества цепочек. Этот способ предусматривает расчленение цепочек, входящих в заданное множество, на части таким образом, чтобы выявить повторяющиеся части цепочек и части, входящие во все цепочки в неизменном виде. Такое расчленение на части представляет собой выявление структуры цепочек заданного множества.
    Для каждого выявленного элемента структуры введем обозначения. Множество таких обозначений составляет основу словаря нетерминальных символов некоторой грамматики.
    Следующим шагом построения является выявление последовательностей, в которых элементы структуры могут входить в заданные цепочки. Такие последовательности являются основой для построения правил грамматики.
    Чтобы показать, каким образом структура цепочек отображается в правила грамматики, рассмотрим следующие примеры.
    1. Цепочке, состоящей из заданных символов abc, соответствует правило

              <I> ® abc.

    2. Цепочке, начинающейся с заданного символа a, соответствует правило

              <I> ® a<A>.

     3. Цепочке, заканчивающейся заданным символом a, соответствует правило

              <I> ® <A>a.

    4. Цепочке, начинающейся и заканчивающейся заданными символами a, b, соответствует правило

              <I> ® a<A>b.

    5. Цепочке, содержащей в середине символ a, соответствует правило

              <I> ® <A>a<B>.

    6. Цепочке заданной длины l =2 соответствуют правила:

            <A> ® a<B>

            и <B> ® a.

    7. Цепочке, состоящей из повторяющихся символов a, соответствуют правила

            <A> ® a<A>

            и <A> ® a.

     8. Цепочке, состоящей из чередующихся символов a и b, соответствуют правила:

            <A> ® a<B>

            и <B> ® b<A>.

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




- Начало -  - Назад -  - Вперед -