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

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

Распространённость[править | править код]

Сейчас регулярные выражения используются многими текстовыми редакторами и утилитами для поиска и изменения текста на основе выбранных правил. Многие языки программирования уже поддерживают регулярные выражения для работы со строками. Например, Perl и Tcl имеют встроенный в их синтаксис механизм обработки регулярных выражений. Набор утилит (включая редактор sed и фильтр grep), поставляемых в дистрибутивах Unix, одним из первых способствовал популяризации понятия регулярных выражений.

Базовые понятия[править | править код]

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

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

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

Группировка

Круглые скобки используются для определения области действия и приоритета операторов. Например, «gray|grey» и «gr(a|e)y» являются разными образцами, но они оба описывают множество, содержащее gray и grey.

Квантификация

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

{m,n}: общее выражение, повторений может быть от m до n включительно.
{m,}: общее выражение, m и более повторений.
{,n}: общее выражение, не более n повторений.
?: Знак вопроса означает 0 или 1 раз, то же самое, что и {0,1}. Например, «colou?r» соответствует и color, и colour.
*: Звёздочка означает 0, 1 или любое число раз ({0,}). Например, «go*gle» соответствует ggle, gogle, google и др.
+: Плюс означает хотя бы 1 раз ({1,}). Например, «go+gle» соответствует gogle, google и т. д. (но не ggle).

Конкретный синтаксис регулярных выражений зависит от реализации.

История[править | править код]

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

Регулярные выражения в Perl и Tcl происходят от реализации, написанной Генри Спенсером. Филип Хазэль разработал библиотеку pcre (англ. Perl Compatible Regular Expressions — Perl-совместимые регулярные выражения), которая используется во многих современных инструментах, таких как PHP и Apache.

В теории формальных языков[править | править код]

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

(пустое множество) ∅ обозначает ∅
(пустая строка) ε обозначает множество {ε}
(строка) a в Σ обозначает множество {a}

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

