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

Результаты сопоставления шаблона

(? < = \ .) {2,}(?= [AZ] )

Соответствуют по крайней мере два пробела, но только если они стоят непосредственно после точки (.) и перед заглавной буквой.

Стивен Коул Клини , представивший концепцию

Черный список в Википедии , который использует регулярные выражения для выявления плохих заголовков .

Регулярное выражение (сокращенно regex или regexp ; ^[1] также называется рациональным выражением ^[2]^[3] ) — это последовательность символов , определяющая шаблон поиска в тексте . Обычно такие шаблоны используются алгоритмами поиска строк для операций «найти» или «найти и заменить» над строками или для проверки ввода. Это метод, разработанный в теоретической информатике и теории формального языка .

Концепция регулярных выражений зародилась в 1950-х годах, когда американский математик Стивен Коул Клини формализовал описание регулярного языка . Они стали широко использоваться с утилитами обработки текста Unix . Различные синтаксисы для написания регулярных выражений существуют с 1980-х годов, один из которых является стандартом POSIX , а другой, широко используемый, является синтаксисом Perl .

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

История

Регулярные выражения возникли в 1951 году, когда математик Стивен Коул Клини описал регулярные языки, используя свою математическую нотацию, называемую регулярными событиями . ^[4]^[5] Они возникли в теоретической информатике , в подразделах теории автоматов (модели вычислений), а также в описании и классификации формальных языков . Другие ранние реализации сопоставления с образцом включают язык SNOBOL , который не использовал регулярные выражения, а вместо этого использовал собственные конструкции сопоставления с образцом.

