Регулярные выражения: различия между версиями

оформление
(оформление)
{{википедия}}
'''Регуля́рные выраже́ния''' ({{lang-en|regular expressions}}, [[w:жаргон|жарг.]] '''''регэ́кспы''''' или '''''ре́гексы''''') — система обработки текста, основанная на специальной системе записи образцов для поиска. Образец ({{lang-en|pattern}}), задающий правило поиска, по-русски также иногда называют «шаблоном», «маской».
 
Сейчас регулярные выражения используются многими текстовыми редакторами и утилитами для поиска и изменения текста на основе выбранных правил. Многие языки программирования уже поддерживают регулярные выражения для работы со строками. Например, [[w:Perl|Perl]] и [[w:Tcl|Tcl]] имеют встроенный в их синтаксис механизм обработки регулярных выражений. Набор утилит (включая редактор sed и фильтр grep), поставляемых в дистрибутивах Unix, одним из первых способствовал популяризации понятия регулярных выражений.
 
== Базовые понятия ==
Регулярные выражения используются для сжатого описания некоторого [[w:множество|множества]] строк с помощью шаблонов, без необходимости перечисления всех элементов этого множества. При составлении шаблонов используется специальный [[w:Синтаксис (программирование)|синтаксис]], поддерживающий, обычно, следующие операции:
; Перечисление
: Вертикальная черта разделяет допустимые варианты. Например, «gray|grey» соответствует ''gray'' или ''grey''.
 
== В теории формальных языков ==
Регулярные выражения состоят из [[w:константа|констант]] и [[w:оператор|оператор]]ов, которые определяют [[w:множество|множества]] [[w:строка (программирование)|строк]] и множества [[w:операция|операций]] на них соответственно. На данном конечном [[w:алфавит|алфавит]]е Σ определены следующие константы:
* (''пустое множество'') ∅ обозначает ∅
* (''пустая строка'') ε обозначает множество {ε}
* (''[[w:строка (тип данных)|строка]]'') ''a'' в Σ обозначает множество {''a''}
и следующие операции:
* (''связь'', ''конкатенация'') ''RS'' обозначает множество { αβ | α из ''R'' и β из ''S'' }. Пример: {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.
* (''перечисление'') ''R|S'' обозначает объединение ''R'' и ''S''.
* (''[[w:звезда Клини|''замыкание Клини'', ''звезда Клини'']]'') ''R''* обозначает минимальное [[супермножествоw:надмножество|надмножество]] из ''R'', которое содержит ε и закрыто связью строк. Это есть множество всех строк, которые могут быть получены связью нуля или более строк из ''R''. Например, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", … }.
 
Многие книги используют символы ∪, + или ∨ для перечисления вместо вертикальной черты.
|- valign="top"
|\''n''
|Где ''n'' — это [[w:цифра|цифра]] от 1 до 9; соответствует ''n''-му отмеченному подвыражению. Эта конструкция теоретически '''нерегулярна''', она не была принята в расширенном синтаксисе регулярных выражений.
|- valign="top"
|*
|}
 
Различные реализации регулярных выражений интерпретируют обратную косую черту перед метасимволами по-разному. Например, [[w:egrep|egrep]] и [[w:Perl|Perl]] интерпретируют скобки и вертикальную черту как метасимволы, если перед ними ''нет'' обратной косой черты и воспринимают их как обычные символы, если черта есть.
 
Многие диапазоны символов зависят от выбранных настроек локализации. POSIX стандартизовал объявление некоторых классов и категорий символов, как показано в следующей таблице:
 
=== «Жадные» выражения ===
Квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются «жадными», англ. ''greedy''). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение <code><nowiki>(<.*>)</nowiki></code> найдёт в тексте [[w:тег|тег]]и [[w:HTML|HTML]]. Однако этому выражению соответствует целиком строка
 
<code>{{Highlight|<nowiki><p><b>Википедия</b> — свободная энциклопедия, в которой <i>каждый</i> может изменить или дополнить любую статью</p></nowiki>}}</code>.
=== Современные (расширенные) регулярные выражения в POSIX ===
 
Регулярные выражения в [[w:POSIX|POSIX]] аналогичны традиционному Unix-синтаксису, но с добавлением некоторых метасимволов:
 
