Теория и реализация языков программирования

             

Регулярные множества и выражения - часть 2


Пример 3.1. Несколько примеров регулярных выражений и обозначаемых ими регулярных множеств:

  1. a(e|a)|b - обозначает множество {a; b; aa};
  2. a(a|b)* - обозначает множество всевозможных цепочек, состоящих из a и b, начинающихся с a;
  3. (a|b)*(a|b)(a|b)* - обозначает множество всех непустых цепочек, состоящих из a и b, то есть множество {a, b}+;
  4. ((0|1)(0|1)(0|1))* - обозначает множество всех цепочек, состоящих из нулей и единиц, длины которых делятся на 3.

Ясно, что для каждого регулярного множества можно найти регулярное выражение, обозначающее это множество, и наоборот. Более того, для каждого регулярного множества существует бесконечно много обозначающих его регулярных выражений.

Будем говорить, что регулярные выражения равны или эквивалентны (=), если они обозначают одно и то же регулярное множество.

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

Лемма. Пусть p, q и r - регулярные выражения. Тогда справедливы следующие соотношения:

  1. p|q = q|p;
  2. * = e;
  3. p|(q|r) = (p|q)|r;
  4. p(qr) = (pq)r;
  5. p(q|r) = pq|pr;
  6. (p|q)r = pr|qr;
  7. pe = ep = p;
  8. p = p
    =
    ;
  9. p* = p|p*;
  10. (p*)* = p*;
  11. p|p = p;
  12. p|
    = p;

Следствие. Для любого регулярного выражения существует эквивалентное регулярное выражение, которое либо есть

, либо не содержит в своей записи
.

В дальнейшем будем рассматривать только регулярные выражения, не содержащие в своей записи

. При практическом описании лексических структур бывает полезно сопоставлять регулярным выражениям некоторые имена, и ссылаться на них по этим именам. Для определения таких имен мы будем использовать запись вида

\begin{aligned*} & d_1\ \; = \; r_1 \\ & d_2\ \; = \; r_2 \\ & \ldots\ \\ &d_n\ \; = \; r_n \end{aligned*}

где di - различные имена, а каждое ri - регулярное выражение над символами

T \cup \{d_1, \; d_2, \; \ldots \; , d_{i-1}\}
, то есть символами основного алфавита и ранее определенными символами (именами). Таким образом, для любого ri

можно построить регулярное выражение над T, повторно заменяя имена регулярных выражений на обозначаемые ими регулярные выражения.

Пример 3.2. Несколько примеров использования имен для обозначения регулярных выражений.

  1. Регулярное выражение для множества идентификаторов.
    \begin{aligned}& Letter = a \mid b \mid c \mid \ldots \mid x \mid y \mid z\\ & Digit=0 \mid 1 \mid \ldots \mid 9 \\ & Identifier = Letter(Letter \mid Digit)^*\\ \end{aligned}

  2. Регулярное выражение для множества чисел в десятичной записи.

    \begin{aligned}& Digit=0 \mid 1 \mid \ldots \mid 9 \\ & Integer=Digit^+\\ & Fraction=.Integer \mid e \\ & Exponent= (E(+ \mid - \mid e)Integer) \mid e \\ & Number = Integer \; Fraction \; Exponent \end{aligned}




Содержание  Назад  Вперед