(связь, конкатенация) RS обозначает множество { αβ | α из R и β из S }. Пример: {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.
(перечисление) R|S обозначает объединение R и S.
(замыкание Клини, звезда Клини) R* обозначает минимальное супермножество из R, которое содержит ε и закрыто связью строк. Это есть множество всех строк, которые могут быть получены связью нуля или более строк из R. Например, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", … }.

Многие книги используют символы ∪, + или ∨ для перечисления вместо вертикальной черты.

Синтаксис[править | править код]

Традиционные регулярные выражения в Unix[править | править код]

Синтаксис «базовых» регулярных выражений Unix на данный момент определён POSIX как устаревший, но он до сих пор широко распространён из соображений обратной совместимости. Многие Unix-утилиты используют такие регулярные выражения по умолчанию.

В этом синтаксисе большинство символов соответствуют сами себе («a» соответствует «a» и т. д.). Исключения из этого правила называются метасимволами:

.	Соответствует любому единичному символу.
[ ]	Соответствует любому единичному символу из числа заключённых в скобки. Символ «-» интерпретируется буквально только в том случае, если он расположен непосредственно после открывающей или перед закрывающей скобкой: [abc-] или [-abc]. В противном случае, он обозначает интервал символов. Например, [abc] соответствует «a», «b» или «c». [a-z] соответствует буквам нижнего регистра латинского алфавита. Эти обозначения могут и сочетаться: [abcq-z] соответствует a, b, c, q, r, s, t, u, v, w, x, y, z. Чтобы установить соответствие символам «[» или «]», достаточно, чтобы закрывающая скобка была первым символом после открывающей: [][ab] соответствует «]», «[», «a» или «b».
[^ ]	Соответствует единичному символу из числа тех, которых нет в скобках. Например, [^abc] соответствует любому символу, кроме «a», «b» или «c». [^a-z] соответствует любому символу, кроме символов нижнего регистра в латинском алфавите.
^	Соответствует началу текста (или началу любой строки в мультистроковом режиме).
$	Соответствует концу текста (или концу любой строки в мультистроковом режиме).
	Объявляет «отмеченное подвыражение», которое может быть использовано позже (см. следующий элемент: \n). «Отмеченное подвыражение» также является «блоком».
\n	Где n — это цифра от 1 до 9; соответствует n-му отмеченному подвыражению. Эта конструкция теоретически нерегулярна, она не была принята в расширенном синтаксисе регулярных выражений.
*	Звёздочка после выражения, соответствующего единичному символу, соответствует нулю или более копий этого выражения. Например, «[xyz]» соответствует пустой строке, «x», «y», «zx», «zyx», и т. д. \n, где n — это цифра от 1 до 9, соответствует нулю или более вхождений для соответствия n-го отмеченного подвыражения. Например, « $a.$ c\1» соответствует «abcab» и «abcaba», но не «abcac». Выражение, заключённое в « $» и «$ » и сопровождаемое «», следует считать неправильным. В некоторых случаях, оно соответствует нулю или более вхождений строки, которая была заключена в скобки. В других, оно соответствует выражению, заключённому в скобки, учитывая символ «*».
\{x,y\}	Соответствует последнему блоку, встречающемуся не менее x и не более y раз. Например, «a\{3,5\}» соответствует «aaa», «aaaa» или «aaaaa».

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

Многие диапазоны символов зависят от выбранных настроек локализации. POSIX стандартизовал объявление некоторых классов и категорий символов, как показано в следующей таблице:

POSIX класс	подобно	означает
[:upper:]	[A-Z]	символы верхнего регистра
[:lower:]	[a-z]	символы нижнего регистра
[:alpha:]	[A-Za-z]	символы верхнего и нижнего регистра
[:alnum:]	[A-Za-z0-9]	цифры, символы верхнего и нижнего регистра
[:digit:]	[0-9]	цифры
[:xdigit:]	[0-9A-Fa-f]	шестнадцатеричные цифры
[:punct:]	[.,!?:…]	знаки пунктуации
[:blank:]	[ \t]	пробел и TAB
[:space:]	[ \t\n\r\f\v]	символы пропуска
[:cntrl:]		символы управления
[:graph:]	[^ \t\n\r\f\v]	символы печати
[:print:]	[^\t\n\r\f\v]	символы печати и символы пропуска

«Жадные» выражения[править | править код]

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

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

Современные (расширенные) регулярные выражения в POSIX[править | править код]

Регулярные выражения в POSIX аналогичны традиционному Unix-синтаксису, но с добавлением некоторых метасимволов:

+	Указывает на то, что предыдущий символ или группа может повторяться один или несколько раз. В отличие от звёздочки, хотя бы одно повторение обязательно.
?	Делает предыдущий символ или группу необязательной. Другими словами, в соответствующей строке она может отсутствовать, либо присутствовать ровно один раз.
\|	Разделяет альтернативные варианты регулярных выражений. Один символ задаёт две альтернативы, но их может быть и больше, достаточно использовать больше вертикальных чёрточек. Необходимо помнить, что этот оператор использует максимально возможную часть выражения. По этой причине, оператор альтернативы чаще всего используется внутри скобок.

Также было отменено использование обратной косой черты: \{…\} становится {…} и $…$ становится (…).

Perl-совместимые регулярные выражения (PCRE)[править | править код]

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

Реализации[править | править код]

NFA (Nondeterministic Finite State Machine; Недетерминированные Конечные Автоматы) используют «жадный» алгоритм отката, проверяя все возможные расширения регулярного выражения в определённом порядке и выбирая первое подходящее значение. NFA может обрабатывать подвыражения и обратные ссылки. Но из-за алгоритма отката традиционный NFA может проверять одно и то же место несколько раз, что отрицательно сказывается на скорости работы. Поскольку традиционный NFA принимает первое найденное соответствие, он может и не найти самое длинное из вхождений (этого требует стандарт POSIX, и существуют модификации NFA выполняющие это требование — GNU sed). Именно такой механизм регулярных выражений используется, например, в Perl, Tcl и .NET.
DFA (Deterministic Finite-state Automaton; Детерминированные Конечные Автоматы) работают линейно по времени, поскольку не используют откаты и никогда не проверяют какую-либо часть текста дважды. Они могут гарантированно найти самую длинную строку из возможных. DFA содержит только конечное состояние, следовательно, не обрабатывает обратных ссылок, а также не поддерживает конструкций с явным расширением, то есть не способен обработать и подвыражения. DFA используется, например, в lex и egrep.