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

Регуля́рные выраже́ния (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэ́кспы или ре́гексы) — система синтаксического разбора текстовых фрагментов по формализованному шаблону, основанная на системе записи образцов для поиска. Образец (англ. pattern), задающий правило поиска, по-русски также иногда называют «шаблоном», «маской». Регулярные выражения произвели прорыв в электронной обработке текста в конце XX века. Они являются развитием символов-джокеров (англ. wildcard characters).

Сейчас регулярные выражения используются многими текстовыми редакторами и утилитами для поиска и изменения текста на основе выбранных правил. Многие языки программирования уже поддерживают регулярные выражения для работы со строками. Например, [1], .NET Framework^[2], PHP, Python, Ruby и др. имеют встроенную поддержку регулярных выражений. Набор утилит (включая редактор grep), поставляемых в дистрибутивах

История

Истоки регулярных выражений лежат в теории автоматов и теории формальных языков. Эти области изучают вычислительные модели (автоматы) и способы описания и классификации формальных языков. В 1940-х гг. Уоррен Маккалок и Уолтер Питтс описали нервную систему, используя простой автомат в качестве модели нейрона. Математик Стивен Клини позже описал эти модели, используя свою систему математических обозначений, названную «регулярные множества». Кен Томпсон встроил их в редактор QED, а затем в редактор expr, awk, vi, Perl.

Регулярные выражения в Perl и Tcl происходят от реализации, написанной Генри Спенсером. Филип Хейзел разработал библиотеку англ. Perl-compatible regular expressions — Perl-совместимые регулярные выражения), которая используется во многих современных инструментах, таких как Apache.

В теории формальных языков

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

• (пустое множество) ∅.
• (пустая строка (англ.)) ε обозначает строку, не содержащую ни одного символа. Эквивалентно «».
• (строка) «a», где a — символ алфавита Σ, обозначает строку, состоящую из одного этого символа.

и следующие операции:

• (сцепление, конкатенация) RS обозначает множество {αβ | α ∈ R & β ∈ S}. Например, {«boy», «girl»}{«friend», «cott»} = {«boyfriend», «girlfriend», «boycott», «girlcott»}.
• (дизъюнкция, перечисление) R|S обозначает объединение R и S.^[3]
• (замыкание Клини, звезда Клини) R* обозначает минимальное надмножество множества R, которое содержит ε и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {«Go», «Russia»}* = {ε, «Go», «Russia», «GoGo», «GoRussia», «RussiaGo», «RussiaRussia», «GoGoGo», «GoGoRussia», «GoRussiaGo», …}.

Синтаксис

Представление символов

Основная статья: Представление символов в регулярных выражениях

Обычные символы (литералы) и специальные символы (метасимволы)

Большинство символов в регулярном выражении представляют сами себя за исключением специальных символов [ ] \ ^ $ . | ? * + ( ) { }, которые могут быть предварены символом \ (обратная косая черта) («экранированы», «защищены») для представления их самих в качестве символов текста. Можно экранировать целую последовательность символов, заключив её между \Q и \E.

Пример	Соответствие
a\.?	a. или a
a\\\\b	a\\b
a\[F\]	a[F]
\Q+-*/\E	+-*/

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

Любой символ

Метасимвол . (точка) означает один любой символ.

Символьные классы (наборы символов)

Набор символов в квадратных скобках [ ] именуется символьным классом и позволяют указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. В частности, [абв] задаёт возможность появления в тексте одного из трёх указанных символов, а [1234567890] задаёт соответствие одной из цифр. Возможно указание диапазонов символов: например, [А-Яа-я] соответствует буквам русского алфавита.^[4]

Если требуется указать символы, которые не входят в указанный набор, то используют символ ^ внутри квадратных скобок, например [^0-9] означает любой символ, кроме цифр.

Добавление в набор специальных символов путём экранирования — самый бесхитростный способ. Однако в современных регулярных выражениях унаследован также и традиционный подход — см. Традиционные регулярные выражения.

Позиция внутри строки

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

Представление	Позиция	Пример	Соответствие
^	Начало строки	^a	aaa aaa
$	Конец строки	a$	aaa aaa
\b	Граница слова	a\b	aaa aaa
		\ba	aaa aaa
\B	Не граница слова	\Ba\B	aaa aaa
\G	Предыдущий успешный поиск	\Ga	aaa aaa (поиск остановился на 4-й позиции — там, где не нашлось a)

Квантификация (поиск последовательностей)

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

Представление	Число повторений	Пример	Соответствие
{n}	Ровно n	colou{3}r	colouuur
{m,n}	От m до n включительно	colou{2,4}r	colouur, colouuur, colouuuur
{m,}	Не менее m	colou{2,}r	colouur, colouuur, colouuuur и т. д.
{,n}	Не более n	colou{,3}r	color, colour, colouur, colouuur