Регулярные выражения стали широко использоваться с 1968 года в двух случаях: сопоставление с образцом в текстовом редакторе ^[6] и лексический анализ в компиляторе. ^[7] Одно из первых проявлений регулярных выражений в программной форме было, когда Кен Томпсон встроил нотацию Клини в редактор QED как средство сопоставления шаблонов в текстовых файлах . ^[6]^[8]^[9]^[10] Для ускорения Томпсон реализовал сопоставление регулярных выражений с помощью JIT -компиляции с кодом IBM 7094 в Compatible Time-Sharing System , важном раннем примере JIT-компиляции. ^[11]Позже он добавил эту возможность в редактор Unix ed , что в конечном итоге привело к использованию регулярных выражений в популярном инструменте поиска grep («grep» — это слово, полученное из команды для поиска по регулярному выражению в редакторе ed: это означает «Глобальный поиск для регулярных выражений и совпадающих строк печати"). ^[12] Примерно в то же время, когда Томпсон разработал QED, группа исследователей, включая Дугласа Т. Росса , внедрила инструмент, основанный на регулярных выражениях, который используется для лексического анализа при разработке компилятора . ^[7]g/re/p

Многие вариации этих оригинальных форм регулярных выражений использовались в программах Unix ^[10] в Bell Labs в 1970-х, включая vi , lex , sed , AWK и expr , а также в других программах, таких как Emacs . Впоследствии регулярные выражения были приняты широким кругом программ, причем эти ранние формы были стандартизированы в стандарте POSIX.2 в 1992 году.

В 1980-х годах более сложные регулярные выражения появились в Perl , который первоначально был получен из библиотеки регулярных выражений, написанной Генри Спенсером (1986), который позже написал реализацию расширенных регулярных выражений для Tcl . ^[13] Библиотека Tcl представляет собой гибридную реализацию NFA / DFA с улучшенными характеристиками производительности. Программные проекты, в которых реализована реализация регулярных выражений Tcl Спенсера, включают PostgreSQL . ^[14] Позже Perl расширил исходную библиотеку Спенсера, добавив много новых функций. ^[15] Часть усилий по дизайну Раку(ранее называвшийся Perl 6) призван улучшить интеграцию Perl с регулярными выражениями, а также расширить их возможности и возможности, чтобы разрешить определение грамматик синтаксического анализа выражений . ^[16] Результатом стал мини-язык под названием Raku rules , который используется для определения грамматики Raku, а также предоставляет инструмент для программистов на этом языке. Эти правила сохраняют существующие функции регулярных выражений Perl 5.x, но также позволяют определять синтаксический анализатор рекурсивного спуска в стиле BNF с помощью подправил.

Использование регулярных выражений в стандартах структурированной информации для моделирования документов и баз данных началось в 1960-х годах и расширилось в 1980-х годах, когда были объединены отраслевые стандарты, такие как ISO SGML (предшественник ANSI «GCA 101-1983»). Ядро стандартов языка спецификации структуры состоит из регулярных выражений. Его использование очевидно в синтаксисе группы элементов DTD .

Начиная с 1997 года Филип Хейзел разработал PCRE (Perl-совместимые регулярные выражения), который пытается точно имитировать функциональность регулярных выражений Perl и используется многими современными инструментами, включая PHP и HTTP-сервер Apache .

Сегодня регулярные выражения широко поддерживаются в языках программирования, программах обработки текста (в частности , лексерах ), продвинутых текстовых редакторах и некоторых других программах. Поддержка регулярных выражений является частью стандартной библиотеки многих языков программирования, включая Java и Python , и встроена в синтаксис других, включая Perl и ECMAScript . Реализации функциональности регулярных выражений часто называют механизмом регулярных выражений , и ряд библиотек доступен для повторного использования. В конце 2010-х несколько компаний начали предлагать аппаратные средства, FPGA , ^[17] GPU ^[18] реализации совместимых с PCREмеханизмы регулярных выражений , которые быстрее по сравнению с реализациями ЦП .

Узоры

Фраза регулярные выражения или регулярные выражения часто используется для обозначения определенного стандартного текстового синтаксиса для представления шаблонов для сопоставления текста, в отличие от математической нотации, описанной ниже. Каждый символ в регулярном выражении (то есть каждый символ в строке, описывающей его шаблон) является либо метасимволом , имеющим особое значение, либо обычным символом, имеющим буквальное значение. Например, в регулярном выраженииb., 'b' — буквальный символ, который соответствует только 'b', а '.' метасимвол, который соответствует всем символам, кроме новой строки. Следовательно, это регулярное выражение соответствует, например, «b%», или «bx», или «b5». Вместе метасимволы и литеральные символы могут использоваться для идентификации текста заданного шаблона или обработки нескольких его экземпляров. Совпадения с образцом могут варьироваться от точного равенства до очень общего сходства, что контролируется метасимволами. Например, .это очень общий шаблон [a-z](соответствует всем строчным буквам от «а» до «z») менее общий иbявляется точным шаблоном (соответствует только «b»). Синтаксис метасимволов разработан специально для представления заданных целей в сжатом и гибком виде, чтобы направлять автоматизацию обработки текста различных входных данных в форме, удобной для ввода с помощью стандартной клавиатуры ASCII .

Очень простой случай регулярного выражения в этом синтаксисе — найти слово, написанное двумя разными способами в текстовом редакторе , регулярное выражение seriali[sz]eсоответствует как «сериализовать», так и «сериализовать». Подстановочные знаки также достигают этого, но они более ограничены в том, что они могут создавать, поскольку у них меньше метасимволов и простая языковая база.

Обычный контекст подстановочных знаков заключается в объединении похожих имен в списке файлов, тогда как регулярные выражения обычно используются в приложениях, которые в целом сопоставляют текстовые строки с шаблоном. Например, регулярное выражение соответствует лишним пробелам в начале или конце строки. Расширенным регулярным выражением, которое соответствует любому числу, является .^[ \t]+|[ \t]+$[+-]?(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?

Перевод звезды Клини
( s * означает «ноль или более s »)

Процессор регулярных выражений преобразует регулярное выражение в приведенном выше синтаксисе во внутреннее представление, которое может быть выполнено и сопоставлено со строкой , представляющей искомый текст. Одним из возможных подходов является алгоритм построения Томпсона для построения недетерминированного конечного автомата (NFA), который затем делается детерминированным , и полученный детерминированный конечный автомат (DFA) запускается на целевой текстовой строке для распознавания подстрок, соответствующих регулярному выражению. На рисунке показана схема NFA, полученная из регулярного выражения , где sN(s*)s*в свою очередь обозначает более простое регулярное выражение, которое уже было рекурсивно переведено в NFA N ( s ).

Базовые концепты

Регулярное выражение, часто называемое шаблоном , задает набор строк, необходимых для определенной цели. Простой способ задать конечное множество строк — перечислить его элементы или члены. Однако часто есть более краткие способы: например, набор, содержащий три строки «Гендель», «Гендель» и «Гендель», может быть указан шаблоном H(ä|ae?)ndel; мы говорим, что этот шаблон соответствует каждой из трех строк. В большинстве формализмов, если существует хотя бы одно регулярное выражение, которое соответствует определенному набору, то существует бесконечное число других регулярных выражений, которые также ему соответствуют — спецификация не уникальна. Большинство формализмов предоставляют следующие операции для построения регулярных выражений.

логическое "или": Вертикальная черта разделяет альтернативы. Например, может соответствовать «серый» или «серый».gray|grey
Группировка: Круглые скобки используются для определения области действия и приоритета операторов (среди прочего). Например, gray|greyи являются эквивалентными шаблонами, которые оба описывают набор «серый» или «серый».gr(a|e)y
Количественная оценка: Квантификатор после токена (например, символа) или группы указывает, как часто может встречаться предшествующий элемент . Наиболее распространенными квантификаторами являются вопросительный знак ? , звездочка * (производная от звезды Клини ) и знак плюс + ( Клин плюс ).

`?`	Знак вопроса указывает на ноль или одно вхождение предшествующего элемента. Например, `colou?r`соответствует как «цвет», так и «цвет».
`*`	Звездочка указывает на ноль или более вхождений предыдущего элемента. Например, `ab*c`соответствует "ac", "abc", "abbc", "abbbc" и так далее.
`+`	Знак плюс указывает на одно или несколько вхождений предыдущего элемента. Например, `ab+c`соответствует «abc», «abbc», «abbbc» и т. д., но не «ac».
`{n}`^[19]	Предыдущий элемент соответствует ровно n раз.
`{min,}`^[19]	Предыдущий элемент соответствует min или более раз.
`{,max}`^[19]	Предыдущий элемент соответствует максимальному количеству раз.
`{min,max}`^[19]	Предыдущий элемент соответствует не менее min раз, но не более max раз.

Подстановочный знак

Подстановочный знак .соответствует любому символу. Например, a.bсоответствует любой строке, содержащей «а», затем любой символ, а затем «б»; и a.*bсоответствует любой строке, которая содержит «a», а затем символ «b» в какой-то более поздний момент.

Эти конструкции можно комбинировать для формирования произвольно сложных выражений, подобно тому, как можно строить арифметические выражения из чисел и операций +, -, × и ÷. Например, H(ae?|ä)ndelи являются допустимыми шаблонами, которые соответствуют тем же строкам, что и в предыдущем примере, .H(a|ae|ä)ndelH(ä|ae?)ndel

Точный синтаксис регулярных выражений зависит от инструмента и контекста; более подробно дано в § Синтаксис .

Теория формального языка

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

Формальное определение

Регулярные выражения состоят из констант, обозначающих наборы строк, и символов операторов, обозначающих операции над этими наборами. Следующее определение является стандартным и встречается в большинстве учебников по теории формального языка. ^[20]^[21] Для конечного алфавита Σ следующие константы определяются как регулярные выражения:

( пустое множество ) ∅, обозначающее множество ∅.
( пустая строка ) ε обозначает набор, содержащий только «пустую» строку, в которой вообще нет символов.
( буквальный символ ) aв Σ, обозначающий множество, содержащее только символ a .

Для заданных регулярных выражений R и S определены следующие операции над ними для создания регулярных выражений:

( конкатенация ) (RS)обозначает набор строк, которые могут быть получены путем объединения строки, принятой R, и строки, принятой S (в указанном порядке). Например, пусть R обозначает {"ab", "c"}, а S обозначает {"d", "ef"}. Затем (RS)обозначает {"abd", "abef", "cd", "cef"}.
( чередование ) (R|S)обозначает объединение множеств, описанных R и S. Например, если R описывает {"ab", "c"}, а S описывает {"ab", "d", "ef"}, выражение (R|S)описывает { «аб», «в», «г», «эф»}.
( звезда Клини ) (R*)обозначает наименьшее надмножество множества, описываемого R , которое содержит ε и замкнуто относительно конкатенации строк. Это набор всех строк, которые могут быть получены конкатенацией любого конечного числа (включая ноль) строк из набора, описанного R. Например, если R обозначает {"0", "1"}, (R*)обозначает набор всех конечные двоичные строки (включая пустую строку). Если R обозначает {"ab", "c"}, (R*)обозначает {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", . .. }.

Чтобы избежать скобок, предполагается, что звезда Клини имеет наивысший приоритет, затем конкатенация и затем чередование. Если нет двусмысленности, скобки можно опустить. Например, (ab)cможет быть записано как abc, а a|(b(c*))может быть записано как a|bc*. Многие учебники используют символы ∪, + или ∨ для чередования вместо вертикальной черты.

Примеры:

a|b* обозначает {ε, "a", "b", "bb", "bbb", ...}
(a|b)* обозначает множество всех строк без символов, кроме «a» и «b», включая пустую строку: {ε, «a», «b», «aa», «ab», «ba», «bb» , "ааа", ...}
ab*(c|ε) обозначает набор строк, начинающихся с «a», затем ноль или более «b» и, наконец, необязательно «c»: {«a», «ac», «ab», «abc», «abb», «abbc ", ...}
(0|(1(01*0)*1))* обозначает набор двоичных чисел, кратных 3: { ε, «0», «00», «11», «000», «011», «110», «0000», «0011», «0110» , "1001", "1100", "1111", "00000", ... }

Выразительная мощь и компактность

Формальное определение регулярных выражений намеренно сведено к минимуму и избегает определения ?и +— они могут быть выражены следующим образом: a+= aa*и a?= (a|ε). Иногда дополнение оператор добавлен, чтобы дать обобщенную регулярное выражение ; здесь R ^c соответствует всем строкам над Σ*, которые не соответствуют R . В принципе, оператор дополнения является избыточным, потому что он не дает большей выразительной силы. Однако это может сделать регулярное выражение гораздо более кратким — исключение одного оператора дополнения может привести к двойному экспоненциальному увеличению его длины. ^[22]^[23]^[24]

Регулярные выражения в этом смысле могут выражать регулярные языки, а именно класс языков, принятых детерминированными конечными автоматами . Однако есть существенная разница в компактности. Некоторые классы регулярных языков могут быть описаны только детерминированными конечными автоматами, размер которых экспоненциально растет по мере увеличения размера кратчайших эквивалентных регулярных выражений. Стандартным примером здесь являются языки Lk , состоящие из всех строк в алфавите { a , b }, где _k^{- я} буква, начиная с последней , равна a . С одной стороны, регулярное выражение, описывающее L ₄ , имеет вид . ${\ Displaystyle (а \ середина б) ^ {*} а (а \ середина б) (а \ середина б) (а \ середина б)}$

Обобщение этого шаблона на L _k дает выражение: ${\ displaystyle (a \ mid b) ^ {*} a \ underbrace {(a \ mid b) (a \ mid b) \ cdots (a \ mid b)} _ {k-1 {\ text {times}} }.\,}$

С другой стороны, известно, что каждый детерминированный конечный автомат, принимающий язык Lk , должен иметь не менее _2k^{состояний} . К счастью, существует простое преобразование регулярных выражений в более общие недетерминированные конечные автоматы (НКА), которое не приводит к такому увеличению размера; по этой причине NFA часто используются как альтернативные представления обычных языков. НКА представляют собой простую вариацию грамматик типа 3 иерархии Хомского . ^[20]

С другой стороны, есть много языков, которые легко описываются с помощью DFA, но не описываются с помощью регулярных выражений. Например, определение достоверности данного ISBN требует вычисления модуля целочисленной базы 11 и может быть легко реализовано с помощью DFA с 11 состояниями. Однако регулярное выражение для решения той же проблемы делимости на 11 имеет длину не менее нескольких мегабайт. ^{[ нужна ссылка ]}

По заданному регулярному выражению алгоритм построения Томпсона вычисляет эквивалентный недетерминированный конечный автомат. Преобразование в обратном направлении достигается алгоритмом Клини .

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

Определение эквивалентности регулярных выражений

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

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

Алгебраические законы для регулярных выражений можно получить с помощью метода Гишера, который лучше всего объясняется на примере: Чтобы проверить, обозначают ли ( X + Y ) ^* и ( X ^* Y ^* ) ^* один и тот же регулярный язык для всех регулярных выражений X , Y , необходимо и достаточно проверить, обозначают ли конкретные регулярные выражения ( a + b ) ^* и ( a ^* b ^* ) ^* один и тот же язык над алфавитом Σ={ a , b}. В более общем смысле уравнение E = F между членами регулярного выражения с переменными выполняется тогда и только тогда, когда выполняется его конкретизация с другими переменными, замененными разными символьными константами. ^[25]^[26]

Каждое регулярное выражение может быть записано исключительно в терминах звезд Клини и объединений множеств . Это удивительно сложная проблема. Какими бы простыми ни были регулярные выражения, нет способа систематически переписать их в какую-либо нормальную форму. Отсутствие аксиомы в прошлом приводило к проблеме высоты звезды . В 1991 году Декстер Козен аксиоматизировал регулярные выражения как алгебру Клини , используя аксиомы уравнения и предложения Хорна . ^[27] Уже в 1964 г. Редько доказал, что никакой конечный набор чисто эквациональных аксиом не может характеризовать алгебру регулярных языков. ^[28]

Синтаксис

Шаблон регулярного выражения соответствует целевой строке . Узор состоит из последовательности атомов . Атом — это отдельная точка в шаблоне регулярного выражения, которую он пытается сопоставить с целевой строкой. Самый простой атом — это литерал, но для группировки частей шаблона в соответствии с атомом потребуется использовать его ( )в качестве метасимволов. Метасимволы помогают формировать: атомы ; квантификаторы , сообщающие, сколько атомов (и является ли он жадным квантификатором )или нет); логический символ ИЛИ, который предлагает набор альтернатив, и логический символ НЕ, отрицающий существование атома; и обратные ссылки для ссылки на предыдущие атомы завершающего набора атомов. Сопоставление выполняется не тогда, когда совпадают все атомы строки, а когда совпадают все атомы шаблона в регулярном выражении. Идея состоит в том, чтобы небольшой шаблон символов обозначал большое количество возможных строк, а не составлял большой список всех буквальных возможностей.

В зависимости от процессора регулярных выражений существует около четырнадцати метасимволов, символов, которые могут иметь или не иметь своего буквального значения, в зависимости от контекста, или от того, являются ли они «экранированными», т.е. им предшествует управляющая последовательность , в данном случае обратная косая черта \. Современные и расширенные регулярные выражения POSIX используют метасимволы чаще, чем их буквальное значение, поэтому, чтобы избежать «обратной косой черты» или синдрома наклона зубочистки , имеет смысл использовать переход метасимвола в буквальный режим; но для начала имеет смысл иметь четыре метасимвола в квадратных скобках ( )и { }быть в основном буквальным, а также «избегать» этого обычного значения, чтобы стать метасимволами. Общие стандарты реализуют оба.Обычные метасимволы {}[]()^$.|*+?и\. Обычные символы, которые становятся метасимволами при экранировании, это dswDSWи N.

Разделители

При вводе регулярного выражения на языке программирования они могут быть представлены как обычный строковый литерал, поэтому обычно заключаются в кавычки; это распространено, например, в C, Java и Python, где регулярное выражение reвводится как "re". Однако они часто пишутся с косой чертой в качестве разделителей , как в /re/регулярном выражении re. Это берет свое начало в ed , где /находится команда редактора для поиска, и выражение /re/может использоваться для указания диапазона строк (соответствующих шаблону), которые можно комбинировать с другими командами с любой стороны, наиболее известными g/re/pкак в grep ("global regex print"), который включен в большинство операционных систем на основе Unix , таких как Linuxдистрибутивы. Аналогичное соглашение используется в sed , где поиск и замена задаются , s/re/replacement/а шаблоны могут быть объединены запятой для указания диапазона строк, как в /re1/,/re2/. Эта нотация особенно хорошо известна из-за ее использования в Perl , где она является частью синтаксиса, отличного от обычных строковых литералов. В некоторых случаях, таких как sed и Perl, можно использовать альтернативные разделители, чтобы избежать конфликта с содержимым и избежать появления символа-разделителя в содержимом. Например, в sed команда s,/,X,заменит a /на X, используя запятые в качестве разделителей.

Стандарты

Стандарт IEEE POSIX имеет три типа соответствия: BRE (базовые регулярные выражения), ^[29] ERE (расширенные регулярные выражения) и SRE (простые регулярные выражения). SRE устарел [ ^30] в пользу BRE, так как оба обеспечивают обратную совместимость . Подраздел ниже, охватывающий классы символов, относится как к BRE, так и к ERE.

BRE и ERE работают вместе. ERE добавляет ?, +и |, и устраняет необходимость экранировать метасимволы ( )и { }, которые требуются в BRE. Кроме того, пока соблюдается стандартный синтаксис POSIX для регулярных выражений, может существовать и часто используется дополнительный синтаксис для обслуживания конкретных (но совместимых с POSIX) приложений. Хотя POSIX.2 оставляет некоторые особенности реализации неопределенными, BRE и ERE предоставляют «стандарт», который с тех пор был принят в качестве синтаксиса по умолчанию для многих инструментов, где обычно поддерживается выбор режимов BRE или ERE. Например, GNU grep имеет следующие параметры: " grep -E" для ERE и " grep -G" для BRE (по умолчанию) и " grep -P" для регулярных выражений Perl .

Регулярные выражения Perl стали стандартом де-факто, имея богатый и мощный набор атомарных выражений. В Perl нет «базового» или «расширенного» уровней. Как и в POSIX ERE, ( )и { }рассматриваются как метасимволы, если они не экранированы; известно, что другие метасимволы являются буквальными или символическими, основываясь только на контексте. Дополнительные функции включают ленивое сопоставление , обратные ссылки , именованные группы захвата и рекурсивные шаблоны.

POSIX базовый и расширенный

В стандарте POSIX базовый регулярный синтаксис ( BRE ) требует, чтобы метасимволы ( ) и { }были обозначены и \{\}, тогда как расширенный регулярный синтаксис ( ERE ) этого не требует.

Метасимвол	Описание
`^`	Соответствует начальной позиции в строке. В линейных инструментах он соответствует начальной позиции любой линии.
`.`	Соответствует любому одиночному символу (многие приложения исключают символы новой строки , и именно то, какие символы считаются новыми строками, зависит от вкуса, кодировки символов и платформы, но можно с уверенностью предположить, что символ перевода строки включен). В выражениях скобок POSIX символ точки соответствует буквальной точке. Например, `a.c`соответствует «abc» и т. д., но `[a.c]`соответствует только «a», «.» или «c».
`[ ]`	Скобочное выражение. Соответствует одному символу, заключенному в скобки. Например, `[abc]`соответствует "a", "b" или "c". `[a-z]`определяет диапазон, который соответствует любой строчной букве от «a» до «z». Эти формы могут быть смешаны: `[abcx-z]`соответствует «a», «b», «c», «x», «y» или «z», как и `[a-cx-z]`. Символ `-`рассматривается как буквальный символ, если он является последним или первым (после `^`символа , если он присутствует) символом в скобках: `[abc-]`, `[-abc]`. Обратите внимание, что символы обратной косой черты не допускаются. Символ `]`может быть включен в выражение в квадратных скобках, если он является первым (после `^`) символом: `[]abc]`.
`[^ ]`	Соответствует одному символу, который не содержится в квадратных скобках. Например, `[^abc]`соответствует любому символу, кроме "a", "b" или "c". `[^a-z]`соответствует любому одиночному символу, который не является строчной буквой от «a» до «z». Точно так же можно смешивать буквенные символы и диапазоны.
`$`	Соответствует конечной позиции строки или позиции непосредственно перед символом новой строки в конце строки. В линейных инструментах он соответствует конечной позиции любой строки.
`( )`	Определяет отмеченное подвыражение. Строка, совпавшая в скобках, может быть вызвана позже (см. следующую запись, ). Отмеченное подвыражение также называется блоком или группой захвата. Для режима BRE требуется .`\n```
`\n`	Соответствует тому, чему соответствует n -е помеченное подвыражение, где n — цифра от 1 до 9. Эта конструкция нечетко определена в стандарте POSIX.2. Некоторые инструменты позволяют ссылаться более чем на девять групп захвата. Также известен как обратная ссылка. обратные ссылки поддерживаются только в режиме BRE
`*`	Соответствует предыдущему элементу ноль или более раз. Например, `abc`соответствует «ac», «abc», «abbbc» и т. д. `[xyz]`соответствует «», «x», «y», «z», «zx», «zyx», «xyzzy» и т. д. `(ab)*`соответствует "", "ab", "abab", "ababab" и так далее.
`{m,n}`	Соответствует предыдущему элементу не менее m и не более n раз. Например, `a{3,5}`соответствует только «ааа», «аааа» и «ааааа». Этого нет в нескольких старых экземплярах регулярных выражений. Для режима BRE требуется`\{m,n\}` .

Примеры:

.at соответствует любой строке из трех символов, оканчивающейся на «at», включая «шляпу», «кошку» и «летучую мышь».
[hc]at соответствует «шляпе» и «кошке».
[^b]atсоответствует всем строкам, .atза исключением "bat".
[^hc]atсоответствует всем строкам, совпадающим с .atдругими, кроме "шляпа" и "кошка".
^[hc]at соответствует "шляпе" и "кошке", но только в начале строки или строки.
[hc]at$ соответствует "шляпе" и "кошке", но только в конце строки или строки.
\[.\] соответствует любому одиночному символу, окруженному "[" и "]", поскольку скобки экранированы, например: "[a]" и "[b]".
s.* соответствует s, за которым следует ноль или более символов, например: "s" и "saw" и "seed".

POSIX расширенный

Значение метасимволов , экранированных обратной косой чертой, для некоторых символов в синтаксисе расширенных регулярных выражений POSIX ( ERE ) меняется на обратное. В этом синтаксисе обратная косая черта заставляет метасимвол рассматриваться как буквальный символ. Так, например, сейчас ( )и \{ \}сейчас { }. Кроме того, удалена поддержка обратных ссылок и добавлены следующие метасимволы:\n

Метасимвол	Описание
`?`	Соответствует предыдущему элементу ноль или один раз. Например, `ab?c`соответствует только "ac" или "abc".
`+`	Соответствует предыдущему элементу один или несколько раз. Например, `ab+c`соответствует «abc», «abbc», «abbbc» и т. д., но не «ac».
`\|`	Оператор выбора (также известный как чередование или объединение множеств) соответствует либо выражению до, либо выражению после оператора. Например, `abc\|def`соответствует "abc" или "def".

Примеры:

[hc]?at соответствует «at», «шляпе» и «кошке».
[hc]*at соответствует "at", "hat", "cat", "hhat", "chat", "hcat", "cchchat" и так далее.
[hc]+at соответствует «шляпе», «коту», «чхат», «чату», «чкоту», «чччату» и т. д., но не «ат».
cat|dog соответствует «кошке» или «собаке».

Расширенные регулярные выражения POSIX часто можно использовать с современными утилитами Unix, включив флаг командной строки -E .

Классы персонажей

Класс символов — это самая основная концепция регулярных выражений после буквального совпадения. Он заставляет одну небольшую последовательность символов соответствовать большому набору символов. Например, может обозначать любую заглавную букву английского алфавита и может означать любую цифру. Классы символов применяются к обоим уровням POSIX.[A-Z]\d

При указании диапазона символов, например (т. е. от строчных до прописных ), настройки локали компьютера определяют содержимое в соответствии с числовым порядком кодировки символов. Они могут хранить цифры в этой последовательности или в таком порядке: abc…zABC…Z или aAbBcC…zZ . Таким образом, стандарт POSIX определяет класс символов, который будет известен установленному процессору регулярных выражений. Эти определения приведены в следующей таблице:[a-Z]aZ

Описание	POSIX	Нестандартный	Perl/Tcl	Вим	Ява	ASCII
ASCII-символы		`[:ascii:]`^[31]			`\p{ASCII}`	`[\x00-\x7F]`
Буквенно-цифровые символы	`[:alnum:]`				`\p{Alnum}`	`[A-Za-z0-9]`
Буквенно-цифровые символы плюс "_"		`[:word:]`^[31]	`\w`	`\w`	`\w`	`[A-Za-z0-9_]`
Символы, не являющиеся словами			`\W`	`\W`	`\W`	`[^A-Za-z0-9_]`
Алфавитные символы	`[:alpha:]`			`\a`	`\p{Alpha}`	`[A-Za-z]`
Пробел и вкладка	`[:blank:]`			`\s`	`\p{Blank}`	`[ \t]`
Границы слов			`\b`	`\< \>`	`\b`	`(?<=\W)(?=\w)\|(?<=\w)(?=\W)`
Границы без слов					`\B`	`(?<=\W)(?=\W)\|(?<=\w)(?=\w)`
Управляющие символы	`[:cntrl:]`				`\p{Cntrl}`	`[\x00-\x1F\x7F]`
Цифры	`[:digit:]`		`\d`	`\d`	`\p{Digit}` или `\d`	`[0-9]`
Нецифры			`\D`	`\D`	`\D`	`[^0-9]`
Видимые символы	`[:graph:]`				`\p{Graph}`	`[\x21-\x7E]`
Строчные буквы	`[:lower:]`			`\l`	`\p{Lower}`	`[a-z]`
Видимые символы и символ пробела	`[:print:]`			`\p`	`\p{Print}`	`[\x20-\x7E]`
Знаки препинания	`[:punct:]`				`\p{Punct}`	[][!"#$%&'()*+,./:;<=>?@\^_`{\|}~-]
Пробелы	`[:space:]`		`\s`	`\_s`	`\p{Space}` или `\s`	`[ \t\r\n\v\f]`
Символы без пробелов			`\S`	`\S`	`\S`	`[^ \t\r\n\v\f]`
Заглавные буквы	`[:upper:]`			`\u`	`\p{Upper}`	`[A-Z]`
Шестнадцатеричные цифры	`[:xdigit:]`			`\x`	`\p{XDigit}`	`[A-Fa-f0-9]`

Классы символов POSIX могут использоваться только в выражениях со скобками. Например, соответствует прописным буквам и строчным буквам «а» и «б».[[:upper:]ab]

Дополнительным классом, не относящимся к POSIX, который понимают некоторые инструменты, является , который обычно определяется как плюс подчеркивание. Это отражает тот факт, что во многих языках программирования именно эти символы могут использоваться в идентификаторах. Редактор Vim дополнительно различает классы слов и заголовков слов (используя обозначения и ), поскольку во многих языках программирования символы, которые могут начинать идентификатор, не совпадают с теми, которые могут встречаться в других позициях: числа обычно исключаются, поэтому идентификатор будет выглядеть как или в нотации POSIX.[:word:][:alnum:]\w\h\h\w*[[:alpha:]_][[:alnum:]_]*

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

Perl и PCRE

Из-за своей выразительной силы и (относительной) простоты чтения многие другие утилиты и языки программирования приняли синтаксис, аналогичный Perl — например, Java , JavaScript , Julia , Python , Ruby , Qt , Microsoft .NET Framework и XML . Схема . Некоторые языки и инструменты, такие как Boost и PHPподдержка нескольких разновидностей регулярных выражений. Реализации регулярных выражений, производные от Perl, не идентичны и обычно реализуют подмножество функций Perl 5.0, выпущенного в 1994 году. Perl иногда включает функции, первоначально обнаруженные в других языках. Например, Perl 5.10 реализует синтаксические расширения, первоначально разработанные в PCRE и Python. ^[32]

Ленивое сопоставление

В Python и некоторых других реализациях (например, Java) три общих квантификатора ( *, +и ?) по умолчанию являются жадными , поскольку они соответствуют как можно большему числу символов. ^[33] Регулярное выражение ".+"(включая двойные кавычки), примененное к строке

«Ганимед, — продолжил он, — самый большой спутник в Солнечной системе».

соответствует всей строке (поскольку вся строка начинается и заканчивается двойной кавычкой), а не соответствует только первой части, "Ganymede,". Однако вышеупомянутые квантификаторы можно сделать ленивыми , минимальными или неохотными , чтобы они соответствовали как можно меньшему количеству символов, добавив вопросительный знак: только ".+?"совпадения "Ganymede,". ^[33]

Тем не менее, в некоторых обстоятельствах все предложение может быть сопоставлено. Оператор вопросительного знака не меняет значения оператора точки, поэтому он по-прежнему может соответствовать двойным кавычкам во входных данных. Такой шаблон ".*?" EOFбудет по-прежнему соответствовать всему вводу, если это строка:

«Ганимед, — продолжил он, — самый большой спутник в Солнечной системе». EOF

Чтобы убедиться, что двойные кавычки не могут быть частью совпадения, точка должна быть заменена (например, "[^"]*"). Это будет соответствовать части текста в кавычках без дополнительных двойных кавычек. (Удалив возможность сопоставления фиксированного суффикса, т . е ". это также преобразовало ленивое сопоставление в жадное сопоставление, поэтому ?больше не требуется.) ^{[ нужна ссылка ]}

Притяжательное соответствие

В Java квантификаторы можно сделать притяжательными , добавив знак «плюс», который отключает откат (в механизме поиска с возвратом), даже если это позволит выполнить полное совпадение: ^[34] Хотя регулярное выражение ".*"применяется к строке

«Ганимед, — продолжил он, — самый большой спутник в Солнечной системе».

соответствует всей строке, регулярное выражение ".*+"вообще не соответствует , потому что .*+потребляет весь ввод, включая окончательный ". Таким образом, притяжательные квантификаторы наиболее полезны с классами символов с отрицанием, например "[^"]*+", которые совпадают "Ganymede,"при применении к одной и той же строке.

Другим распространенным расширением, выполняющим ту же функцию, является атомарная группировка, которая отключает поиск с возвратом для группы в скобках. Типичный синтаксис (?>group) . Например, в то время как ^(wi|w)i$ соответствует и wi , и wii , ^(?>wi|w)i$ соответствует только wii , потому что движку запрещено возвращаться, и попробуйте установить группу как «w». ^[35]

Притяжательные квантификаторы легче реализовать, чем жадные и ленивые квантификаторы, и обычно они более эффективны во время выполнения. ^[34]

Шаблоны для нерегулярных языков

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

Язык квадратов не является ни регулярным, ни контекстно-свободным из-за леммы о накачке . Однако сопоставление с образцом с неограниченным числом обратных ссылок, поддерживаемое многочисленными современными инструментами, по-прежнему зависит от контекста . ^[36] Общая проблема сопоставления любого количества обратных ссылок является NP-полной , экспоненциально растущей по количеству используемых групп обратных ссылок. ^[37]

Однако многие инструменты, библиотеки и движки, предоставляющие такие конструкции, по-прежнему используют для своих шаблонов термин регулярное выражение . Это привело к номенклатуре, в которой термин «регулярное выражение» имеет разные значения в формальной теории языка и сопоставлении с образцом. По этой причине некоторые люди стали использовать термин регулярное выражение , регулярное выражение или просто шаблон для описания последнего. Ларри Уолл , автор языка программирования Perl, пишет в эссе о дизайне Raku :

«Регулярные выражения» […] лишь незначительно связаны с реальными регулярными выражениями. Тем не менее, этот термин расширился благодаря возможностям наших механизмов сопоставления с образцом, поэтому я не собираюсь здесь бороться с лингвистической необходимостью. Однако обычно я буду называть их "регулярными выражениями" (или "регулярными выражениями", когда я в англо-саксонском настроении). ^[16]

Утверждение	Смотреть за	Смотреть вперед
Положительный	(? <= шаблон )	(? = шаблон )
Отрицательный	(? <! образец )	(? ! образец )
Утверждения просмотра назад и вперед в регулярных выражениях Perl

Другие функции, отсутствующие в описании обычных языков, включают утверждения. К ним относятся вездесущие ^ и $ , а также некоторые более сложные расширения, такие как lookaround. Они определяют окружение совпадения и не распространяются на само совпадение — функция, имеющая отношение только к варианту использования поиска строки. Некоторые из них можно смоделировать на обычном языке, рассматривая окружение также как часть языка. ^[38]

Реализации и время работы

Существует как минимум три разных алгоритма , которые определяют, соответствует ли заданное регулярное выражение строке и каким образом.

Самый старый и самый быстрый основан на результате теории формального языка, который позволяет преобразовать любой недетерминированный конечный автомат (НКА) в детерминированный конечный автомат (ДКА). DFA можно построить явно, а затем запускать результирующую входную строку по одному символу за раз. Построение DFA для регулярного выражения размера m требует затрат времени и памяти O (2 ^m ), но его можно запустить на строке размера n за время O ( n ). Обратите внимание, что размер выражения равен размеру после расширения аббревиатур, таких как числовые квантификаторы.

Альтернативный подход состоит в том, чтобы моделировать NFA напрямую, по существу, создавая каждое состояние DFA по запросу, а затем отбрасывая его на следующем шаге. Это сохраняет неявный DFA и позволяет избежать экспоненциальной стоимости строительства, но эксплуатационные расходы возрастают до O ( mn ). Явный подход называется алгоритмом DFA, а неявный подход — алгоритмом NFA. Добавление кэширования к алгоритму NFA часто называют алгоритмом «ленивого DFA» или просто алгоритмом DFA без каких-либо различий. Эти алгоритмы работают быстро, но использовать их для вызова сгруппированных подвыражений, ленивой квантификации и подобных функций сложно. ^[39]^[40] Современные реализации включают семейство re1-re2-sregex, основанное на коде Кокса.

Третий алгоритм заключается в сопоставлении шаблона с входной строкой путем поиска с возвратом . Этот алгоритм обычно называют NFA, но эта терминология может сбивать с толку. Его время выполнения может быть экспоненциальным, что демонстрируют простые реализации при сопоставлении с выражениями, подобными этому, которые содержат как чередование, так и неограниченную количественную оценку, и заставляют алгоритм рассматривать экспоненциально растущее количество подслучаев. Такое поведение может вызвать проблему безопасности, называемую отказом в обслуживании с помощью регулярных выражений (ReDoS).(a|aa)*b

Хотя реализации с возвратом дают экспоненциальную гарантию только в худшем случае, они обеспечивают гораздо большую гибкость и выразительную мощь. Например, любая реализация, позволяющая использовать обратные ссылки или реализующая различные расширения, представленные в Perl, должна включать какой-либо вид поиска с возвратом. Некоторые реализации пытаются обеспечить лучшее из обоих алгоритмов, сначала запуская быстрый алгоритм DFA, и возвращаются к потенциально более медленному алгоритму поиска с возвратом только тогда, когда во время сопоставления встречается обратная ссылка. GNU grep (и базовый gnulib DFA) использует такую стратегию. ^[41]

Сублинейные алгоритмы времени выполнения были реализованы с использованием алгоритмов на основе Бойера-Мура (BM) и связанных с ними методов оптимизации DFA, таких как обратное сканирование. ^[42] GNU grep, который поддерживает широкий спектр синтаксисов и расширений POSIX, использует BM для предварительной фильтрации первого прохода, а затем использует неявный DFA. Wu agrep , который реализует приближенное сопоставление, объединяет предварительную фильтрацию с DFA в BDM (обратное сопоставление DAWG). BNDM от NR-grep расширяет технику BDM за счет побитового параллелизма Shift-Or. ^[43]

Существует несколько теоретических альтернатив обратному отслеживанию для обратных ссылок, и их «экспоненты» более ручные в том смысле, что они связаны только с количеством обратных ссылок, фиксированным свойством некоторых языков регулярных выражений, таких как POSIX. Один наивный метод, который дублирует NFA без возврата для каждой обратной ссылки, имеет сложность времени и пространства для стога сена длиной n и k обратных ссылок в RegExp. ^[44] Очень недавняя теоретическая работа, основанная на автоматах памяти, дает более жесткую границу на основе используемых «активных» узлов переменных и полиномиальную возможность для некоторых регулярных выражений с обратными ссылками. ^[45] ${\ Displaystyle {\ mathrm {O}} (п ^ {2k + 2})}$ ${\ Displaystyle {\ mathrm {O}} (п ^ {2k + 1})}$

Юникод

Теоретически любой набор токенов может быть сопоставлен с регулярными выражениями, если он заранее определен. С точки зрения исторических реализаций, регулярные выражения изначально были написаны для использования символов ASCII в качестве набора токенов, хотя библиотеки регулярных выражений поддерживали множество других наборов символов . Многие современные механизмы регулярных выражений предлагают по крайней мере некоторую поддержку Unicode . В большинстве случаев не имеет значения, какой набор символов, но некоторые проблемы возникают при расширении регулярных выражений для поддержки Unicode.

Поддерживаемая кодировка . Некоторые библиотеки регулярных выражений предполагают работу с определенной кодировкой, а не с абстрактными символами Unicode. Многие из них требуют кодировки UTF-8 , в то время как другие могут ожидать кодировку UTF-16 или UTF-32 . Напротив, Perl и Java не зависят от кодировок, вместо этого внутренне оперируя декодированными символами.
Поддерживаемый диапазон Юникода . Многие движки регулярных выражений поддерживают только Basic Multilingual Plane , то есть символы, которые можно закодировать всего 16 битами. В настоящее время (по состоянию на 2016 год) только несколько движков регулярных выражений (например, Perl и Java) могут обрабатывать весь 21-битный диапазон Unicode.
Расширение конструкций, ориентированных на ASCII, на Unicode . Например, в реализациях на основе ASCII диапазоны символов формы [x-y]допустимы везде, где x и y имеют кодовые точки в диапазоне [0x00,0x7F] и кодовая точка ( x ) ≤ кодовая точка ( y ). Естественное расширение таких диапазонов символов до Unicode просто изменило бы требование, чтобы конечные точки находились в [0x00,0x7F], на требование, чтобы они находились в [0x0000,0x10FFFF]. Однако на практике это часто не так. Некоторые реализации, такие как gawk, не позволяйте диапазонам символов пересекать блоки Unicode. Диапазон, подобный [0x61,0x7F], является допустимым, поскольку обе конечные точки попадают в блок Basic Latin, как и [0x0530,0x0560], поскольку обе конечные точки попадают в армянский блок, но диапазон, подобный [0x0061,0x0532], недействителен, поскольку он включает несколько блоков Unicode. Другие движки, такие как редактор Vim , допускают пересечение блоков, но значения символов не должны отличаться друг от друга более чем на 256 символов. ^[46]
Нечувствительность к регистру . Некоторые флаги нечувствительности к регистру влияют только на символы ASCII. Другие флаги влияют на всех персонажей. Некоторые движки имеют два разных флага, один для ASCII, другой для Unicode. То, какие именно символы принадлежат классам POSIX, также различается.
Родственники регистронезависимости . Поскольку ASCII различает регистр, нечувствительность к регистру стала логической особенностью текстового поиска. Юникод представил алфавитные шрифты без регистра, такие как Деванагари . Для них чувствительность к регистру не применяется. Для таких письменностей, как китайский, кажется логичным другое различие: между традиционным и упрощенным. В арабских шрифтах может быть желательна нечувствительность к начальному, среднему, конечному и изолированному положению . В японском иногда полезна нечувствительность между хираганой и катаканой .
Нормализация . Юникод имеет комбинированные символы. Как и в старых пишущих машинках, за простыми базовыми символами (пробелы, знаки препинания, символы, цифры или буквы) может следовать один или несколько символов без пробелов (обычно диакритические знаки, например, знаки ударения, изменяющие буквы), чтобы сформировать один печатный символ; но Unicode также предоставляет ограниченный набор предварительно составленных символов, т. е. символов, которые уже включают один или несколько комбинируемых символов. Последовательность базового символа + комбинированных символов должна сопоставляться с идентичным одиночным предварительно составленным символом (только некоторые из этих комбинированных последовательностей могут быть предварительно скомпонованы в один символ Unicode, но бесконечно много других комбинированных последовательностей возможны в Unicode и необходимы для различных языков. , используя один или несколько комбинированных символов после начального основного символа; эти комбинированные последовательности могутвключают базовый символ или комбинацию символов, частично предварительно составленных, но не обязательно в каноническом порядке и не обязательно с использованием канонических прекомпозиций). Процесс стандартизации последовательностей базового символа + объединения символов путем разложения этих канонически эквивалентных последовательностей перед их переупорядочением в каноническом порядке (и, при необходимости, перекомпоновкой некоторых комбинирующих символов в начальный базовый символ) называется нормализацией.
Новые коды управления . Unicode представил среди прочего метки порядка байтов и маркеры направления текста. С этими кодами, возможно, придется обращаться особым образом.
Введение классов символов для блоков Unicode, скриптов и многих других свойств символов . Свойства блока гораздо менее полезны, чем свойства скрипта, потому что блок может иметь кодовые точки из нескольких разных скриптов, а скрипт может иметь кодовые точки из нескольких разных блоков. ^[47] В Perl и java.util.regexбиблиотеке свойства формы \p{InX}или \p{Block=X}соответствуют символам в блоке X и \P{InX}/или \P{Block=X}соответствуют кодовым точкам, не входящим в этот блок. Точно так же , \p{Armenian}, \p{IsArmenian}или \p{Script=Armenian}соответствует любому символу армянского письма. Как правило, \p{X}соответствует любому символу либо с бинарным свойством X , либо с общей категорией X.. Например, \p{Lu}, \p{Uppercase_Letter}или \p{GC=Lu}соответствует любой заглавной букве. К бинарным свойствам, не являющимся общими категориями, относятся \p{White_Space}, \p{Alphabetic}, \p{Math}и \p{Dash}. Примерами небинарных свойств являются \p{Bidi_Class=Right_to_Left}, \p{Word_Break=A_Letter}и \p{Numeric_Value=10}.

Использование

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

Хотя регулярные выражения были бы полезны в поисковых системах Интернета , их обработка во всей базе данных может потреблять чрезмерные компьютерные ресурсы в зависимости от сложности и структуры регулярного выражения. Хотя во многих случаях системные администраторы могут выполнять внутренние запросы на основе регулярных выражений, большинство поисковых систем не предлагают общедоступную поддержку регулярных выражений. Заметными исключениями являются Google Code Search и Exalead . Однако в январе 2012 года Google Code Search был закрыт. ^[48]

Примеры

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

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

В примерах используются следующие соглашения. ^[49]

метасимвол(ы) ;; столбец метасимволов указывает демонстрируемый синтаксис регулярного выражения
=~ м// ;; указывает на операцию сопоставления с регулярным выражением в Perl
=~ с/// ;; указывает на операцию замены регулярных выражений в Perl

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

Если не указано иное, следующие примеры соответствуют языку программирования Perl версии 5.8.8 от 31 января 2006 г. Это означает, что другие реализации могут не поддерживать некоторые части показанного здесь синтаксиса (например, базовое или расширенное регулярное выражение, а также расширенное регулярное выражение). (), или отсутствие \dвместо POSIX [:digit:] ).

Синтаксис и соглашения, используемые в этих примерах, также совпадают с таковыми в других средах программирования. ^[50]

Метасимвол(ы)	Описание	Пример ^[51]
`.`	Обычно соответствует любому символу, кроме новой строки. В квадратных скобках точка буквальная.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/...../ ) { print "$string1 имеет длину >= 5.\n" ; } Вывод: Привет мир имеет длину >= 5.
`( )`	Группирует ряд элементов шаблона в один элемент. Когда вы сопоставляете шаблон в круглых скобках, вы можете использовать любой из `$1`, `$2`, ... позже, чтобы сослаться на ранее сопоставленный шаблон. В некоторых реализациях вместо этого может использоваться обратная косая черта, например `\1`, `\2`.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/(H..).(o..)/ ) { print "Мы сопоставили '$1' и '$2'.\n" ; } Вывод: Мы сопоставили «Hel» и «o W».
`+`	Соответствует предыдущему элементу шаблона один или несколько раз.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/l+/ ) { print "В $string1 есть одна или несколько последовательных букв \"l\".\n" ; } Вывод: В Hello World есть одна или несколько последовательных букв «l».
`?`	Соответствует предыдущему элементу шаблона ноль или один раз.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/H.?e/ ) { print "Имеются 'H' и 'e', разделенные знаком " ; print "0-1 символов (например, He Hue Hee).\n" ; } Вывод: Буквы «H» и «e» разделены символами 0–1 (например, He Hue Hee).
`?`	Изменяет предыдущее регулярное выражение `*`, или 'd `+`, чтобы оно совпадало как можно меньше раз.`?{M,N}`	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/(l.+?o)/ ) { print "Нежадное совпадение с 'l', за которым следует единица или " ; print "больше символов 'llo', а не 'llo Wo'.\n" ; } Вывод: Нежадное совпадение с «l», за которым следует один или несколько символов, — это «llo», а не «llo Wo».
`*`	Соответствует предыдущему элементу шаблона ноль или более раз.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/elo/ ) { print "Имеется буква 'e', за которой следует нуль до многих" ; print "'l' с последующим 'o' (например, eo, elo, ello, elllo).\n" ; } Вывод:* Существует буква «е», за которой следует ноль, или множество букв «l», за которыми следует «o» (например, eo, elo, ello, elllo).
`{M,N}`	Обозначает минимальное M и максимальное количество совпадений N. N может быть опущен, а M может быть равен 0: `{M}`соответствует «ровно» M раз; `{M,}`соответствует "по крайней мере" M раз; `{0,N}`соответствует «не более» N раз. `x* y+ z?`таким образом эквивалентен `x{0,} y{1,} z{0,1}`.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/l{1,2}/ ) { print "Существует подстрока, содержащая хотя бы 1" ; print "и не более 2 л в $string1\n" ; } Вывод: Существует подстрока, содержащая не менее 1 и не более 2 l в Hello World.
`[…]`	Обозначает набор возможных совпадений символов.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/[aeiou]+/ ) { print "$string1 содержит одну или несколько гласных.\n" ; } Вывод: Привет мир содержит одну или несколько гласных.
`\|`	Разделяет альтернативные возможности.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/(Hello\|Hi\|Pogo)/ ) { print "$string1 содержит хотя бы одно из слов Hello, Hi или Pogo." ; } Вывод: Привет мир содержит по крайней мере один из слов Hello, Hi или Pogo.
`\b`	Соответствует границе нулевой ширины между символом класса слова (см. далее) и либо символом класса слова, либо ребром; такой же как `(^\w\|\w$\|\W\w\|\w\W)`.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/llo\b/ ) { print "Есть слово, оканчивающееся на 'llo'.\n" ; } Вывод: Есть слово, оканчивающееся на «лло».
`\w`	Соответствует буквенно-цифровому символу, включая "_"; так же, как `[A-Za-z0-9_]`в ASCII, и `[\p{Alphabetic}\p{GC=Mark}\p{GC=Decimal_Number}\p{GC=Connector_Punctuation}]` в Unicode, ^[47] где `Alphabetic`свойство содержит больше латинских букв, а `Decimal_Number`свойство содержит больше арабских цифр.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/\w/ ) { print "Есть хотя бы одна буквенно-цифровая" ; print "символ в $string1 (AZ, az, 0-9, _).\n" ; } Вывод: В Hello World есть хотя бы один буквенно-цифровой символ. (AZ, az, 0-9, _).
`\W`	Соответствует небуквенно -цифровому символу, кроме "_"; так же, как `[^A-Za-z0-9_]`в ASCII, и `[^\p{Alphabetic}\p{GC=Mark}\p{GC=Decimal_Number}\p{GC=Connector_Punctuation}]` в Юникоде.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/\W/ ) { print "Пробел между Hello и " ; print "Мир не буквенно-цифровой.\n" ; } Вывод: Пробел между Hello и World не является буквенно-цифровым.
`\s`	Соответствует символу пробела, которым в ASCII являются табуляция, перевод строки, перевод страницы, возврат каретки и пробел; в Unicode также соответствует неразрывным пробелам, следующей строке и пробелам переменной ширины (среди прочего).	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/\s.\s/ ) { print "В $string1 есть ДВА символа пробела, которые могут" ; print "разделяться другими символами.\n" ; } Вывод:* В привет мир есть ДВА символа пробела, которые могут быть разделены другими символами.
`\S`	Соответствует чему угодно, кроме пробела.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/\S.\S/ ) { print "В $string1 есть ДВА непробельных символа, которые" ; print "может быть разделен другими символами.\n" ; } Вывод:* В привет мир есть ДВА непробельных символа, которые могут быть разделены другими символами.
`\d`	Соответствует цифре; то же, что и `[0-9]`в ASCII; в Unicode, то же, что `\p{Digit}`и `\p{GC=Decimal_Number}`свойство or, которое само по себе совпадает со `\p{Numeric_Type=Decimal}`свойством.	$string1 = "99 бутылок пива на стене." ; if ( $string1 =~ m/(\d+)/ ) { print "$1 — первое число в строке '$string1'\n" ; } Вывод: 99 — первое число в «99 бутылках пива на стене».
`\D`	Соответствует нецифре; так же, как `[^0-9]`в ASCII или `\P{Digit}`в Unicode.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/\D/ ) { print "В $string1 есть хотя бы один символ" ; напечатайте "это не цифра.\n" ; } Вывод: В Hello World есть хотя бы один персонаж это не цифра.
`^`	Соответствует началу строки или строки.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/^He/ ) { print "$string1 начинается с символов 'He'.\n" ; } Вывод: Привет мир начинается с символов «Он».
`$`	Соответствует концу строки или строки.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/rld$/ ) { print "$string1 — это строка или строка" ; print "оканчивается на 'rld'.\n" ; } Вывод: Привет мир это строка или строка, оканчивающаяся на 'rld'.
`\A`	Соответствует началу строки (но не внутренней строке).	$string1 = "Привет\nМир\n" ; if ( $string1 =~ m/\AH/ ) { print "$string1 является строкой" ; print "начинается с 'H'.\n" ; } Вывод: Привет Мир это строка, начинающаяся с «H».
`\z`	Соответствует концу строки (но не внутренней строке). ^[52]	$string1 = "Привет\nМир\n" ; if ( $string1 =~ m/d\n\z/ ) { print "$string1 является строкой" ; print "оканчивается на 'd\\n'.\n" ; } Вывод: Привет Мир это строка, оканчивающаяся на 'd\n'.
`[^…]`	Соответствует всем символам, кроме тех, которые заключены в скобки.	$string1 = "Привет, мир\n" ; if ( $string1 =~ m/[^abc]/ ) { print "$string1 содержит символ, отличный от " ; напечатать "a, b и c.\n" ; } Вывод: Привет мир содержит символ, отличный от a, b и c.

