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

'''Регуля́рные выраже́ния''' ({{lang-en|regular expressions}}, [[w:жаргон|жарг.]] '''''регэ́кспы''''' или '''''ре́гексы''''') — система обработки текста, основанная на специальной системе записи образцов для поиска. Образец ({{lang-en|pattern}}), задающий правило поиска, по-русски также иногда называют «шаблоном», «маской».

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

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

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

* (''[[w:строка (тип данных)|строка]]'') ''a'' в Σ обозначает множество {''a''}

* (''[[w:звезда Клини|''замыкание Клини'', ''звезда Клини'']]'') ''R''* обозначает минимальное [[супермножествоw:надмножество|надмножество]] из ''R'', которое содержит ε и закрыто связью строк. Это есть множество всех строк, которые могут быть получены связью нуля или более строк из ''R''. Например, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", … }.

|Где ''n'' — это [[w:цифра|цифра]] от 1 до 9; соответствует ''n''-му отмеченному подвыражению. Эта конструкция теоретически '''нерегулярна''', она не была принята в расширенном синтаксисе регулярных выражений.

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

Квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются «жадными», англ. ''greedy''). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение <code><nowiki>(<.*>)</nowiki></code> найдёт в тексте [[w:тег|тег]]и [[w:HTML|HTML]]. Однако этому выражению соответствует целиком строка

Регулярные выражения в [[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:Вильямс (издательство)|«Вильямс»]]

|издательство = [[w:Вильямс (издательство)|«Вильямс»]]

* [http://wwwblog.regexpalstevenlevithan.com/ ПрограммаA JavaScript дляand тестированияregular регулярныхexpression выраженийcentric blog]

[[Категория:{{Темы|Программирование]]}}