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

Пример 3

Пусть L – множество (A,B,…,Z,a,b,…,z), а М – множество (0,1,2,…,9). Можно рассматривать множества L и М двояко. С одной стороны, L представляет собой алфавит, состоящий из набора прописных и строчных букв, а М – алфавит, состоящий из цифр. С другой стороны, поскольку символ можно рассматривать как строку единичной длины, множества L и М представляет собой конечные языки. Вот несколько примеров новых языков, созданных из L и М с применением операторов, приведенных на рис. 3.8.

1. L М представляет собой множество букв и цифр.

2. LМ – множество строк, состоящих из букв, за которой следует цифра.

3. L⁴ – множество всех четырехбуквенных строк.

4. L^* - множество всех строк из букв, включая пустую строку ε.

5. L(L М)^* - множество всех строк из букв и цифр, начинающихся с буквы.

6. М⁺ - множество всех строк из одной или нескольких цифр.

Множество, определенное в п.5 примера 3, описывает идентификаторы языка Pascal и представляет собой букву, за которой следует нуль или несколько букв или цифр. Представленный способ записи называется регулярным выражением, который позволяет точно определять подобные множества. С помощью этого способа записи можно определить идентификаторы Pascal как

letter (letter│digit) *

Вертикальная черта означает “или”, скобки используются для группирования подвыражений, а непосредственное соседство letter с оставшейся частью выражения означает конкатенацию.

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

Правила, которые определяют регулярные выражения над алфавитом А.

1. λ (или ε) представляет собой регулярное выражение, обозначающее { λ }, т.е. множество, содержащее пустую строку.

2. Если a является символом из А, то a – регулярное выражение, обозначающее { а }, т.е. множество, содержащее строку а. Хотя мы используем одну и туже запись, технически регулярное выражение а отличается от строки а. О чем идет речь, о регулярном выражении, строке или символе – становится понятно из контекста.

3. Если r и s – регулярные выражения, обозначающие языки L(r) и L(s),

тогда

· (r)│(s) представляет собой регулярное выражение, обозначающее L(r) L(s).

· (r)(s) – регулярное выражение, обозначающее L(r) и L(s).

· (r)^* – регулярное выражение, обозначающее (L(r))^*.

· (r) - регулярное выражение, обозначающее L(r).

Язык, задаваемый регулярным выражением, называется регулярным множеством.

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

1. Унарный оператор * имеет высший приоритет и левоассоциативен.

2. Конкатенация имеет второй по значимости приоритет и левоассоциативна.

3. │(объединение) имеет низший приоритет и левоассоциативно.

При этих соглашениях запись (а)│((b)*(c)) эквивалентна а │ b * c. Оба выражения обозначают множества строк, которые представляют собой либо единичный а, либо нуль или несколько b, за которыми следует единственный с [3].

Дата добавления: 2014-12-27