индукция

Регулярные выражения часто могут быть созданы («индуцированы» или «выучены») на основе набора строк-примеров. Это известно как индукция регулярных языков и является частью общей проблемы индукции грамматики в вычислительной теории обучения . Формально, имея примеры строк на регулярном языке и, возможно, также примеры строк не на этом регулярном языке, можно вывести грамматику для языка, т. е. регулярное выражение, которое генерирует этот язык. Не все регулярные языки можно индуцировать таким образом (см. идентификацию языка в пределе), но многие могут. Например, набор примеров {1, 10, 100} и отрицательный набор (контрпримеров) {11, 1001, 101, 0} можно использовать для создания регулярного выражения 1⋅0* (1, за которым следует ноль или более 0с).

Смотрите также

Сравнение движков регулярных выражений
Расширенная форма Бэкуса – Наура
Соответствующие подстановочные знаки
Грамматика регулярного дерева
Конструкция Томпсона - преобразует регулярное выражение в эквивалентный недетерминированный конечный автомат (NFA) .

Примечания

^ Гойвартс, Ян. «Учебник по регулярным выражениям - узнайте, как использовать регулярные выражения» . www.regular-expressions.info . Архивировано из оригинала 01.11.2016 . Проверено 31 октября 2016 г. .
^ Митков, Руслан (2003). Оксфордский справочник по вычислительной лингвистике . Издательство Оксфордского университета. п. 754. ISBN 978-0-19-927634-9. Архивировано из оригинала 28 февраля 2017 г. Проверено 25 июля 2016 г. .
↑ Лоусон, Марк В. (17 сентября 2003 г.). Конечные автоматы . КПР Пресс. стр. 98–100. ISBN 978-1-58488-255-8. Архивировано из оригинала 27 февраля 2017 года . Проверено 25 июля 2016 г.
^ Клини 1951 .
↑ Люн, Хинг (16 сентября 2010 г.). «Регулярные языки и конечные автоматы» (PDF) . Университет штата Нью-Мексико . Архивировано из оригинала (PDF) 5 декабря 2013 г .. Проверено 13 августа 2019 г. Концепция регулярных событий была введена Клини через определение регулярных выражений.
^ б Томпсон 1968 .
^ б Джонсон и соавт. 1968 .
^ Керниган, Брайан (2007-08-08). «Сопоставитель регулярных выражений» . Красивый код . О'Райли Медиа . стр. 1–2. ISBN 978-0-596-51004-6. Архивировано из оригинала 07.10.2020 . Проверено 15 мая 2013 г. .
^ Ричи, Деннис М. «Неполная история текстового редактора QED» . Архивировано из оригинала 21 февраля 1999 г. Проверено 9 октября 2013 г.
^ a b Aho & Ullman 1992 , 10.11 Библиографические примечания к главе 10, с. 589.
^ Aycock 2003 , 2. Методы компиляции JIT, 2.1 Genesis, p. 98.
^ Рэймонд, Эрик С. со ссылкой на Денниса Ричи (2003). «Файл жаргона 4.4.7: grep» . Архивировано из оригинала 05.06.2011 . Проверено 17 февраля 2009 г. .
^ «Новые возможности регулярных выражений в Tcl 8.1» . Архивировано из оригинала 07.10.2020 . Проверено 11 октября 2013 г. .
^ «Документация PostgreSQL 9.3.1: 9.7. Сопоставление с образцом» . Архивировано из оригинала 07.10.2020 . Проверено 12 октября 2013 г. .
↑ Уолл, Ларри и команда разработчиков Perl 5 (2006). "perlre: регулярные выражения Perl" . Архивировано из оригинала 31 декабря 2009 г .. Проверено 10 октября 2006 г. .
^ а б Стена (2002)
^ «GROVF | Ускорение аналитики больших данных» . grovf.com . Архивировано из оригинала 07.10.2020 . Проверено 22 октября 2019 г. .
Викискладе есть медиафайлы по теме CUDA . bkase.github.io . Архивировано из оригинала 07.10.2020 . Проверено 22 октября 2019 г. .
^ справочная страница a b c d grep (1)
^ а б Хопкрофт, Мотвани и Ульман (2000)
^ Сипсер (1998)
↑ Gelade & Neven (2008 , стр. 332, Thm.4.1)
^ Грубер и Хольцер (2008)
↑ Основываясь на Gelade & Neven (2008) , регулярное выражение длиной около 850, такое что его дополнение имеет длину около 2³² , можно найти в File:RegexComplementBlowup.png .
^ Джей Л. Гишер (1984). (Название неизвестно) (Технический отчет). Стэнфордский университет, кафедра Comp. наук
^ Джон Э. Хопкрофт; Раджив Мотвани и Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления . Река Аппер-Сэдл/Нью-Джерси: Эддисон Уэсли. ISBN 978-0-201-44124-6.Здесь: Разд.3.4.6, с.117-120. — Это свойство может не выполняться для расширенных регулярных выражений, даже если они описывают не более крупный класс, чем обычные языки; ср. стр.121.
^ Козен (1991) ^{[ нужна страница ]}
^ В. Н. Редько (1964). «Об определяющих соотношениях для алгебры регулярных событий» . Украинский математический журнал . 16 (1): 120–126. Архивировано из оригинала 29 марта 2018 г. Проверено 28 марта 2018 г. . (На русском)
^ ISO / IEC 9945-2: 1993 Информационные технологии - Интерфейс переносимой операционной системы (POSIX) - Часть 2: Оболочка и утилиты , последовательно пересматриваемый как ISO / IEC 9945-2: 2002 Информационные технологии - Интерфейс переносимой операционной системы (POSIX) - Часть 2: Системные интерфейсы , ISO/IEC 9945-2:2003, а в настоящее время ISO/IEC/IEEE 9945:2009 Информационные технологии – Базовые спецификации интерфейса переносимых операционных систем (POSIX®), выпуск 7
^ Единая спецификация Unix (версия 2)
^ a b "33.3.1.2 Классы символов - Руководство по Emacs lisp - Версия 25.1" . gnu.org . 2016. Архивировано из оригинала 07.10.2020 . Проверено 13 апреля 2017 г. .
^ «Документация по регулярным выражениям Perl» . perldoc.perl.org. Архивировано из оригинала 31 декабря 2009 года . Проверено 8 января 2012 г.
^ a b "Синтаксис регулярных выражений" . Документация Python 3.5.0 . Фонд программного обеспечения Python . Архивировано из оригинала 18 июля 2018 года . Проверено 10 октября 2015 г.
^ a b «Основные классы: регулярные выражения: квантификаторы: различия между жадными, неохотными и притяжательными квантификаторами» . Учебники по Java . Оракул . Архивировано из оригинала 7 октября 2020 года . Проверено 23 декабря 2016 г.
^ "Атомная группировка" . Учебник по регулярным выражениям . Архивировано из оригинала 7 октября 2020 года . Проверено 24 ноября 2019 г.
^ Сезар Кампеану; Кай Саломаа и Шэн Ю (декабрь 2003 г.). «Формальное исследование практических регулярных выражений» . Международный журнал основ компьютерных наук . 14 (6): 1007–1018. doi : 10.1142/S012905410300214X . Архивировано из оригинала 04.07.2015 . Проверено 3 июля 2015 г. . Теорема 3 (стр.9)
^ «Сопоставление регулярных выражений Perl - это NP-Hard» . perl.plover.com . Архивировано из оригинала 07.10.2020 . Проверено 21 ноября 2019 г. .
^ Блуждающая логика. «Как имитировать просмотр вперед и назад в автоматах с конечным состоянием?» . Обмен стеками компьютерных наук . Архивировано из оригинала 7 октября 2020 года . Проверено 24 ноября 2019 г.
^ Кокс (2007)
^ Лаурикари (2009)
^ "gnulib/lib/dfa.c" . Если сканер обнаруживает переход по обратной ссылке, он возвращает своего рода «полууспех», указывающий, что совпадение должно быть проверено с помощью средства сопоставления с возвратом.
^ Кернс, Стивен (август 2013 г.). «Сублинейное сопоставление с конечными автоматами с использованием обратного сканирования суффиксов». arXiv : 1308.3822 [ cs.DS ].
↑ Наварро, Гонсало (10 ноября 2001 г.). «NR-grep: быстрый и гибкий инструмент для сопоставления с образцом» (PDF) . Программное обеспечение: практика и опыт . 31 (13): 1265–1312. doi : 10.1002/spe.411 . S2CID 3175806 . Архивировано (PDF) из оригинала 7 октября 2020 г .. Проверено 21 ноября 2019 г. .
^ "travisdowns/polyregex" . Гитхаб . 5 июля 2019 года. Архивировано из оригинала 14 сентября 2020 года . Проверено 21 ноября 2019 г. .
^ Шмид, Маркус Л. (март 2019 г.). «Регулярные выражения с обратными ссылками: методы сопоставления полиномиального времени». arXiv : 1903.05896 [ cs.FL ].
^ «Документация Vim: шаблон» . Vimdoc.sourceforge.net. Архивировано из оригинала 07.10.2020 . Проверено 25 сентября 2013 г. .
^ a b «UTS # 18 по регулярным выражениям Unicode, Приложение A: Блоки символов» . Архивировано из оригинала 07.10.2020 . Проверено 5 февраля 2010 г. .
↑ Горовиц, Брэдли (24 октября 2011 г.). «Осенняя зачистка» . Блог Google . Архивировано из оригинала 21 октября 2018 года . Проверено 4 мая 2019 г. .
^ Символ 'm' не всегда требуется для указанияоперации сопоставления Perl . Например,m/[^abc]/может также отображаться как/[^abc]/. «m» необходим только в том случае, если пользователь хочет указать операцию сопоставления без использования косой черты в качестве разделителя регулярного выражения . Иногда полезно указать альтернативный разделитель регулярных выражений, чтобы избежать « коллизии разделителей ». Подробнее см. « perldoc perlre. Архивировано 31 декабря 2009 г. на Wayback Machine ».
^ Например, см. Java в двух словах , с. 213; Сценарии Python для вычислительной науки , с. 320; Программирование PHP , с. 106.
^ Обратите внимание, что все операторы if возвращают значение TRUE.
^ Конвей, Дамиан (2005). «Регулярные выражения, конец строки» . Лучшие практики Perl . О'Райли . п. 240. ISBN 978-0-596-00173-5. Архивировано из оригинала 07.10.2020 . Проверено 10 сентября 2017 г. .

