Вывод цепочек

Регулярные выражения

Чтобы формально определить понятие регулярного выражения, введем вначале понятие алфавита. Алфавит представляет собой конечный набор символов, подобный приведенным ниже.

{0, 1} {а..я} {0..9}

Если А — алфавит, то к числу регулярных выражений относятся:

нулевая строка (обозначается e);

любой элемента А.

Кроме того, если Р и Q являются регулярными выражениями, то регулярными являются также следующие выражения.

PQ (Q следует после Р)

P | Q (Р или Q)

P^* (нуль или более вхождений Р)

Следует отметить, что введенный ранее оператор + (одно или более вхождений элемента), строго говоря, не является оператором регулярного выражения, поскольку при описании любого регулярного выражения можно обойтись и без него. Это связано с тем, что любое выражение, содержащее +, можно заменить эквивалентным выражением, содержащим оператор конкатенации и оператор *. Например, выражение

(abc)⁺

эквивалентно записывается следующим образом (abc)(abc)^*

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

I (I | d)^*

Здесь I обозначает букву, a d — цифру. Число с фиксированной запятой можно пред-ставить следующим выражением.

(d^*d.d^*) | (d^*.dd^*)

Здесь d также обозначает любую цифру.

Один из языков, ранее рассмотренных в данном разделе,

{ xⁿ yⁿ | n> 0}

невозможно определить посредством регулярного выражения, поскольку в регулярных выражениях не существует возможности указать, что количество элементов х должно равняться количеству элементов у. Следовательно, в этом случае нам необходим более мощный механизм, который позволит описать такой очевидно простой язык. Один из методов заключается в использовании продукции (production), подобной приведенным ниже.

S-> xSy

S-> xy

Здесь символ " -> " можно читать как " может иметь вид". Продукции могут использоваться для генерации строк языка с использованием следующих правил:

1. Начать с символа S и заменить его строкой, расположенной справа от знака продукции.

2. Если полученная строка не содержит больше символов S, она является строкой языка. В противном случае следует снова заменить S строкой после знака продукции, а затем снова вернуться к п. 2.

Приведем пример последовательности строк.

S

xSy

xxSyy

хххууу

Обычно подобную последовательность записывают следующим образом:

S => xSy => xxSyy => хххууу

Здесь знак " => " читается " порождает". Последовательность шагов, использованная для генерации строки с применением продукций грамматики, называется порождением (derivation) строки.

Очевидно, что описанным выше способом могут быть получены все строки языка

{ xⁿ yⁿ | n> 0}

При этом не будет порождена ни одна строка, не принадлежащая указанному языку.

Определим понятия грамматики, основываясь на введенном выше понятии продукции.