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

Двузначные НДА

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

Будем говорить, что такой НДА распознаёт текст X, если текст X переводит этот НДА из начального состояния в подмножество, пересекающееся с T. Например, если взять автомат КМП (со стандартным начальным состоянием), построенный по тексту Y, и объявить его наибольшее состояние терминальным, то такой автомат будет распознавать те и только те тексты, которые заканчиваются на Y.

Автомат с множеством терминальных состояний мы будем дальше называть двузначным.

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

Есть важный класс двузначных НДКА, называемый регулярными автоматами. Этот класс обладает следующими свойствами:

Регулярные автоматы обладают текстовым представлением.
Любой двузначный конечный автомат эквивалентен (в смысле равенства множеств распознаваемых текстов) некоторому регулярному.

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

Регулярное выражение — это формула, составленная из букв алфавита и трёх операций:

бинарная конкатенация
бинарная дизъюнкция
звёздочка

Семантика этих операций такова:

выражение AB распознаёт те и только те тексты, которые имеют вид XY, где X распознаётся A, а Y распознаётся B
выражение A|B распознаёт те и только те тексты, которые распознаются хотя бы одним из A или B
выражение (A)* распознаёт те и только те тексты, которые можно представить в виде конечной (возможно, пустой) последовательности текстов, каждый из которых распознаётся A

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

Выражение aba распознаёт только текст aba.
Выражение ab*a распознаёт тексты aa, aba, abba, abbba и т.д. Стоит отметить, что если звёздочка относится только к одной букве, скобки традиционно не ставятся.
Выражение ab*|b*a распознаёт тесты a, ab, abb, abbb и т.д., а также — тексты ba, bba, bbba и т.д.

Осталось описать соответствие между регулярными выражениями и автоматами. Можно, например, применить алгоритм Томпсона для построения двузначного НДКА по регулярному выражению.

Регулярные выражения, практическая сторона

Почти во всех языках программирования есть поддержка того или иного диалекта регулярных выражений. Регулярные выражения используются для поиска в текстах подтекстов. Здесь мы поговорим о той части синтаксиса регулярных выражений, которая встречается почти во всех их реализациях.

Сперва отметим главную особенность регулярных выражений в большинстве языков программирования: поиск в тексте T по регулярному выражению R ищет какое-нибудь разбиение текста T=AXB, в котором X распознаётся выражением R. Выбрать конкретное разбиение в случае, если их несколько, нельзя (компромисс в целях скорости поиска), но можно ограниченным образом контроллировать искомое разбиение. Основные способы контроля следующие:

выражения ^R, R$ и ^R$ ищут разбиения вида XB, AX и X соответственно
есть два вида звёздочки * и *?: жадная и ленивая; выражение (S)*Q выбирает тот среди распознаваемых текстов, в котором часть, распознанная (S)*, распознаётся наибольшим возможным количеством повторений S; ленивая же звёздочка соответствует наименьшему возможному количеству повторений S
есть глобальный режим, позволяющий найти несколько непересекающихся разбиений (то есть таких, части которых, распознаваемые выражением, не пересекаются по положению)

Кратко опишем особенности синтаксиса регулярных выражений по сравнению с математической моделью:

обычные скобки — это пара (?: и ); пара же ( и ) — это т.н. захватывающие скобки; исполнитель выражения с захватывающими скобками запоминает ту часть текста, которая была распознана подвыражением, заключённым в эти скобки
есть целое семейство унарных операторов, называемых кванторами: {m} -- ровно m вхождений, {m,n} -- от m до n вхождений, {m,} -- хотя бы m вхождений; в их терминах определяются *, +, ? как {0,}, {1,} и {0,1} соответственно
точка . распознаёт любую одну букву
т.н. классы символов, заключаемые в квадратные скобки, задают выражение, распознающее одну букву из некоторого подмножества алфавита
есть обратные ссылки (back references), распознающие участки, совпадающие с участками, захваченными скобками

