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


Итерационная форма


    Для получения более компактных описаний синтаксиса применяют итерационную форму описания. Такая форма предполагает введение специальной операции, которая называется итерацией и обозначается парой фигурных скобок со звездочкой. Итерация вида {a}* определяется как множество, включающее цепочки всевозможной длины, построенные с использованием символа a, и пустую цепочку.

      {a}* = {$, a, aa, aaa, aaaa,...}.

    Иcпользуя итерацию для описания множества цепочек, задаваемых символическими правилами, для списка получаем:

              <L> ® <E> {<E>}*.

    Например, описание множества цепочек, каждая из которых должна начинаться знаком # и может состоять из произвольного числа букв x и y, может быть представлено в итерационной форме так:

              <I> ® #{x | y}*

              .

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

          <A> ® x<A>y<B>z и <A>

          ® x<B>z

    могут быть записаны так:

            <A> ® x[<A>y]<B>z.

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




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