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

Последовательность символов, образующая шаблон поиска

Синий Подсветка показывает результаты соответствия шаблону регулярного выражения: (строчная буква r , за которой следует одна или несколько строчных гласных букв)./r[aeiou]+/g

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

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

Регулярные выражения используются в поисковых системах , в диалогах поиска и замены текстовых процессоров и текстовых редакторов , в утилитах обработки текста , таких как sed и AWK , и в лексическом анализе . Регулярные выражения поддерживаются во многих языках программирования. Реализации библиотек часто называют « движком », ^{[4] [5]} и многие из них доступны для повторного использования.

История

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

Регулярные выражения возникли в 1951 году, когда математик Стивен Коул Клини описал регулярные языки, используя свою математическую нотацию, называемую регулярными событиями . ^{[6] [7]} Они возникли в теоретической информатике , в подобластях теории автоматов (моделей вычислений) и описания и классификации формальных языков , мотивированных попыткой Клини описать ранние искусственные нейронные сети . (Клин представил его как альтернативу термину «постижимый» Маккалока и Питтса , но признал: «Мы будем приветствовать любые предложения относительно более описательного термина». ^[8] ) Другие ранние реализации сопоставления с образцом включают язык SNOBOL , который не использовал регулярные выражения, а вместо этого свои собственные конструкции сопоставления с образцом.

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

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

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

Использование регулярных выражений в стандартах структурированной информации для моделирования документов и баз данных началось в 1960-х годах и расширилось в 1980-х годах, когда консолидировались отраслевые стандарты, такие как ISO SGML (предшественником которого был ANSI "GCA 101-1983"). Ядро стандартов языка спецификации структур состоит из регулярных выражений. Его использование очевидно в синтаксисе группы элементов DTD . До использования регулярных выражений многие языки поиска допускали простые подстановочные знаки, например, "*" для соответствия любой последовательности символов и "?" для соответствия одному символу. Остатки этого можно найти сегодня в синтаксисе glob для имен файлов и в операторе SQL LIKE .

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

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

Узоры

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

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

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

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

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

Основные понятия

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

Большинство формализмов предоставляют следующие операции для построения регулярных выражений.

Булевое "или"

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

Группировка

Скобки используются для определения области действия и приоритета операторов ( среди прочего). Например, gray|greyи являются эквивалентными шаблонами, которые оба описывают множество "серый" или "серый".gr(a|e)y

Количественная оценка

Квантификатор после элемента (например, токена , символа или группы) указывает, сколько раз допускается повторение предыдущего элемента. Наиболее распространенными квантификаторами являются вопросительный знак , звездочка (происходит от звезды Клини ) и знак плюс ( плюс Клини ). ? * +

Универсальный символ

Подстановочный знак .соответствует любому символу. Например,

a.bсоответствует любой строке, содержащей «a», затем любой символ, а затем «b».

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

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

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

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

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

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

Регулярные выражения состоят из констант, которые обозначают наборы строк, и символов операторов, которые обозначают операции над этими наборами. Следующее определение является стандартным и встречается в большинстве учебников по теории формального языка. ^{[24] [25]} Учитывая конечный алфавит Σ, следующие константы определяются как регулярные выражения:

• ( пустое множество ) ∅ обозначает множество ∅.
• ( пустая строка ) ε обозначает набор, содержащий только «пустую» строку, которая вообще не содержит символов.
• ( буквенный символ ) 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)описывает {"ab", "c", "d", "ef"}.
• ( Звезда Клини ) (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», «aaa», ...}
• 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 . В принципе, оператор дополнения избыточен, поскольку он не предоставляет никакой дополнительной выразительной силы. Однако он может сделать регулярное выражение намного более кратким — исключение одного оператора дополнения может вызвать двойной экспоненциальный взрыв его длины. ^{[26] [27] [28]}

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

Обобщение этой закономерности на L _k дает выражение:

${\displaystyle (a\mid b)^{*}a\underbrace {(a\mid b)(a\mid b)\cdots (a\mid b)} _{k-1{\text{ times}}}.\,}$

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

