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

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

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

Регулярное выражение (сокращенно 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 в совместимой системе разделения времени , важном раннем примере 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 под названием Advanced Regular Expressions . ^[13] Библиотека Tcl представляет собой гибридную реализацию NFA / DFA с улучшенными характеристиками производительности. Программные проекты, в которых реализована реализация регулярных выражений Tcl Спенсера, включают PostgreSQL . ^[14] Позже Perl расширил исходную библиотеку Спенсера, добавив множество новых функций. ^[15] Часть усилий при разработке Raku (ранее называвшегося Perl 6) направлена ​​на улучшение интеграции регулярных выражений Perl, а также на расширение их области применения и возможностей, позволяющих определять грамматики синтаксического анализа выражений . ^[16] Результатом стал мини-язык под названием «правила Раку» , который используется для определения грамматики Раку, а также предоставляет программистам инструмент на этом языке. Эти правила поддерживают существующие функции регулярных выражений Perl 5.x, но также позволяют определять парсер рекурсивного спуска в стиле BNF через подправила.

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

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

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

Узоры

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

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

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

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

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

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

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

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

Логическое "или"

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

Группировка

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

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

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

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

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

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

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

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

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

Формальная теория языка

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

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

Регулярные выражения состоят из констант, которые обозначают наборы строк, и символов операторов, которые обозначают операции над этими наборами. Следующее определение является стандартным и встречается в большинстве учебников по теории формального языка. ^{[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|ε)обозначает набор строк, начинающихся с «а», затем нуля или более букв «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]}

Регулярные выражения в этом смысле могут выражать регулярные языки, а именно тот класс языков, который принимается детерминированными конечными автоматами . Однако есть существенная разница в компактности. Некоторые классы регулярных языков могут быть описаны только детерминированными конечными автоматами, размер которых растет экспоненциально с увеличением размера кратчайшего эквивалентного регулярного выражения. Стандартным примером здесь являются языки L _k , состоящие из всех строк алфавита { a , b }, k ^-я буква которых с конца равна  a . С одной стороны, регулярное выражение, описывающее L ₄ , имеет вид . ${\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}}}.\,}$

С другой стороны, известно, что каждый детерминированный конечный автомат, допускающий язык Lk _, должен иметь не менее 2k ^{состояний} . К счастью, существует простое преобразование регулярных выражений в более общие недетерминированные конечные автоматы (НКА), которое не приводит к такому увеличению размера; по этой причине NFA часто используются как альтернативные представления обычных языков. 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]

Синтаксис

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

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

Разделители

При вводе регулярных выражений на языке программирования они могут быть представлены как обычный строковый литерал, поэтому обычно заключаются в кавычки; это часто встречается, например, в C, Java и Python, где регулярное выражение reвводится как "re". Однако они часто пишутся с косыми чертами в качестве разделителей , например, /re/для регулярных выражений re. Это происходит из ed , где /находится команда редактора для поиска, а выражение /re/может использоваться для указания диапазона строк (соответствующих шаблону), которые можно комбинировать с другими командами с обеих сторон, наиболее известным из которых g/re/pявляется grep («глобальные 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 ) этого не делает.

Примеры:

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

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

POSIX расширен

Значение метасимволов, экранированных обратной косой чертой, меняется на противоположное для некоторых символов в синтаксисе расширенного регулярного выражения POSIX ( ERE ). При таком синтаксисе обратная косая черта заставляет метасимвол рассматриваться как буквальный символ. Так, например, \( \)сейчас ( )и \{ \}сейчас { }. Кроме того, удалена поддержка обратных ссылок и добавлены следующие метасимволы:\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 называет выражениями в скобках .

Перл и 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. ^[33]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Утверждения

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

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

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

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

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

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

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

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

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

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

Юникод

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

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

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

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

• С ^[53]
• С++ ^[54]
• Ява ^[55]
• JavaScript ^[56]
• Окамл ^[57]
• Перл ^[58]
• PHP ^[59]
• Питон ^[60]
• Ржавчина ^[61]

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

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

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

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

Примеры

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

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

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

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

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

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

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

Индукция

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

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

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

Примечания

