Регулярные выражения: различия между версиями
MaxSem (обсуждение | вклад) начато на основе w:Регулярные выражения |
(нет различий)
|
Версия от 21:13, 7 января 2008
Регуля́рные выраже́ния (англ. regular expressions, жарг. регэ́кспы или ре́гексы) — система обработки текста, основанная на специальной системе записи образцов для поиска. Образец (англ. pattern), задающий правило поиска, по-русски также иногда называют «шаблоном», «маской».
Сейчас регулярные выражения используются многими текстовыми редакторами и утилитами для поиска и изменения текста на основе выбранных правил. Многие языки программирования уже поддерживают регулярные выражения для работы со строками. Например, 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).
Конкретный синтаксис регулярных выражений зависит от реализации.
В теории формальных языков
Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. На данном конечном алфавите Σ определены следующие константы:
- (пустое множество) ∅ обозначает ∅
- (пустая строка) ε обозначает множество {ε}
- (строка) 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-му отмеченному подвыражению. Эта конструкция теоретически нерегулярна, она не была принята в расширенном синтаксисе регулярных выражений. |
* |
|
\{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] | символы печати и символы пропуска |
Защита метасимволов
Cпособ представить сами метасимволы ., - [ ] и другие в регулярных выражениях без интерпретации, то есть, в качестве простых (не специальных) символов — предварить их обратной косой чертой: \. Например, чтобы представить сам символ «точка» (просто точка, и ничего более), надо написать \. (обратная косая черта, а за ней - точка). Чтобы представить символ открывающей квадратной скобки [, надо написать \[ (обратная косая черта и следом за ней скобка [) и т.д. Сам метасимвол \ тоже может быть защищен, то есть представлен как \\ (две обратных косых черты), и тогда интерпретатор регулярных выражений воспримет его как простой символ обратной косой черты \.
«Жадные» выражения
Квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются «жадными», англ. greedy). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение (<.*>)
найдёт в тексте теги HTML. Однако этому выражению соответствует целиком строка
<p><b>Википедия</b> — свободная энциклопедия, в которой <i>каждый</i> может изменить или дополнить любую статью</p>
.
Эту проблему можно решить двумя способами. Первый состоит в том, что в регулярном выражении учитываются символы, не соответствующие желаемому образцу (<[^>]*>
для вышеописанного случая). Второй заключается в определении квантификатора как нежадного (ленивого, англ. lazy)— большинство реализаций позволяют это сделать, добавив после него знак вопроса.
Например, выражению (<.*?>)
соответствует не вся показанная выше строка, а отдельные теги (выделены цветом):
<p><b>Википедия</b> — свободная энциклопедия, в которой <i>каждый</i> может изменить или дополнить любую статью</p>
*?
- «не жадный» («ленивый») эквивалент*
+?
- «не жадный» («ленивый») эквивалент+
{n,}?
- «не жадный» («ленивый») эквивалент{n,}
Использование «ленивых» квантификаторов, правда, может повлечь за собой обратную проблему, когда выражению соответствует слишком короткая строка.
Современные (расширенные) регулярные выражения в 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.
Литература
- Билл Смит Методы и алгоритмы вычислений на строках (regexp) = Computing Patterns in Strings. — М.: «Вильямс», 2006. — С. 496. — ISBN 0-201-39839-7
- Фридл Дж. Регулярные выражения. Библиотека программиста. — СПб.: Питер, 2001. 352 с. ISBN 5-318-00056-8.
- Бен Форта Освой самостоятельно регулярные выражения (regexp). PHP, Perl, JavaScript, Java, C#(си шарп), Visual Basic, ASP.NET,JSP, MySQL, Unix, Linux = Sams Teach Yourself Regular Expressions in 10 Minutes. — М.: «Вильямс», 2004. — С. 192. — ISBN 0-672-32566-7
Ссылки
- Практическое использование регулярных выражений для веб-программирования
- Документация, примеры и конструктор регулярных выражений
- Применение регулярных выражений в Perl с примерами
- Программа JavaScript для тестирования регулярных выражений
- Форум посвященный регулярным выражениям в Perl
- Регулярные выражения в JavaScript
- Проверка регулярных выражений