В противоположном направлении, есть много языков, которые легко описываются DFA, но нелегко описываются регулярным выражением. Например, определение действительности данного ISBN требует вычисления модуля целого числа с основанием 11 и может быть легко реализовано с помощью 11-стабильного DFA. Однако преобразование его в регулярное выражение приводит к файлу размером 2,14 мегабайта. ^[29]

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

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

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

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

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

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

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

Синтаксис

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

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

Разделители

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

Стандарт IEEE POSIX

Стандарт IEEE POSIX имеет три набора соответствия: BRE (базовые регулярные выражения), ^[34] ERE (расширенные регулярные выражения) и SRE (простые регулярные выражения). SRE устарело [ ^35] в пользу 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 ) этого не требует.

Примеры:

• .atсоответствует любой трехсимвольной строке, заканчивающейся на «at», включая «hat», «cat», «bat», «4at», «#at» и «at» (начинающейся с пробела).
• [hc]atсоответствует "шляпа" и "кошка".
• [^b]atсоответствует всем строкам, соответствующим условию, .atза исключением «bat».
• [^hc]atсоответствует всем строкам, не соответствующим .at«hat» и «cat».
• ^[hc]atсоответствует «hat» и «cat», но только в начале строки или отрезка.
• [hc]at$соответствует словам «hat» и «cat», но только в конце строки или ряда.
• \[.\]соответствует любому одиночному символу, заключенному в скобки «[» и «]», поскольку скобки экранированы, например: «[a]», «[b]», «[7]», «[@]», «[]]» и «[ ]» (скобка пробел скобка).
• s.*соответствует s, за которым следует ноль или более символов, например: "s", "saw", "seed", "s3w96.7" и "s6#h%(>>>mn mQ".

По словам Расса Кокса, спецификация POSIX требует, чтобы неоднозначные подвыражения обрабатывались способом, отличным от Perl. Комитет заменил правила Perl на те, которые легко объяснить, но новые «простые» правила на самом деле сложнее реализовать: они были несовместимы с уже существующими инструментами и сделали по сути невозможным определение расширения «ленивого сопоставления» (см. ниже). В результате очень немногие программы фактически реализуют правила подвыражений POSIX (даже когда они реализуют другие части синтаксиса POSIX). ^[37]

Метасимволы в расширенном POSIX

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

Примеры:

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

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

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

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

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

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

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

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

Perl и PCRE

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

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

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

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

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

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

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

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

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

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

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

IETF I-Regexp

IETF RFC 9485 описывает "I-Regexp: совместимый формат регулярных выражений". Он определяет ограниченное подмножество идиом регулярных выражений, разработанных для совместимости, т. е. создания того же эффекта, в большом количестве библиотек регулярных выражений. I-Regexp также ограничен сопоставлением, т. е. предоставлением истинного или ложного соответствия между регулярным выражением и заданным фрагментом текста. Таким образом, в нем отсутствуют расширенные функции, такие как группы захвата, опережающий просмотр и обратные ссылки. ^[43]

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

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

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

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

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

Утверждения

Другие функции, не встречающиеся в описании обычных языков, включают утверждения. К ним относятся вездесущие ^и $, используемые по крайней мере с 1970 года, ^[46] а также некоторые более сложные расширения, такие как lookaround, появившиеся в 1994 году. ^[47] Lookarounds определяют окружение совпадения и не проникают в само совпадение, функция, актуальная только для случая использования поиска по строке. ^{[ необходима цитата ]} Некоторые из них можно смоделировать в обычном языке, рассматривая окружение как часть языка. ^[48]

TheУтверждения о взгляде вперед (?=...) и(?!...)были засвидетельствованы по крайней мере с 1994 года, начиная с Perl 5. ^[47] Утверждения о взгляде назад(?<=...)и(?<!...)были засвидетельствованы с 1997 года в коммите Ильи Захаревича в Perl 5.005. ^[49]

Реализации и время выполнения

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

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

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

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

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

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

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

Юникод

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