{|
Также было отменено использование обратной косой черты: \{…\} становится {…} и \(…\) становится (…).
 
=== Perl-совместимые регулярные выражения ([[w:PCRE|PCRE]]) ===
Регулярные выражения в [[w:Perl|Perl]] имеют более богатый и в то же время предсказуемый синтаксис, чем даже в POSIX. По этой причине очень многие приложения используют именно Perl-совместимый синтаксис регулярных выражений.
 
=== Группы ===
 
== Реализации ==
* NFA (Nondeterministic Finite State Machine; [[недетерминированный конечныйw:Конечный автомат|Недетерминированные Конечные Автоматы]]) используют «жадный» алгоритм отката, проверяя все возможные расширения регулярного выражения в определённом порядке и выбирая первое подходящее значение. NFA может обрабатывать подвыражения и обратные ссылки. Но из-за алгоритма отката традиционный NFA может проверять одно и то же место несколько раз, что отрицательно сказывается на скорости работы. Поскольку традиционный NFA принимает первое найденное соответствие, он может и не найти самое длинное из вхождений (этого требует стандарт [[w:POSIX|POSIX]], и существуют модификации NFA выполняющие это требование — [[w:sed|GNU sed]]). Именно такой механизм регулярных выражений используется, например, в [[w:Perl|Perl]], [[w:Tcl|Tcl]] и [[w:.NET|.NET]].
* DFA (Deterministic Finite-state Automaton; [[детерминированный конечныйw:Конечный автомат|Детерминированные Конечные Автоматы]]) работают линейно по времени, поскольку не используют откаты и никогда не проверяют какую-либо часть текста дважды. Они могут гарантированно найти самую длинную строку из возможных. DFA содержит только конечное состояние, следовательно, не обрабатывает обратных ссылок, а также не поддерживает конструкций с явным расширением, то есть не способен обработать и подвыражения. DFA используется, например, в [[w:lex|lex]] и [[w:egrep|egrep]].
 
== Литература ==
|издание =
|место = М.
|издательство = [[w:Вильямс (издательство)|«Вильямс»]]
|год = 2006
|страницы =496
|издание =
|место = М.
|издательство = [[w:Вильямс (издательство)|«Вильямс»]]
|год = 2004
|страницы = 192
 
== Ссылки ==
* [http://www.regular-expressions.info/ Regular-Expressions.info — Regex Tutorial, Examples and Reference - Regexp Patterns]
* [http://regexp.ru/ Практическое использование регулярных выражений для веб-программирования]
* [http://www.regexguru.com/ Regex Guru Blog]
* [http://www.pcre.ru/ Документация, примеры и конструктор регулярных выражений]
* [http://wwwblog.regexpalstevenlevithan.com/ ПрограммаA JavaScript дляand тестированияregular регулярныхexpression выраженийcentric blog]
* [http://xregexp.com/ The one of a kind JavaScript regular expression library]
* [http://regexpal.com/ A JavaScript regular expression tester]
* [http://easyregexpregexp-online.rucom/ Онлайн проверка и оптимизациягенератор регулярных выражений]
* [http://easyregexp.ru/ Онлайн сервис по работе с регулярными выражениями]
* [http://www.pcre.ru/ PCRE.RU — Регулярные выражения, примеры, документация и шаблоны в perl, php, javascript, apache]
* [https://regex101.com/ Online regex tester and debugger: JavaScript, Python, PHP, and PCRE]
* [http://reg-exp.com/ Regular expression tester]
* [http://www.regexplanet.com/ RegexPlanet — Online Regular Expression (Regex) Testing and Cookbook]
* [http://www.rexegg.com/ Regex Tutorial: From Regex 101 to Advanced Regex]
* [http://javascript.ru/basic/regular-expression Регулярные выражения в JavaScript]
* [http://2lx.ru/2009/02/regulyarnye-vyrazheniya-v-c/ Регулярные выражения в C#]
* [http://yandex.ru/yandsearch?text=%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0%20%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D1%85%20%D0%B2%D1%8B%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B9 Проверка регулярных выражений]
* [http://pcreonline.com/ Площадка для тестирования и хранения регулярных выражений]
* [http://easyregexp.ru/ Онлайн проверка и оптимизация регулярных выражений]
 
[[Категория:{{Темы|Программирование]]}}
7076

правок