Основы конструирования компиляторов

          

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


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

Регулярное множество в алфавите T определяется рекурсивно следующим образом:

  • Регулярные множества и выражения
    (пустое множество) - регулярное множество в алфавите T;
  • {e} - регулярное множество в алфавите T (e - пустая цепочка);
  • {a} - регулярное множество в алфавите

    T для каждого a

    Регулярные множества и выражения
    T;
  • если P и Q - регулярные множества в алфавите T, то регулярными являются и множества

  • P
    Регулярные множества и выражения
    Q (объединение),
  • PQ (конкатенация, т.е. множество {pq|p
    Регулярные множества и выражения
    P, q
    Регулярные множества и выражения
    Q}),
  • P* (итерация: P* =
    Регулярные множества и выражения

    n=0

    Регулярные множества и выражения
    Pn);

  • ничто другое не является регулярным множеством в алфавите T.
  • Итак, множество в алфавите T регулярно тогда и только тогда, когда оно либо

    Регулярные множества и выражения
    , либо {e}, либо {a} для некоторого a
    Регулярные множества и выражения
    T, либо его

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

    Приведенное выше определение регулярного множества позволяет ввести следующую удобную форму его записи, называемую регулярным выражением.

    Регулярное выражение в алфавите T и обозначаемое им регулярное множество в алфавите T определяются рекурсивно следующим образом:

    • Регулярные множества и выражения
      - регулярное выражение, обозначающее множество 
      Регулярные множества и выражения
      ;
    • e - регулярное выражение, обозначающее

      множество {e};

    • a - регулярное выражение, обозначающее множество {a};
    • если p и q - регулярные выражения, обозначающие регулярные множества P и Q соответственно, то

    • (p|q) - регулярное выражение, обозначающее регулярное множество P
      Регулярные множества и выражения
      Q,
    • (pq) - регулярное выражение, обозначающее регулярное множество PQ,
    • (p*) - регулярное выражение, обозначающее регулярное множество P*;

  • ничто другое не является регулярным

    выражением в алфавите T.

  • Мы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идет операции конкатенации, наконец, операция объединения имеет наименьший приоритет.

    Кроме того, мы будем пользоваться записью p+ для обозначения pp*. Таким образом, запись (a|((ba)(a*))) эквивалентна a|ba+.


    Наконец, мы будем использовать запись L(r) для регулярного множества, обозначаемого регулярным выражением

    r.

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


    • a(e|a)|b - обозначает множество {a, b, aa};


    • a(a|b)* - обозначает множество всевозможных цепочек, состоящих из a и b, начинающихся с a;


    • (a|b)*(a|b)(a|b)* - обозначает множество всех непустых цепочек, состоящих из a и b, т.е. множество {a, b}+;


    • ((0|1)(0|1)(0|1))* - обозначает множество всех цепочек, состоящих из нулей и единиц, длины которых делятся на 3.


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

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

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

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

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

    (1)p|q = q|p; (7) pe = ep = p;
    (2)
    Регулярные множества и выражения
    * = e;
    (8)
    Регулярные множества и выражения
    p = p
    Регулярные множества и выражения
    =
    Регулярные множества и выражения
    ;
    (3)p|(q|r) = (p|q)|r;(9) p* = p|p*;
    (4)p(qr) = (pq)r; (10)(p*)* = p*;
    (5)p(q|r) = pq|pr; (11)p|p = p;
    (6)(p|q)r = pr|qr; (12)p|
    Регулярные множества и выражения
    = p.
    Следствие. Для любого регулярного выражения существует эквивалентное регулярное выражение, которое либо есть
    Регулярные множества и выражения
    , либо не содержит в своей записи
    Регулярные множества и выражения
    .

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

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

    определения таких имен мы будем использовать запись вида

    d1 = r1
    d2 = r2
    ...
    dn = rn
    где di - различные имена, а каждое ri - регулярное выражение над символами T
    Регулярные множества и выражения
    {d1, d2, ..., di-1}, т.е. символами основного алфавита и ранее определенными символами (именами). Таким образом, для любого ri можно построить регулярное выражение над T, повторно заменяя имена регулярных выражений на обозначаемые ими регулярные выражения.



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


    • Регулярное выражение для множества идентификаторов.

      Letter = a|b|c|...|x|y|z
      Digit = 0|1|...|9
      Identifier = Letter(Letter|Digit)*
    • Регулярное выражение для множества чисел в десятичной записи.

      Digit = 0|1|...|9
      Integer = Digit+
      Fraction = .Integer|e
      Exponent = (E(+|-|e)Integer)|e
      Number = Integer Fraction Exponent



    Содержание раздела