использованная литература

Ахо, Альфред В. (1990). ван Левен, Ян (ред.). Алгоритмы поиска закономерностей в строках . Справочник по теоретической информатике, том A: Алгоритмы и сложность . Пресс Массачусетского технологического института. стр. 255–300.
Ахо, Альфред В .; Ульман, Джеффри Д. (1992). «Глава 10. Шаблоны, автоматы и регулярные выражения» (PDF) . Основы информатики . Архивировано из оригинала 07.10.2020 . Проверено 14 декабря 2013 г. .
«Регулярные выражения» . Единая спецификация UNIX, версия 2 . Открытая группа. 1997. Архивировано из оригинала 07 октября 2020 г .. Проверено 13 декабря 2011 г. .
«Глава 9: Регулярные выражения» . Базовые спецификации Open Group . Открытая группа (6). 2004 г. Стандарт IEEE 1003.1, издание 2004 г. Архивировано из оригинала 02.12.2011 . Проверено 13 декабря 2011 г. .
Кокс, Расс (2007). «Сопоставление регулярных выражений может быть простым и быстрым» . Архивировано из оригинала 01 января 2010 г. Проверено 27 апреля 2008 г. .
Форта, Бен (2004). Сэмс Научите себя регулярным выражениям за 10 минут . Сэмс. ISBN 978-0-672-32566-3.
Фридл, Джеффри Э.Ф. (2002). Овладение регулярными выражениями . О'Райли . ISBN 978-0-596-00289-3. Архивировано из оригинала 30 августа 2005 г .. Проверено 26 апреля 2005 г. .
Геладе, Воутер; Невен, Фрэнк (2008). Краткость дополнения и пересечения регулярных выражений . Материалы 25-го Международного симпозиума по теоретическим аспектам информатики (STACS 2008) . стр. 325–336. архив : 0802.2869 . Архивировано из оригинала 18 июля 2011 г. Проверено 15 июня 2009 г. .
Гойвертс, Ян; Левитан, Стивен (2009). Поваренная книга регулярных выражений . [О'Райли]. ISBN 978-0-596-52068-7.
Грубер, Герман; Хольцер, Маркус (2008). Конечные автоматы, связность орграфов и размер регулярных выражений (PDF) . Материалы 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP 2008) . 5126 . стр. 39–50. doi : 10.1007/978-3-540-70583-3_4 . Архивировано (PDF) из оригинала 11 июля 2011 г .. Проверено 3 февраля 2011 г. .
Хабиби, Мехран (2004). Реальные регулярные выражения с Java 1.4 . Спрингер. ISBN 978-1-59059-107-9.
Хопкрофт, Джон Э .; Мотвани, Раджив; Ульман, Джеффри Д. (2000). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон-Уэсли.
Джонсон, Уолтер Л.; Портер, Джеймс Х .; Экли, Стефани I .; Росс, Дуглас Т. (1968). «Автоматическое создание эффективных лексических процессоров с использованием методов конечных состояний». Коммуникации АКМ . 11 (12): 805–813. дои : 10.1145/364175.364185 . S2CID 17253809 .
Клини, Стивен С. (1951). Шеннон, Клод Э .; Маккарти, Джон (ред.). Представление событий в нервных сетях и конечных автоматах (PDF) . Исследования автоматов . Издательство Принстонского университета. стр. 3–42. Архивировано (PDF) из оригинала 07 октября 2020 г .. Проверено 10 декабря 2017 г. .
Козен, Декстер (1991). «Теорема полноты для алгебр Клини и алгебры регулярных событий». [1991] Труды Шестого ежегодного симпозиума IEEE по логике в компьютерных науках . Материалы 6-го ежегодного симпозиума IEEE по логике в компьютерных науках (LICS 1991) . стр. 214–225. doi : 10.1109/LICS.1991.151646 . hdl : 1813/6963 . ISBN 978-0-8186-2230-4. S2CID 19875225 .
Лаурикари, Вилле (2009). "Библиотека TRE 0.7.6" . Архивировано из оригинала 14 июля 2010 г. Проверено 1 апреля 2009 г. .
Лигер, Франсуа; МакКуин, Крейг; Уилтон, Пол (2002). Справочник по работе с текстом в Visual Basic .NET . Врокс Пресс . ISBN 978-1-86100-730-8.
Сипсер, Майкл (1998). «Глава 1: Обычные языки» . Введение в теорию вычислений . Издательство PWS. стр. 31–90 . ISBN 978-0-534-94728-6.
Стаблбайн, Тони (2003). Карманный справочник по регулярным выражениям . О'Райли. ISBN 978-0-596-00415-6.
Томпсон, Кен (1968). «Методы программирования: алгоритм поиска регулярных выражений». Коммуникации АКМ . 11 (6): 419–422. дои : 10.1145/363347.363387 . S2CID 21260384 .
Уолл, Ларри (2002). «Апокалипсис 5: Сопоставление с образцом» . Архивировано из оригинала 12 января 2010 г. Проверено 11 октября 2006 г. .