• Поддерживаемая кодировка . Некоторые библиотеки регулярных выражений ожидают работы с определенной кодировкой вместо абстрактных символов Unicode. Многие из них требуют кодировку UTF-8 , в то время как другие могут ожидать UTF-16 или UTF-32 . Напротив, Perl и Java не зависят от кодировок, а работают с декодированными символами внутренне.
• Поддерживаемый диапазон Unicode . Многие движки регулярных выражений поддерживают только Basic Multilingual Plane , то есть символы, которые можно закодировать только 16 битами. В настоящее время (по состоянию на 2016 год ^{[обновлять]}) только несколько движков регулярных выражений (например, Perl и Java) могут обрабатывать полный 21-битный диапазон Unicode.
• Расширение конструкций, ориентированных на ASCII, на Unicode . Например, в реализациях на основе ASCII диапазоны символов формы [x-y]действительны везде, где x и y имеют кодовые точки в диапазоне [0x00,0x7F] и codepoint( x ) ≤ codepoint( y ). Естественное расширение таких диапазонов символов на Unicode просто изменило бы требование, чтобы конечные точки лежали в [0x00,0x7F], на требование, чтобы они лежали в [0x0000,0x10FFFF]. Однако на практике это часто не так. Некоторые реализации, такие как gawk , не позволяют диапазонам символов пересекать блоки Unicode. Диапазон типа [0x61,0x7F] является допустимым, поскольку обе конечные точки попадают в блок Basic Latin, как и [0x0530,0x0560], поскольку обе конечные точки попадают в блок Armenian, но диапазон типа [0x0061,0x0532] является недопустимым, поскольку он включает несколько блоков Unicode. Другие движки, такие как редактор Vim , допускают пересечение блоков, но значения символов не должны отличаться более чем на 256. ^[57]
• Нечувствительность к регистру . Некоторые флаги нечувствительности к регистру влияют только на символы ASCII. Другие флаги влияют на все символы. Некоторые движки имеют два разных флага: один для ASCII, другой для Unicode. Точное определение того, какие символы относятся к классам POSIX, также различается.
• Двоюродные братья нечувствительности к регистру . Поскольку ASCII различает регистр, нечувствительность к регистру стала логичной функцией при поиске текста. Unicode ввел алфавитные письменности без регистра, такие как деванагари . Для них чувствительность к регистру неприменима. Для письменностей, таких как китайский, другое различие кажется логичным: между традиционным и упрощенным. В арабских письменностях может быть желательной нечувствительность к начальной, средней, конечной и изолированной позиции . В японском языке нечувствительность между хираганой и катаканой иногда полезна.
• Нормализация . В Unicode есть объединяющиеся символы . Как и в старых пишущих машинках, за простыми базовыми символами (пробелами, знаками препинания, символами, цифрами или буквами) может следовать один или несколько нераздельных символов (обычно диакритических знаков, таких как знаки ударения, изменяющие буквы), чтобы сформировать один печатный символ; но Unicode также предоставляет ограниченный набор предсоставленных символов, т. е. символов, которые уже включают один или несколько объединяющихся символов. Последовательность из базового символа + объединяющихся символов должна быть сопоставлена ​​с идентичным одним предсоставленным символом (только некоторые из этих объединяющихся последовательностей могут быть предварительно составлены в один символ Unicode, но в Unicode возможно бесконечно много других объединяющихся последовательностей, и они необходимы для различных языков, используя один или несколько объединяющихся символов после начального базового символа; эти объединяющиеся последовательности могут включать базовый символ или частично составленные объединяющиеся символы, но не обязательно в каноническом порядке и не обязательно с использованием канонических предсоставлений). Процесс стандартизации последовательностей базового символа + объединяющих символов путем разложения этих канонически эквивалентных последовательностей перед их переупорядочением в каноническом порядке (и при необходимости повторным объединением некоторых объединяющих символов в ведущий базовый символ) называется нормализацией.
• Новые управляющие коды . Unicode ввел, среди прочих кодов, метки порядка байтов и маркеры направления текста. С этими кодами, возможно, придется обращаться особым образом.
• Введение классов символов для блоков Unicode, скриптов и многочисленных других свойств символов . Свойства блоков гораздо менее полезны, чем свойства скрипта, поскольку блок может иметь кодовые точки из нескольких разных скриптов, а скрипт может иметь кодовые точки из нескольких разных блоков. ^[58] В 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}.