1. Гойвартс, январь. «Учебное пособие по регулярным выражениям. Узнайте, как использовать регулярные выражения». Регулярные выражения.info . Архивировано из оригинала 1 ноября 2016 г. Проверено 31 октября 2016 г.
2. Митьков, Руслан (2003). Оксфордский справочник по компьютерной лингвистике. Издательство Оксфордского университета. п. 754. ИСБН 978-0-19-927634-9. Архивировано из оригинала 28 февраля 2017 г. Проверено 25 июля 2016 г.
3. Лоусон, Марк В. (17 сентября 2003 г.). Конечные автоматы. ЦРК Пресс. стр. 98–100. ISBN 978-1-58488-255-8. Архивировано из оригинала 27 февраля 2017 года . Проверено 25 июля 2016 г.
4. Клини 1951.
5. Люнг, Хинг (16 сентября 2010 г.). «Регулярные языки и конечные автоматы» (PDF) . Университет штата Нью-Мексико . Архивировано из оригинала (PDF) 5 декабря 2013 года . Проверено 13 августа 2019 г. Понятие регулярных событий было введено Клини через определение регулярных выражений.
6. Томпсон 1968.
7. Джонсон и др. 1968.
8. Керниган, Брайан (8 августа 2007 г.). «Сопоставитель регулярных выражений». Красивый код . О'Рейли Медиа . стр. 1–2. ISBN 978-0-596-51004-6. Архивировано из оригинала 07.10.2020 . Проверено 15 мая 2013 г.
9. Ричи, Деннис М. «Неполная история текстового редактора QED». Архивировано из оригинала 21 февраля 1999 г. Проверено 9 октября 2013 г.
10. Aho & Ullman 1992, 10.11 Библиографические примечания к главе 10, стр. 10.11. 589.
11. Эйкок 2003, с. 98.
12. Раймонд, Эрик С. со ссылкой на Денниса Ричи (2003). «Жаргонный файл 4.4.7: grep». Архивировано из оригинала 5 июня 2011 г. Проверено 17 февраля 2009 г.
13. «Новые функции регулярных выражений в Tcl 8.1» . Архивировано из оригинала 07.10.2020 . Проверено 11 октября 2013 г.
14. «Документация: 9.3: Сопоставление с образцом» . ПостгреСБЛ . Архивировано из оригинала 07.10.2020 . Проверено 12 октября 2013 г.
15. Уолл, Ларри (2006). «Регулярные выражения Perl». перлр . Архивировано из оригинала 31 декабря 2009 г. Проверено 10 октября 2006 г.
16. Стена (2002)
17. «GRegex – более быстрая аналитика неструктурированных текстовых данных» . grovf.com . Архивировано из оригинала 07.10.2020 . Проверено 22 октября 2019 г.
18. "CUDA grep" . bkase.github.io . Архивировано из оригинала 07.10.2020 . Проверено 22 октября 2019 г.
19. Керриск, Майкл. «grep(1) — страница руководства Linux». man7.org . Проверено 31 января 2023 г.
20. Хопкрофт, Мотвани и Ульман (2000)
21. Сипсер (1998)
22. Геладе и Невен (2008, стр. 332, Thm.4.1)
23. Грубер и Хольцер (2008)
24. На основе Gelade & Neven (2008), регулярное выражение длиной около 850, такое, что его дополнение имеет длину около 2 ³² , можно найти в File:RegexComplementBlowup.png .
25. Гишер, Джей Л. (1984). (Название неизвестно) (Технический отчет). Стэнфордский университет, кафедра Comp. наук.^{[ название отсутствует ]}
26. Хопкрофт, Джон Э.; Мотвани, Раджив и Уллман, Джеффри Д. (2003). Введение в теорию автоматов, языки и вычисления . Река Аппер-Сэддл, Нью-Джерси: Эддисон Уэсли. стр. 117–120. ISBN 978-0-201-44124-6. Это свойство не обязательно должно соблюдаться для расширенных регулярных выражений, даже если они описывают не более крупный класс, чем обычные языки; ср. стр.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)
31. «9.3.6 BRE, соответствующие нескольким символам» . Базовые спецификации открытой группы, выпуск 7, издание 2018 г. Открытая группа. 2017 . Проверено 10 декабря 2023 г.
32. «Сопоставление регулярных выражений: подход виртуальной машины» . swtch.com . Отступление: сопоставление POSIX
33. «Документация по регулярным выражениям Perl» . perldoc.perl.org. Архивировано из оригинала 31 декабря 2009 года . Проверено 8 января 2012 г.
34. «Синтаксис регулярных выражений». Документация Python 3.5.0 . Фонд программного обеспечения Python . Архивировано из оригинала 18 июля 2018 года . Проверено 10 октября 2015 г.
35. SRE: атомарная группировка (?>...) не поддерживается # 34627.
36. «Основные классы: Регулярные выражения: Кванторы: различия между жадными, неохотными и притяжательными кванторами». Учебники по Java . Оракул . Архивировано из оригинала 7 октября 2020 года . Проверено 23 декабря 2016 г.
37. «Атомная группировка». Учебник по регулярным выражениям . Архивировано из оригинала 7 октября 2020 года . Проверено 24 ноября 2019 г.
38. Цезарь Кампеану; Кай Саломаа и Шэн Ю (декабрь 2003 г.). «Формальное исследование практических регулярных выражений». Международный журнал основ компьютерных наук . 14 (6): 1007–1018. дои : 10.1142/S012905410300214X. Архивировано из оригинала 4 июля 2015 г. Проверено 3 июля 2015 г.Теорема 3 (п.9)
39. «Сопоставление регулярных выражений Perl является NP-сложным» . perl.plover.com . Архивировано из оригинала 07.10.2020 . Проверено 21 ноября 2019 г.
40. Ричи, DM; Томпсон, КЛ (июнь 1970 г.). Текстовый редактор QED (PDF) . ММ-70-1373-3. Архивировано из оригинала (PDF) 3 февраля 2015 г. Проверено 05 сентября 2022 г.Перепечатано как «Справочное руководство по текстовому редактору QED», MHCC-004, Murray Hill Computing, Bell Laboratories (октябрь 1972 г.).
41. Уолл, Ларри (18 октября 1994 г.). «Perl 5: perlre.pod». Гитхаб .
42. Блуждающая логика. «Как моделировать просмотр вперед и назад в автоматах с конечным состоянием?». Обмен стеками в области компьютерных наук . Архивировано из оригинала 7 октября 2020 года . Проверено 24 ноября 2019 г.
43. Захаревич, Илья (19 ноября 1997). «Применено большое исправление регулярных выражений (с небольшими исправлениями): Perl/perl5@c277df4». Гитхаб .
44. Кокс (2007)
45. Лаурикари (2009)
46. "gnulib/lib/dfa.c". Архивировано из оригинала 18 августа 2021 г. Проверено 12 февраля 2022 г. Если сканер обнаруживает переход по обратной ссылке, он возвращает своего рода «полууспех», указывающий, что совпадение необходимо проверить с помощью средства сопоставления с обратным отслеживанием.
47. Кернс, Стивен (август 2013 г.). «Сублинейное сопоставление с конечными автоматами с использованием обратного суффиксного сканирования». arXiv : 1308.3822 [cs.DS].
48. Наварро, Гонсало (10 ноября 2001 г.). «NR-grep: быстрый и гибкий инструмент сопоставления с образцом» (PDF) . Программное обеспечение: практика и опыт . 31 (13): 1265–1312. дои : 10.1002/сп.411. S2CID  3175806. Архивировано (PDF) из оригинала 7 октября 2020 г. . Проверено 21 ноября 2019 г.
49. "travisdowns/polyregex". Гитхаб . 5 июля 2019 года. Архивировано из оригинала 14 сентября 2020 года . Проверено 21 ноября 2019 г.
50. Шмид, Маркус Л. (март 2019 г.). «Регулярные выражения с обратными ссылками: методы сопоставления за полиномиальное время». arXiv : 1903.05896 [cs.FL].
51. «Документация Vim: шаблон» . Vimdoc.sourceforge.net. Архивировано из оригинала 07.10.2020 . Проверено 25 сентября 2013 г.
52. «UTS # 18 о регулярных выражениях Юникода, Приложение A: Блоки символов» . Архивировано из оригинала 07.10.2020 . Проверено 5 февраля 2010 г.
53. «regex(3) — страница руководства Linux» . man7.org . Проверено 27 апреля 2022 г.
54. «Библиотека регулярных выражений — cppreference.com» . ru.cppreference.com . Проверено 27 апреля 2022 г.
55. «Шаблон (платформа Java SE 7)» . docs.oracle.com . Проверено 27 апреля 2022 г.
56. «Регулярные выражения — JavaScript». МДН . Проверено 27 апреля 2022 г.
57. "Библиотека OCaml: Str" . v2.ocaml.org . Проверено 21 августа 2022 г.
58. _ perldoc.perl.org . Проверено 4 февраля 2023 г.
59. «PHP: PCRE — Руководство» . www.php.net . Проверено 4 февраля 2023 г.
60. «re – Операции с регулярными выражениями» . docs.python.org . Проверено 24 февраля 2023 г.
61. "Регулярное выражение на crates.io" . Crates.io . Архивировано из оригинала 29 ноября 2022 г. Проверено 24 февраля 2023 г.
62. Горовиц, Брэдли (24 октября 2011 г.). «Осенняя зачистка». Гугл-блог . Архивировано из оригинала 21 октября 2018 года . Проверено 4 мая 2019 г.
63. Символ «m» не всегда требуется для указания операции сопоставления Perl . Например, m/[^abc]/также может быть отображено как /[^abc]/. Символ «m» необходим только в том случае, если пользователь желает указать операцию сопоставления без использования косой черты в качестве разделителя регулярного выражения . Иногда полезно указать альтернативный разделитель регулярных выражений, чтобы избежать « столкновения разделителей ». Для получения более подробной информации см. «perldoc perlre. Архивировано 31 декабря 2009 г. на Wayback Machine ».
64. Например, см. Java в двух словах , стр. 213; Сценарии Python для вычислительной науки , стр. 320; Программирование PHP , с. 106.
65. Все операторы if возвращают значение TRUE.
66. Конвей, Дамиан (2005). «Регулярные выражения, конец строки». Лучшие практики Perl . О'Рейли . п. 240. ИСБН 978-0-596-00173-5. Архивировано из оригинала 07.10.2020 . Проверено 10 сентября 2017 г.