внешняя ссылка

В Викиучебнике есть книга на тему: Регулярные выражения .

В Wikibook R Programming есть страница на тему: Обработка текста .

Найдите регулярное выражение в Викисловаре, бесплатном словаре.

СМИ, связанные с Regex , на Викискладе?
Регулярные выражения в Curlie
ISO/IEC 9945-2:1993 Информационные технологии – Интерфейс переносимой операционной системы (POSIX) – Часть 2: Оболочка и утилиты
ISO/IEC 9945-2:2002 Информационные технологии – Портативный интерфейс операционной системы (POSIX) – Часть 2: Системные интерфейсы
ISO/IEC 9945-2:2003 Информационные технологии – Портативный интерфейс операционной системы (POSIX) – Часть 2: Системные интерфейсы
ISO/IEC/IEEE 9945:2009 Информационные технологии – Базовые спецификации интерфейса переносимых операционных систем (POSIX®), выпуск 7
Регулярное выражение, стандарт IEEE 1003.1-2017, открытая группа

[1] Гойвартс, Ян. «Учебник по регулярным выражениям - узнайте, как использовать регулярные выражения» . www.regular-expressions.info . Архивировано из оригинала 01.11.2016 . Проверено 31 октября 2016 г. .

[Mitkov2003-2] Митков, Руслан (2003). Оксфордский справочник по вычислительной лингвистике . Издательство Оксфордского университета. п. 754. ISBN 978-0-19-927634-9. Архивировано из оригинала 28 февраля 2017 г. Проверено 25 июля 2016 г. .