Языковая поддержка

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

Использует

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

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

Некоторые высокопроизводительные настольные издательские программы имеют возможность использовать регулярные выражения для автоматического применения стилей текста, избавляя человека, делающего макет, от кропотливого выполнения этого вручную для всего, что может быть сопоставлено регулярным выражением. Например, определив стиль символов , который преобразует текст в маленькие заглавные буквы , а затем используя регулярное выражение [A-Z]{4,}для применения этого стиля, любое слово из четырех или более последовательных заглавных букв будет автоматически отображаться как маленькие заглавные буквы.

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

Примеры

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

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

В примерах используются следующие условные обозначения. ^[60]

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

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

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

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

Индукция

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

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

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

Примечания

1. Goyvaerts, Jan. "Regular Expression Tutorial - Learn How to Use Regular Expressions". Regular-Expressions.info . Архивировано из оригинала 2016-11-01 . Получено 2016-10-31 .
2. Митков, Руслан (2003). Оксфордский справочник по компьютерной лингвистике. Oxford University Press. стр. 754. ISBN 978-0-19-927634-9. Архивировано из оригинала 2017-02-28 . Получено 2016-07-25 .
3. Лоусон, Марк В. (17 сентября 2003 г.). Конечные автоматы. CRC Press. стр. 98–100. ISBN 978-1-58488-255-8. Архивировано из оригинала 27 февраля 2017 . Получено 25 июля 2016 .
4. «Как работает внутренняя система регулярных выражений». regular-expressions.info . Получено 24 февраля 2024 г. .
5. Хеддингс, Энтони (11 марта 2020 г.). «Как на самом деле использовать Regex?». howtogeek.com . Получено 24 февраля 2024 г. .
6. Клини 1951.
7. Leung, Hing (16 сентября 2010 г.). «Регулярные языки и конечные автоматы» (PDF) . New Mexico State University . Архивировано из оригинала (PDF) 5 декабря 2013 г. . Получено 13 августа 2019 г. . Концепция регулярных событий была введена Клини через определение регулярных выражений.
8. Клини 1951, стр. 46
9. Томпсон 1968.
10. Джонсон и др. 1968.
11. Керниган, Брайан (2007-08-08). "A Regular Expressions Matcher". Beautiful Code . O'Reilly Media . стр. 1–2. ISBN 978-0-596-51004-6. Архивировано из оригинала 2020-10-07 . Получено 2013-05-15 .
12. Ритчи, Деннис М. "Неполная история текстового редактора QED". Архивировано из оригинала 1999-02-21 . Получено 9 октября 2013 .
13. Aho & Ullman 1992, 10.11 Библиографические примечания к главе 10, стр. 589.
14. Эйкок 2003, стр. 98.
15. Raymond, Eric S. цитирует Dennis Ritchie (2003). "Jargon File 4.4.7: grep". Архивировано из оригинала 2011-06-05 . Получено 2009-02-17 .
16. "Новые функции регулярных выражений в Tcl 8.1". Архивировано из оригинала 2020-10-07 . Получено 2013-10-11 .
17. "Документация: 9.3: Сопоставление с образцом". PostgreSQL . Архивировано из оригинала 2020-10-07 . Получено 2013-10-12 .
18. Уолл, Ларри (2006). "Perl Regular Expressions". perlre . Архивировано из оригинала 2009-12-31 . Получено 2006-10-10 .
19. Wall (2002)
20. "PCRE - Perl-совместимые регулярные выражения". www.pcre.org . Получено 2024-04-07 .
21. "GRegex – Faster Analytics for Unstructured Text Data". grovf.com . Архивировано из оригинала 2020-10-07 . Получено 2019-10-22 .
22. "CUDA grep". bkase.github.io . Архивировано из оригинала 2020-10-07 . Получено 2019-10-22 .
23. Керриск, Майкл. "grep(1) - страница руководства Linux". man7.org . Получено 31 января 2023 г. .
24. Хопкрофт, Мотвани и Ульман (2000)
25. Сипсер (1998)
26. Геладе и Невен (2008, стр. 332, Thm.4.1)
27. Грубер и Хольцер (2008)
28. Согласно работе Гелада и Невена (2008), регулярное выражение длиной около 850, такое, что его дополнение имеет длину около 2 ^32, можно найти по адресу File:RegexComplementBlowup.png .
29. "Регулярные выражения для определения делимости". s3.boskent.com . Получено 2024-02-21 .
30. Gischer, Jay L. (1984). (Название неизвестно) (Технический отчет). Stanford Univ., Dept. of Comp. Sc.^{[ название отсутствует ]}
31. Хопкрофт, Джон Э.; Мотвани, Раджив и Ульман, Джеффри Д. (2003). Введение в теорию автоматов, языки и вычисления . Верхняя Сэддл-Ривер, Нью-Джерси: Addison Wesley. стр. 117–120. ISBN 978-0-201-44124-6. Это свойство не обязательно должно выполняться для расширенных регулярных выражений, даже если они не описывают больший класс, чем регулярные языки; см. стр. 121.
32. Козен (1991) ^{[ нужна страница ]}
33. Редько, ВН (1964). «Об определяющих соотношениях для алгебры регулярных событий». Украинский математический журнал . 16 (1): 120–126. Архивировано из оригинала 29.03.2018 . Получено 28.03.2018 .
34. 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
35. Единая спецификация Unix (версия 2)
36. "9.3.6 BRE, соответствующие нескольким символам". The Open Group Base Specifications Issue 7, издание 2018 г. The Open Group. 2017 г. Получено 10 декабря 2023 г.
37. Расс Кокс (2009). "Regular Expression Matching: the Virtual Machine Approach". swtch.com . Отступление: POSIX Submatching
38. "Perl Regular Expression Documentation". perldoc.perl.org. Архивировано из оригинала 31 декабря 2009 г. Получено 5 ноября 2024 г.
39. "Regular Expression Syntax". Документация Python 3.5.0 . Python Software Foundation . Архивировано из оригинала 18 июля 2018 г. Получено 10 октября 2015 г.
40. SRE: Атомная группировка (?>...) не поддерживается #34627
41. "Essential classes: Regular Expressions: Quantifiers: Differences Among Greedy, Reluctant, and Possessive Quantifiers". Учебники Java . Oracle . Архивировано из оригинала 7 октября 2020 г. Получено 23 декабря 2016 г.
42. "Atomic Grouping". Regex Tutorial . Архивировано из оригинала 7 октября 2020 г. Получено 24 ноября 2019 г.
43. Борман, Карстен; Брей, Тим. I-Regexp: совместимый формат регулярных выражений. Internet Engineering Task Force. doi : 10.17487/RFC9485 . RFC 9485. Получено 11 марта 2024 г.
44. Cezar Câmpeanu; Kai Salomaa & Sheng Yu (декабрь 2003 г.). "Формальное исследование практических регулярных выражений". International Journal of Foundations of Computer Science . 14 (6): 1007–1018. doi :10.1142/S012905410300214X. Архивировано из оригинала 2015-07-04 . Получено 2015-07-03 .Теорема 3 (стр.9)
45. "Perl Regular Expression Matching is NP-Hard". perl.plover.com . Архивировано из оригинала 2020-10-07 . Получено 2019-11-21 .
46. Ritchie, DM; Thompson, KL (июнь 1970 г.). Текстовый редактор QED (PDF) . MM-70-1373-3. Архивировано из оригинала (PDF) 2015-02-03 . Получено 2022-09-05 .Переиздано как «Справочное руководство по текстовому редактору QED», MHCC-004, Murray Hill Computing, Bell Laboratories (октябрь 1972 г.).
47. Wall, Larry (1994-10-18). "Perl 5: perlre.pod". GitHub .
48. Wandering Logic. «Как имитировать просмотры вперед и назад в конечных автоматах?». Computer Science Stack Exchange . Архивировано из оригинала 7 октября 2020 г. Получено 24 ноября 2019 г.
49. Захаревич, Илья (1997-11-19). "Применен большой патч регулярных выражений (с небольшими исправлениями): Perl/perl5@c277df4". GitHub .
50. Кокс (2007)
51. Лаурикари (2009)
52. "gnulib/lib/dfa.c". Архивировано из оригинала 2021-08-18 . Получено 2022-02-12 . Если сканер обнаруживает переход по backref, он возвращает своего рода "полууспех", указывающий на то, что соответствие должно быть проверено с помощью сопоставителя с возвратом.
53. Кернс, Стивен (август 2013 г.). «Сублинейное сопоставление с конечными автоматами с использованием обратного сканирования суффиксов». arXiv : 1308.3822 [cs.DS].
54. Наварро, Гонсало (10 ноября 2001 г.). «NR-grep: быстрый и гибкий инструмент сопоставления с образцом» (PDF) . Программное обеспечение: практика и опыт . 31 (13): 1265–1312. doi :10.1002/spe.411. S2CID  3175806. Архивировано (PDF) из оригинала 7 октября 2020 г. . Получено 21 ноября 2019 г. .
55. "travisdowns/polyregex". GitHub . 5 июля 2019 г. Архивировано из оригинала 14 сентября 2020 г. Получено 21 ноября 2019 г.
56. Шмид, Маркус Л. (март 2019 г.). «Регулярные выражения с обратными ссылками: методы сопоставления за полиномиальное время». arXiv : 1903.05896 [cs.FL].
57. "Vim documentation: pattern". Vimdoc.sourceforge.net. Архивировано из оригинала 2020-10-07 . Получено 2013-09-25 .
58. "UTS#18 on Unicode Regular Expressions, Annex A: Character Blocks". Архивировано из оригинала 2020-10-07 . Получено 2010-02-05 .
59. Хоровиц, Брэдли (24 октября 2011 г.). "A fall sweep". Google Blog . Архивировано из оригинала 21 октября 2018 г. Получено 4 мая 2019 г.
60. Символ 'm' не всегда требуется для указания операции сопоставления Perl . Например, m/[^abc]/также может быть отображен как /[^abc]/. 'm' необходим только в том случае, если пользователь хочет указать операцию сопоставления без использования прямой косой черты в качестве разделителя регулярного выражения . Иногда полезно указать альтернативный разделитель регулярного выражения, чтобы избежать " коллизии разделителей ". Подробнее см. 'perldoc perlre Архивировано 2009-12-31 на Wayback Machine '.
61. Например, см. Java in a Nutshell , стр. 213; Python Scripting for Computational Science , стр. 320; Programming PHP , стр. 106.
62. Все операторы if возвращают значение TRUE.
63. Conway, Damian (2005). "Регулярные выражения, конец строки". Perl Best Practices . O'Reilly . стр. 240. ISBN 978-0-596-00173-5. Архивировано из оригинала 2020-10-07 . Получено 2017-09-10 .