Про последний пункт стоит сказать отдельно. Регулярные выражения не предназначены для разбора рекурсивных грамматик! Разбирать рекурсивные грамматики регулярными выражениями сложно и неэффективно! Если требуется разбор рекурсивных грамматик, следует прибегнуть к чему-то другому (например, к комбинаторам парсеров). Ни при каких обстоятельствах при разборе выражений не нужно использовать обратные ссылки! (А вот при поиске и замене они вполне полезны.)

В заключение дадим рекомендации по увеличению скорости поиска:

по возможности использовать незахватывающие скобки
в зависимости от конкретной реализации регулярных выражений, иногда имеет смысл заменить все жадные кванторы на ленивые (ленивые кванторы соответствуют стандартной семантике пошагового исполнения НДКА)
не пользоваться обратными ссылками: регулярные выражения не предназначены для разбора рекурсивных грамматик!

Примеры выражений

Для выделения имени сервера из интернет-адреса (кроме почтовых адресов) можно использовать любое из следующих выражений:

^http(?:|s):/+(.*?)(?:$|/)
^http(?:|s):/+([^/]*)

С некоторой осторожностью можно использовать выражение

^http(?:|s):/+([a-zA-Z0-9\-.]*)

Нечто подобное используют браузеры от Microsoft, в результате чего некоторые не удовлетворяющие стандарту имена серверов (например, использующие подчёркивание), воспринимаются некорректно.

Для распознания некоторого строгого надмножества почтовых адресов вида foobar@baz можно использовать выражение вида

^(.*)@([a-zA-Z0-9\-.]*)

Важно заметить, что первый квантор здесь жадный: внутри локальной части foobar вполне допустим символ @.

К сожалению, совсем корректное распознание почтовых адресов представляет огромные сложности из-за очень неудачного стандарта RFC 822. Вот — пример более правильного регулярного выражения (для удобства чтения оно разбито на строчки):

(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:
\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(
?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ 
\t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\0
31]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\
](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+
(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:
(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)
?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\
r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[
 \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)
?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t]
)*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[
 \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*
)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)
*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+
|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r
\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:
\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t
]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031
]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](
?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?
:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?
:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?
:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?
[ \t]))*"(?:(?:\r\n)?[ \t])*)*:(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] 
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|
\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>
@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"
(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?
:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[
\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-
\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(
?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;
:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([
^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\"
.\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\
]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\
[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\
r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] 
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]
|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \0
00-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\
.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,
;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?
:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[
^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]
]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)(?:,\s*(
?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(
?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[
\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t
])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t
])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?
:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|
\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:
[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\
]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)
?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["
()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)
?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>
@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[
 \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,
;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:
\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\[
"()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])
*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])
+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\
.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(
?:\r\n)?[ \t])*))*)?;\s*)

Следует отметить, что даже оно не удовлетворяет стандарту. В частности, оно не умеет обрабатывать вложенные комментарии.

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

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

import re

Регулярное выражение можно использовать двумя способами:

скомпилировав его функцией re.compile
используя функции re.search, re.match, re.fullmatch

Само регулярное выражение для этих функций рекомендуется задавать сырым текстовым литералом (например, r'foo\.' вместо 'foo\\.'). Сырые литералы отключают питоновское экранирование, которое легко перепутать с экранированием в рамках языка регулярных выражений.

Если выражение было скомпилировано, у результата компиляции есть методы search, match и fullmatch, аналогичные функциям re.search, re.match и re.fullmatch. Эти функции работают так:

search ищет разбиение вида AXB, где X удовлетворяет выражению
match ищет разбиение вида XB, где X удовлетовряет выражению
fullmatch просто распознаёт текст при помощи выражения

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

Практическое задание по анализу файла

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

Напомним, что считать файл построчно можно выражением вида

with open(имя_файла, 'r') as f:    
    for line in f:                   
        ...