[Lawson2003-3] Лоусон, Марк В. (17 сентября 2003 г.). Конечные автоматы . КПР Пресс. стр. 98–100. ISBN 978-1-58488-255-8. Архивировано из оригинала 27 февраля 2017 года . Проверено 25 июля 2016 г.

[FOOTNOTEKleene1951-4] Клини 1951 .

[Leung,_New_Mexico_State_University,_2010-5] Люн, Хинг (16 сентября 2010 г.). «Регулярные языки и конечные автоматы» (PDF) . Университет штата Нью-Мексико . Архивировано из оригинала (PDF) 5 декабря 2013 г .. Проверено 13 августа 2019 г. Концепция регулярных событий была введена Клини через определение регулярных выражений.

[FOOTNOTEThompson1968-6] б Томпсон 1968 .

[FOOTNOTEJohnsonPorterAckleyRoss1968-7] б Джонсон и соавт. 1968 .

[Beautiful_Code_Kernighan-8] Керниган, Брайан (2007-08-08). «Сопоставитель регулярных выражений» . Красивый код . О'Райли Медиа . стр. 1–2. ISBN 978-0-596-51004-6. Архивировано из оригинала 07.10.2020 . Проверено 15 мая 2013 г. .

[9] Ричи, Деннис М. «Неполная история текстового редактора QED» . Архивировано из оригинала 21 февраля 1999 г. Проверено 9 октября 2013 г.