Ссылки

• Ахо, Альфред В. (1990). «Алгоритмы поиска закономерностей в строках». В Ван Леувене, Ян (ред.). Справочник по теоретической информатике, том A: Алгоритмы и сложность . Издательство MIT. С. 255–300.
• Ахо, Альфред В.; Ульман, Джеффри Д. (1992). "Глава 10. Шаблоны, автоматы и регулярные выражения" (PDF) . Основы компьютерной науки. Архивировано из оригинала 2020-10-07 . Получено 2013-12-14 .
• Aycock, John (июнь 2003 г.). «Краткая история «точно вовремя»» (PDF) . ACM Computing Surveys . 35 (2): 97–113. CiteSeerX  10.1.1.97.3985 . doi :10.1145/857076.857077. S2CID  15345671.
• "Регулярные выражения". Единая спецификация UNIX, версия 2. The Open Group. 1997. Архивировано из оригинала 2020-10-07 . Получено 2011-12-13 .
• "Глава 9: Регулярные выражения". The Open Group Base Specifications (6). The Open Group. 2004. IEEE Std 1003.1, издание 2004 г. Архивировано из оригинала 2011-12-02 . Получено 2011-12-13 .
• Кокс, Расс (2007). "Соответствие регулярным выражениям может быть простым и быстрым". Архивировано из оригинала 2010-01-01 . Получено 2008-04-27 .
• Форта, Бен (2004). Сэмс. Изучите регулярные выражения за 10 минут . Сэмс. ISBN 978-0-672-32566-3.
• Фридл, Джеффри ЭФ (2002). Освоение регулярных выражений. O'Reilly . ISBN 978-0-596-00289-3. Архивировано из оригинала 2005-08-30 . Получено 2005-04-26 .
• Gelade, Wouter; Neven, Frank (2008). Succinctness of the Complement and Intersection of Regular Expressions. Труды 25-го Международного симпозиума по теоретическим аспектам компьютерной науки (STACS 2008) . стр. 325–336. arXiv : 0802.2869 . Архивировано из оригинала 2011-07-18 . Получено 2009-06-15 .
• Goyvaerts, Jan; Levithan, Steven (2009). Книга рецептов регулярных выражений . [O'reilly]. ISBN 978-0-596-52068-7.
• Грубер, Герман; Хольцер, Маркус (2008). Конечные автоматы, связность диграфов и размер регулярных выражений (PDF) . Труды 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP 2008) . Конспект лекций по информатике. Том 5126. С. 39–50. doi :10.1007/978-3-540-70583-3_4. ISBN 978-3-540-70582-6. Архивировано (PDF) из оригинала 2011-07-11 . Получено 2011-02-03 .
• Хабиби, Мехран (2004). Регулярные выражения реального мира с Java 1.4 . Springer. ISBN 978-1-59059-107-9.
• Хопкрофт, Джон Э.; Мотвани, Раджив; Ульман, Джеффри Д. (2000). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон-Уэсли.
• Джонсон, Уолтер Л.; Портер, Джеймс Х.; Экли, Стефани И.; Росс, Дуглас Т. (1968). «Автоматическая генерация эффективных лексических процессоров с использованием методов конечных состояний». Сообщения ACM . 11 (12): 805–813. doi : 10.1145/364175.364185 . S2CID  17253809.
• Kleene, Stephen C. (1951). «Представление событий в нервных сетях и конечных автоматах». В Shannon, Claude E.; McCarthy, John (ред.). Automata Studies (PDF) . Princeton University Press. стр. 3–42. Архивировано (PDF) из оригинала 2020-10-07 . Получено 2017-12-10 .
• Козен, Декстер (1991). «Теорема полноты для алгебр Клини и алгебры регулярных событий». [1991] Труды шестого ежегодного симпозиума IEEE по логике в компьютерных науках . стр. 214–225. doi :10.1109/LICS.1991.151646. hdl :1813/6963. ISBN 978-0-8186-2230-4. S2CID  19875225.
• Laurikari, Ville (2009). "TRE library 0.7.6". Архивировано из оригинала 2010-07-14 . Получено 2009-04-01 .
• Лигер, Франсуа; Маккуин, Крейг; Уилтон, Пол (2002). Справочник по работе с текстом в Visual Basic .NET . Wrox Press . ISBN 978-1-86100-730-8.
• Sipser, Michael (1998). "Глава 1: Регулярные языки" . Введение в теорию вычислений . PWS Publishing. стр. 31–90. ISBN 978-0-534-94728-6.
• Stubblebine, Tony (2003). Карманный справочник по регулярным выражениям . O'Reilly. ISBN 978-0-596-00415-6.
• Томпсон, Кен (1968). «Техники программирования: алгоритм поиска регулярных выражений». Сообщения ACM . 11 (6): 419–422. doi : 10.1145/363347.363387 . S2CID  21260384.
• Уолл, Ларри (2002). "Апокалипсис 5: Сопоставление с образцом". Архивировано из оригинала 2010-01-12 . Получено 2006-10-11 .

Внешние ссылки

• Медиа, связанные с Regex на Wikimedia Commons
• 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 Std 1003.1-2017, Открытая группа