Представление	Число повторений	Эквивалент	Пример	Соответствие
*	Ноль или более	{0,}	colou*r	color, colour, colouur и т. д.
+	Одно или более	{1,}	colou+r	colour, colouur и т. д. (но не color)
?	Ноль или одно	{0,1}	colou?r	color, colour

Часто используется последовательность .* для обозначения любого количества любых символов между двумя частями регулярного выражения.

Символьные классы в сочетании с квантификаторами позволяют устанавливать соответствия с реальными текстами. Например, столбцами цифр, телефонами, почтовыми адресами, элементами

Если символы { } не образуют квантификатор, их специальное значение игнорируется.

Жадная и ленивая квантификация

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

Выражение (<.*>) соответствует строке, содержащей несколько тегов

<p><b>Википедия</b> — свободная энциклопедия, в которой <i>каждый</i> может изменить или дополнить любую статью</p>.

Чтобы выделить отдельные теги, можно применить ленивую версию этого выражения: (<.*?>) Ей соответствует не вся показанная выше строка, а отдельные теги (выделены цветом):

<p><b>Википедия</b> — свободная энциклопедия, в которой <i>каждый</i> может изменить или дополнить любую статью</p>.

В некоторых реализациях квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются жадными, англ. greedy). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение (<.*>) найдёт в тексте теги

<p><b>Википедия</b> — свободная энциклопедия, в которой <i>каждый</i> может изменить или дополнить любую статью</p>.

Эту проблему можно решить двумя способами.

1. Учитывать символы, не соответствующие желаемому образцу (<[^>]*> для вышеописанного случая).
2. Определить квантификатор как нежадный (ленивый, англ. lazy) — большинство реализаций позволяют это сделать, добавив после него знак вопроса.

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

Жадный	Ленивый
*	*?
+	+?
{n,}	{n,}?

Также общей проблемой как жадных, так и ленивых выражений являются точки возврата для перебора вариантов выражения. Точки ставятся после каждой итерации квантификатора. Если интерпретатор не нашёл соответствия после квантификатора, то он начинает возвращаться по всем установленным точкам, пересчитывая оттуда выражение по-другому.

См. также статью: Жадность (регулярные выражения)

Ревнивая квантификация

Пример неревнивого поиска выражения

Интерпретатор при поиске выражения (a+a+)+b в строке aaaaa пойдёт приблизительно по следующему пути:

1. aaaaa
2. aaaaa
3. aaaaa
4. aaaaa
5. aaaaa
6. aaaaa
7. aaaaa — и только тут, потратив все точки возврата, сдастся

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

В отличие от обычной (жадной) квантификации, такая квантификация не только старается найти максимально длинный вариант, но ещё и не позволяет возвращаться назад впоследствии для перебора других возможных вариантов.

Жадный	Ревнивый
*	*+
?	?+
+	++
{n,}	{n,}+

Пример	Соответствие
ab[xa]*+a	abxaabxa; но не abxaabxa, так как буква a уже занята

Группировка

Обозначение группы

Круглые скобки используются для определения области действия и приоритета операций. Шаблон внутри группы обрабатывается как единое целое и может быть квантифицирован. Например, выражение (gr[ae]y-?)* найдёт последовательность вида grey-gray-grey-grey-gray.

Обратная связь

Одно из применений группировки — повторное использование ранее найденных групп символов (подстрок, блоков, отмеченных подвыражений). При обработке выражения подстро́ки, найденные по шаблону внутри группы, сохраняются в отдельной области памяти и получают номер начиная с единицы. Квантификация группы не влияет на сохранённый результат, то есть сохраняется лишь первое вхождение. Обычно поддерживается до 9 нумерованных подстрок с номерами от 1 до 9, но некоторые интерпретаторы позволяют работать с бо́льшим количеством. В последствии в пределах данного регулярного выражения можно использовать обозначения от \1 до \9 для проверки на совпадение с ранее найденной подстрокой.

Например, регулярное выражение (grey|gray)-\1 найдёт строку grey-grey или gray-gray, но пропустит строку grey-gray.

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

Группировка без обратной связи

Если группа используется только для группировки и её результат в дальнейшем не потребуется, то можно использовать группировку вида (?:шаблон). Под результат такой группировки не выделяется отдельная область памяти и, соответственно, ей не назначается номер. Это положительно влияет на скорость выполнения выражения, но понижает удобочитаемость.

Атомарная группировка

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