[FOOTNOTEAhoUllman199210.11_Bibliographic_Notes_for_Chapter_10,_p._589-10] Aho & Ullman 1992 , 10.11 Библиографические примечания к главе 10, с. 589.

[FOOTNOTEAycock20032._JIT_Compilation_Techniques,_2.1_Genesis,_p._98-11] Aycock 2003 , 2. Методы компиляции JIT, 2.1 Genesis, p. 98.

[12] Рэймонд, Эрик С. со ссылкой на Денниса Ричи (2003). «Файл жаргона 4.4.7: grep» . Архивировано из оригинала 05.06.2011 . Проверено 17 февраля 2009 г. .

[13] «Новые возможности регулярных выражений в Tcl 8.1» . Архивировано из оригинала 07.10.2020 . Проверено 11 октября 2013 г. .

[14] «Документация PostgreSQL 9.3.1: 9.7. Сопоставление с образцом» . Архивировано из оригинала 07.10.2020 . Проверено 12 октября 2013 г. .

[15] Уолл, Ларри и команда разработчиков Perl 5 (2006). "perlre: регулярные выражения Perl" . Архивировано из оригинала 31 декабря 2009 г .. Проверено 10 октября 2006 г. .

[Apocalypse5-16] а б Стена (2002)

[17] «GROVF | Ускорение аналитики больших данных» . grovf.com . Архивировано из оригинала 07.10.2020 . Проверено 22 октября 2019 г. .