Рекомендации

• Ахо, Альфред В. (1990). «Алгоритмы поиска закономерностей в строках». Ин ван Леувен, Ян (ред.). Справочник по теоретической информатике, том A: Алгоритмы и сложность . Массачусетский технологический институт Пресс. стр. 255–300.
• Ахо, Альфред В.; Уллман, Джеффри Д. (1992). «Глава 10. Шаблоны, автоматы и регулярные выражения» (PDF) . Основы информатики. Архивировано из оригинала 07.10.2020 . Проверено 14 декабря 2013 г.
• Эйкок, Джон (июнь 2003 г.). «Краткая история системы «точно в срок»» (PDF) . Обзоры вычислительной техники ACM . 35 (2): 97–113. CiteSeerX  10.1.1.97.3985 . дои : 10.1145/857076.857077. S2CID  15345671.
• "Обычные выражения". Единая спецификация UNIX, версия 2. Открытая группа. 1997. Архивировано из оригинала 07 октября 2020 г. Проверено 13 декабря 2011 г.
• «Глава 9: Регулярные выражения». Базовые характеристики открытой группы . Открытая группа (6). 2004. IEEE Std 1003.1, издание 2004 г. Архивировано из оригинала 2 декабря 2011 г. Проверено 13 декабря 2011 г.
• Кокс, Расс (2007). «Сопоставление регулярных выражений может быть простым и быстрым». Архивировано из оригинала 1 января 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. arXiv : 0802.2869 . Архивировано из оригинала 18 июля 2011 г. Проверено 15 июня 2009 г.
• Гойвертс, Ян; Левитан, Стивен (2009). Справочник по регулярным выражениям . [О'Рейли]. ISBN 978-0-596-52068-7.
• Грубер, Герман; Хольцер, Маркус (2008). Конечные автоматы, связность орграфов и размер регулярного выражения (PDF) . Материалы 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP 2008) . Конспекты лекций по информатике. Том. 5126. стр. 39–50. дои : 10.1007/978-3-540-70583-3_4. ISBN 978-3-540-70582-6. Архивировано (PDF) из оригинала 11 июля 2011 г. Проверено 3 февраля 2011 г.
• Хабиби, Мехран (2004). Реальные регулярные выражения с Java 1.4 . Спрингер. ISBN 978-1-59059-107-9.
• Хопкрофт, Джон Э.; Мотвани, Раджив; Уллман, Джеффри Д. (2000). Введение в теорию автоматов, языки и вычисления (2-е изд.). Аддисон-Уэсли.
• Джонсон, Уолтер Л.; Портер, Джеймс Х.; Экли, Стефани И.; Росс, Дуглас Т. (1968). «Автоматическое создание эффективных лексических процессоров с использованием методов конечных состояний». Коммуникации АКМ . 11 (12): 805–813. дои : 10.1145/364175.364185 . S2CID  17253809.
• Клини, Стивен К. (1951). «Представление событий в нервных сетях и конечных автоматах». В Шенноне, Клод Э.; Маккарти, Джон (ред.). Исследования автоматов (PDF) . Издательство Принстонского университета. стр. 3–42. Архивировано (PDF) из оригинала 07 октября 2020 г. Проверено 10 декабря 2017 г.
• Козен, Декстер (1991). «Теорема полноты для алгебр Клини и алгебры регулярных событий». [1991] Материалы шестого ежегодного симпозиума IEEE по логике в информатике . стр. 214–225. дои : 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: Обычные языки» . Введение в теорию вычислений . Издательство ПВС. стр. 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 г.

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

• СМИ, связанные с 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 Std 1003.1-2017, открытая группа