Пример	Соответствие	Создаваемые группы
a(bc|b|x)cc	abccaxcc abccaxcc	abccaxcc abccaxcc
a(?:bc|b|x)cc		нет
a(?>bc|b|x)cc	abccaxcc но не abccaxcc: вариант bc найден, остальные проигнорированы
a(?>x*)xa	не найдётся axxxa: все x заняты, и нет возврата внутрь группы

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

Модификаторы

Модификаторы действуют с момента вхождения и до конца регулярного выражения или противоположного модификатора. Некоторые интерпретаторы могут применить модификатор ко всему выражению, а не с момента его вхождения.

Синтаксис	Описание
(?i)	Включает	нечувствительность выражения к регистру символов (англ. case insensitivity)
(?-i)	Выключает
(?s)	Включает	режим соответствия точки символам переноса строки и возврата каретки
(?-s)	Выключает
(?m)	Символы ^ и $ вызывают соответствие только	после и до символов новой строки
(?-m)		с началом и концом строки
(?x)	Включает	режим без учёта пробелов между частями регулярного выражения и позволяет использовать # для комментариев
(?-x)	Выключает

Группы-модификаторы можно объединять в одну группу: (?i-sm). Такая группа включает режим i, m и выключает режим s. Если использование модификаторов требуется только в пределах группы, то нужный шаблон указывается внутри группы после модификаторов и двоеточия. Например, (?-i)(?i:tV)set найдёт TVset, но не TVSET.

Комментарии

Для добавления комментариев в регулярное выражение можно использовать группы-комментарии вида (?#комментарий). Такая группа интерпретатором полностью игнорируется и не проверяется на вхождение в текст. Например, выражение А(?#тут комментарий)Б соответствует строке АБ.

Перечисление

Вертикальная черта разделяет допустимые варианты. Например, gray|grey соответствует gray или grey. Следует помнить, что перебор вариантов выполняется слева направо, как они указаны.

Если требуется указать перечень вариантов внутри более сложного регулярного выражения, то его нужно заключить в группу. Например, gray|grey или gr(a|e)y описывают строку gray или grey. В случае с односимвольными альтернативами предпочтителен вариант gr[ae]y, так как сравнение с символьным классом выполняется проще, чем обработка группы с проверкой на все её возможные модификаторы и генерацией обратной связи.

Просмотр вперёд и назад

В большинстве реализаций регулярных выражений есть способ производить поиск фрагмента текста, «просматривая» (но не включая в найденное) окружающий текст, который расположен до или после искомого фрагмента текста. Например, таким способом легко найти имя тега HTML, не включая в результат поиска окружающие его угловые скобки или другие знаки, но и не упуская их «из внимания» при поиске нужного контекста. Просмотр с отрицанием используется реже и «следит» за тем, чтобы указанные соответствия, напротив, не встречались до или после искомого текстового фрагмента.

Представление	Вид просмотра	Пример	Соответствие
(?=шаблон)	Позитивный просмотр вперёд	Людовик(?=XVI)	ЛюдовикXV, ЛюдовикXVI, ЛюдовикXVIII, ЛюдовикLXVII, ЛюдовикXXL
(?!шаблон)	Негативный просмотр вперёд (с отрицанием)	Людовик(?!XVI)	ЛюдовикXV, ЛюдовикXVI, ЛюдовикXVIII, ЛюдовикLXVII, ЛюдовикXXL
(?<=шаблон)	Позитивный просмотр назад	(?<=Сергей )Иванов	Сергей Иванов, Игорь Иванов
(?<!шаблон)	Негативный просмотр назад (с отрицанием)	(?<!Сергей )Иванов	Сергей Иванов, Игорь Иванов

Поиск по условию

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

Представление	Пояснение	Пример	Соответствие
(?(?=если)то|иначе)	Если операция просмотра успешна, то далее выполняется часть то, иначе выполняется часть иначе. В выражении может использоваться любая из четырёх операций просмотра. Следует учитывать, что операция просмотра нулевой ширины, поэтому части то в случае позитивного или иначе в случае негативного просмотра должны включать в себя описание шаблона из операции просмотра.	(?(?<=а)м|п)	мам,пап
(?(n)то|иначе)	Если n-я группа вернула значение, то поиск по условию выполняется по шаблону то, иначе по шаблону иначе.	(а)?(?(1)м|п)	мам,пап

Версии регулярных выражений

Традиционные регулярные выражения в англ. basic regular expressions (BRE)) на данный момент определён

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

• .
• [ ]
• [^ ]
• ^
• $
• *
• \{ \} — первоначальный вариант для { }
• \( \) — первоначальный вариант для ( )
• \n, где n — номер от 1 до 9

Особенности:

• Звёздочка должна следовать после выражения, соответствующего единичному символу. Пример: [xyz]*.
• Выражение \(блок\)* следует считать неправильным. В некоторых случаях оно соответствует нулю или более повторений строки блок. В других оно соответствует строке блок*.
• Внутри символьного класса специальные значения символов, в основном, игнорируются. Особые случаи:
  • Чтобы добавить символ ^ в набор, его следует поместить туда не первым.
  • Чтобы добавить символ - в набор, его следует поместить туда первым или последним. Например:
    • шаблон DNS-имени, куда могут входить буквы, цифры, минус и точка-разделитель: [-0-9a-zA-Z.];
    • любой символ, кроме минуса и цифры: [^-0-9].
  • Чтобы добавить символ [ или ] в набор, его следует поместить туда первым. Например:
    • [][ab] соответствует ], [, a или b.

Расширенные регулярные выражения в стандарте POSIX

Синтаксис расширенных регулярных выражений англ. extended regular expressions (ERE)) в основном аналогичен традиционному.

• Отменено использование обратной косой черты для метасимволов { } и ( ).
• Обратная косая черта перед метасимволом отменяет его специальное значение (см. Представление специальных символов).
• Отвергнута теоретически нерегулярная конструкция \n.
• Добавлены метасимволы +, ?, |.

См. также статью: Символьные классы POSIX

Регулярные выражения, совместимые с Основная статья: англ. Perl-compatible regular expressions (PCRE)) имеют более богатый и в то же время предсказуемый синтаксис, чем даже POSIX ERE. По этой причине очень многие приложения используют именно Perl-совместимый синтаксис регулярных выражений.

Реализации

• NFA (англ. nondeterministic finite-state automata — недетерминированные конечные автоматы) используют жадный алгоритм отката, проверяя все возможные расширения регулярного выражения в определённом порядке и выбирая первое подходящее значение. NFA может обрабатывать подвыражения и обратные ссылки. Но из-за алгоритма отката традиционный NFA может проверять одно и то же место несколько раз, что отрицательно сказывается на скорости работы. Поскольку традиционный NFA принимает первое найденное соответствие, он может и не найти самое длинное из вхождений (этого требует стандарт GNU sed). Именно такой механизм регулярных выражений используется, например, в Tcl и .NET.
• DFA (англ. deterministic finite-state automata — детерминированные конечные автоматы) работают линейно по времени, поскольку не используют откаты и никогда не проверяют какую-либо часть текста дважды. Они могут гарантированно найти самую длинную строку из возможных. DFA содержит только конечное состояние, следовательно, не обрабатывает обратных ссылок, а также не поддерживает конструкций с явным расширением, то есть не способен обработать и подвыражения. DFA используется, например, в egrep.

Примечания

1. ↑ java.sun.com
2. ↑ MSDN
3. ↑ Во многих книгах используются символы ∪, + или ∨ вместо |.
4. ↑ Для использования последовательностей букв необходимо установить правильную кодовую страницу в которой эти последовательности будут идти в порядке от и до указанных символов. Для русского языка это ISO 8859-5 и Юникод, так как в DOS-855, DOS-866 и KOI8-R русские буквы не идут одной целой группой или не упорядочены по алфавиту.

Литература

• Фридл, Дж. Регулярные выражения. — СПб.: «Питер», 2001. — 352 с. — (Библиотека программиста). — ISBN 5-318-00056-8
• Смит, Билл. Методы и алгоритмы вычислений на строках (regexp) = Computing Patterns in Strings. — М.: «Вильямс», 2006. — 496 с. — ISBN 0-201-39839-7
• Форта, Бен. Освой самостоятельно регулярные выражения. 10 минут на урок = Sams Teach Yourself Regular Expressions in 10 Minutes. — М.: «Вильямс», 2005. — 184 с. — ISBN 5-8459-0713-6

Ссылки

• Практическое использование регулярных выражений для веб-программирования
• Справочник и ресурсы по регулярным выражениям(англ.) — учебник и детальное описание синтаксиса с примерами, сравнение различных интерпретаторов и прочее
• MSDN(англ.)
• MSDN - Знакомство с регулярными выражениями(рус.)
• Онлайн-редактор регулярных выражений (PCRE) с полной подсветкой синтаксиса (java-applet)(англ.)
• Сборник регулярных выражений в разных форматах(англ.)
• Полезные ссылки по регулярным выражениям — каталог полезных ссылок по использованию регулярных выражений в различных языках программирования
• Программа на JavaScript для тестирования регулярных выражений(англ.)
• Проверка регулярных выражений
• Онлайн-валидатор регулярных выражений для JavaScript(англ.)
• Программа-валидатор регулярных выражений для .NET(рус.)