[18] Викискладе есть медиафайлы по теме CUDA . bkase.github.io . Архивировано из оригинала 07.10.2020 . Проверено 22 октября 2019 г. .

[grep-19] справочная страница a b c d grep (1)

[HopcroftMotwaniUllman01-20] а б Хопкрофт, Мотвани и Ульман (2000)

[21] Сипсер (1998)

[22] ↑ Gelade & Neven (2008 , стр. 332, Thm.4.1)

[23] Грубер и Хольцер (2008)

[24] Основываясь на Gelade & Neven (2008) , регулярное выражение длиной около 850, такое что его дополнение имеет длину около 2³² , можно найти в File:RegexComplementBlowup.png .

[25] Джей Л. Гишер (1984). (Название неизвестно) (Технический отчет). Стэнфордский университет, кафедра Comp. наук

[26] Джон Э. Хопкрофт; Раджив Мотвани и Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления . Река Аппер-Сэдл/Нью-Джерси: Эддисон Уэсли. ISBN 978-0-201-44124-6.Здесь: Разд.3.4.6, с.117-120. — Это свойство может не выполняться для расширенных регулярных выражений, даже если они описывают не более крупный класс, чем обычные языки; ср. стр.121.

[27] Козен (1991) ^{[ нужна страница ]}

[28] В. Н. Редько (1964). «Об определяющих соотношениях для алгебры регулярных событий» . Украинский математический журнал . 16 (1): 120–126. Архивировано из оригинала 29 марта 2018 г. Проверено 28 марта 2018 г. . (На русском)

[29] ISO / IEC 9945-2: 1993 Информационные технологии - Интерфейс переносимой операционной системы (POSIX) - Часть 2: Оболочка и утилиты , последовательно пересматриваемый как ISO / IEC 9945-2: 2002 Информационные технологии - Интерфейс переносимой операционной системы (POSIX) - Часть 2: Системные интерфейсы , ISO/IEC 9945-2:2003, а в настоящее время ISO/IEC/IEEE 9945:2009 Информационные технологии – Базовые спецификации интерфейса переносимых операционных систем (POSIX®), выпуск 7

[30] Единая спецификация Unix (версия 2)

[char-classes-emacs-list-2016-31] "33.3.1.2 Классы символов - Руководство по Emacs lisp - Версия 25.1" . gnu.org . 2016. Архивировано из оригинала 07.10.2020 . Проверено 13 апреля 2017 г. .

[32] «Документация по регулярным выражениям Perl» . perldoc.perl.org. Архивировано из оригинала 31 декабря 2009 года . Проверено 8 января 2012 г.

[py-re-33] "Синтаксис регулярных выражений" . Документация Python 3.5.0 . Фонд программного обеспечения Python . Архивировано из оригинала 18 июля 2018 года . Проверено 10 октября 2015 г.

[es-re-34] «Основные классы: регулярные выражения: квантификаторы: различия между жадными, неохотными и притяжательными квантификаторами» . Учебники по Java . Оракул . Архивировано из оригинала 7 октября 2020 года . Проверено 23 декабря 2016 г.

[35] "Атомная группировка" . Учебник по регулярным выражениям . Архивировано из оригинала 7 октября 2020 года . Проверено 24 ноября 2019 г.

[36] Сезар Кампеану; Кай Саломаа и Шэн Ю (декабрь 2003 г.). «Формальное исследование практических регулярных выражений» . Международный журнал основ компьютерных наук . 14 (6): 1007–1018. doi : 10.1142/S012905410300214X . Архивировано из оригинала 04.07.2015 . Проверено 3 июля 2015 г. . Теорема 3 (стр.9)

[37] «Сопоставление регулярных выражений Perl - это NP-Hard» . perl.plover.com . Архивировано из оригинала 07.10.2020 . Проверено 21 ноября 2019 г. .

[38] Блуждающая логика. «Как имитировать просмотр вперед и назад в автоматах с конечным состоянием?» . Обмен стеками компьютерных наук . Архивировано из оригинала 7 октября 2020 года . Проверено 24 ноября 2019 г.

[39] Кокс (2007)

[40] Лаурикари (2009)

[41] "gnulib/lib/dfa.c" . Если сканер обнаруживает переход по обратной ссылке, он возвращает своего рода «полууспех», указывающий, что совпадение должно быть проверено с помощью средства сопоставления с возвратом.

[42] Кернс, Стивен (август 2013 г.). «Сублинейное сопоставление с конечными автоматами с использованием обратного сканирования суффиксов». arXiv : 1308.3822 [ cs.DS ].

[43] Наварро, Гонсало (10 ноября 2001 г.). «NR-grep: быстрый и гибкий инструмент для сопоставления с образцом» (PDF) . Программное обеспечение: практика и опыт . 31 (13): 1265–1312. doi : 10.1002/spe.411 . S2CID 3175806 . Архивировано (PDF) из оригинала 7 октября 2020 г .. Проверено 21 ноября 2019 г. .

[44] "travisdowns/polyregex" . Гитхаб . 5 июля 2019 года. Архивировано из оригинала 14 сентября 2020 года . Проверено 21 ноября 2019 г. .

[45] Шмид, Маркус Л. (март 2019 г.). «Регулярные выражения с обратными ссылками: методы сопоставления полиномиального времени». arXiv : 1903.05896 [ cs.FL ].

[46] «Документация Vim: шаблон» . Vimdoc.sourceforge.net. Архивировано из оригинала 07.10.2020 . Проверено 25 сентября 2013 г. .

[unicode-47] «UTS # 18 по регулярным выражениям Unicode, Приложение A: Блоки символов» . Архивировано из оригинала 07.10.2020 . Проверено 5 февраля 2010 г. .

[48] Горовиц, Брэдли (24 октября 2011 г.). «Осенняя зачистка» . Блог Google . Архивировано из оригинала 21 октября 2018 года . Проверено 4 мая 2019 г. .

[clarify000-49] Символ 'm' не всегда требуется для указанияоперации сопоставления Perl . Например,m/[^abc]/может также отображаться как/[^abc]/. «m» необходим только в том случае, если пользователь хочет указать операцию сопоставления без использования косой черты в качестве разделителя регулярного выражения . Иногда полезно указать альтернативный разделитель регулярных выражений, чтобы избежать « коллизии разделителей ». Подробнее см. « perldoc perlre. Архивировано 31 декабря 2009 г. на Wayback Machine ».

[50] Например, см. Java в двух словах , с. 213; Сценарии Python для вычислительной науки , с. 320; Программирование PHP , с. 106.

[51] Обратите внимание, что все операторы if возвращают значение TRUE.

[Perl_Best_Practices-52] Конвей, Дамиан (2005). «Регулярные выражения, конец строки» . Лучшие практики Perl . О'Райли . п. 240. ISBN 978-0-596-00173-5. Архивировано из оригинала 07.10.2020 . Проверено 10 сентября 2017 г. .

[1]

втеСтруны
Строковый показатель	Приблизительное соответствие строк Битап-алгоритм Расстояние Дамерау – Левенштейна Изменить расстояние Сопоставление гештальт-паттернов Расстояние Хэмминга Расстояние Яро – Винклера Ли расстояние автомат Левенштейна расстояние Левенштейна Алгоритм Вагнера – Фишера
Алгоритм поиска строки	Алгоритм Апостолико – Джанкарло Алгоритм поиска строк Бойера – Мура Алгоритм Бойера-Мура-Хорспула Алгоритм Кнута – Морриса – Пратта Алгоритм Рабина – Карпа
Поиск нескольких строк	Ахо-Корасик Комментарий Алгоритм z-Walter
Регулярное выражение	Сравнение движков регулярных выражений Обычная грамматика Конструкция Томпсона Недетерминированный конечный автомат
Выравнивание последовательности	Алгоритм Хиршберга Алгоритм Нидлмана – Вунша Алгоритм Смита – Уотермана
Структура данных	ДАФСА Массив суффиксов Суффиксный автомат Суффиксное дерево Обобщенное суффиксное дерево Веревка Тернарное дерево поиска попробовать
Другой	Разбор Сопоставление с образцом Сопоставление сжатого шаблона Самая длинная общая подпоследовательность Самая длинная общая подстрока Последовательный анализ шаблонов Сортировка

Авторитетный контроль
Общий	Интегрированный авторитетный файл (Германия)
Национальные библиотеки	Франция (данные) Соединенные Штаты Япония
Другой	Академический Microsoft