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

«Регулярное выражение» перенаправляется сюда. Чтобы узнать о комиксе, см. Re:Gex .

«.*» перенаправляется сюда. Информацию об операторе C++ см. в разделе Указатель (информатика) § Указатель на член .

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

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

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

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

История

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

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

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

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

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

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

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

Сегодня регулярные выражения широко поддерживаются в языках программирования, программах обработки текста (особенно лексерах ), продвинутых текстовых редакторах и некоторых других программах. Поддержка Regex является частью стандартной библиотеки многих языков программирования, включая Java и Python , и встроена в синтаксис других, включая Perl и ECMAScript . В конце 2010-х годов несколько компаний начали предлагать аппаратное обеспечение FPGA . графический процессор реализации 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. N(s*) полученное из регулярного выражения s*, где s , в свою очередь, обозначает более простое регулярное выражение, которое уже рекурсивно переведено в NFA N ( s ).

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

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

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

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

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

Группировка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• ( пустое множество ) ∅, обозначающее множество ∅.
• ( пустая строка ) ε обозначает набор, содержащий только «пустую» строку, в которой вообще нет символов.
• ( буквальный персонаж ) 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». , «ааа», ...}
• 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 . В принципе, оператор дополнения излишен, поскольку он не дает большей выразительной силы. Однако это может сделать регулярное выражение гораздо более кратким: исключение одного оператора дополнения может привести к двойному экспоненциальному увеличению его длины.

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

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

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

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

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

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

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

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

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

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

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

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

Синтаксис

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

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

Разделители

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

Стандарт IEEE POSIX

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

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

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

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

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

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

Примеры:

• .at соответствует любой трехсимвольной строке, заканчивающейся на «at», включая «hat», «cat», «bat», «4at», «#at» и «at» (начинающиеся с пробела).
• [hc]at соответствует «шляпе» и «коту».
• [^b]at соответствует всем строкам, соответствующим .at кроме «летучей мыши».
• [^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).

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

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

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

Примеры:

• [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] может обозначать любую заглавную букву английского алфавита и \d может означать любую цифру. Классы символов применимы к обоим уровням POSIX.

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

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

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

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

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

Перл и PCRE

См. также: Регулярные выражения, совместимые с Perl.

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

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

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

"Ganymede," he continued, "is the largest moon in the Solar System."

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

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

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

"Ganymede," he continued, "is the largest moon in the Solar System."

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

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

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

IETF I-Regexp

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

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

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

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

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

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

Утверждения

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

Другие функции, отсутствующие в описании обычных языков, включают утверждения. К ним относятся вездесущие ^ и $, используется как минимум с 1970 года, а также некоторые более сложные расширения, такие как Lookaround, появившиеся в 1994 году. Поисковые обходы определяют окружение совпадения и не затрагивают само совпадение, эта функция актуальна только для варианта использования строкового поиска. . Некоторые из них можно смоделировать на обычном языке, рассматривая окружающую среду как часть языка.

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

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

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

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

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

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

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

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

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

Юникод

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

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

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

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

• С
• С++
• С#
• Ява
• JavaScript
• OCaml
• Перл
• PHP
• Питон
• Ржавчина

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

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

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

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

Примеры

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

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

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

metacharacter(s) ;; the metacharacters column specifies the regex syntax being demonstrated
=~ m//           ;; indicates a regex match operation in Perl
=~ s///          ;; indicates a regex substitution operation in Perl

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

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

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

Метасимвол(ы)	Описание	Пример
.	Обычно соответствует любому символу, кроме символа новой строки. В квадратных скобках точка является буквальной.	$string1 = "Hello World\n"; if ($string1 =~ m/...../) { print "$string1 has length >= 5.\n"; } Выход: Hello World has length >= 5.
( )	Группирует серию элементов узора в один элемент. Когда вы сопоставляете шаблон в круглых скобках, вы можете использовать любой из $1, $2, ... позже, чтобы обратиться к ранее сопоставленному шаблону. В некоторых реализациях вместо этого может использоваться обратная косая черта, например \1, \2.	$string1 = "Hello World\n"; if ($string1 =~ m/(H..).(o..)/) { print "We matched '$1' and '$2'.\n"; } Выход: We matched 'Hel' and 'o W'.
+	Соответствует предыдущему элементу шаблона один или несколько раз.	$string1 = "Hello World\n"; if ($string1 =~ m/l+/) { print "There are one or more consecutive letter \"l\"'s in $string1.\n"; } Выход: There are one or more consecutive letter "l"'s in Hello World.
?	Соответствует предыдущему элементу шаблона ноль или один раз.	$string1 = "Hello World\n"; if ($string1 =~ m/H.?e/) { print "There is an 'H' and a 'e' separated by "; print "0-1 characters (e.g., He Hue Hee).\n"; } Выход: There is an 'H' and a 'e' separated by 0-1 characters (e.g., He Hue Hee).
?	Изменяет *, +, ? или {M,N}'' регулярное выражение, которое идет раньше, чтобы соответствовать как можно меньшему количеству раз.	$string1 = "Hello World\n"; if ($string1 =~ m/(l.+?o)/) { print "The non-greedy match with 'l' followed by one or "; print "more characters is 'llo' rather than 'llo Wo'.\n"; } Выход: The non-greedy match with 'l' followed by one or more characters is 'llo' rather than 'llo Wo'.
*	Соответствует предыдущему элементу шаблона ноль или более раз.	$string1 = "Hello World\n"; if ($string1 =~ m/el*o/) { print "There is an 'e' followed by zero to many "; print "'l' followed by 'o' (e.g., eo, elo, ello, elllo).\n"; } Выход: There is an 'e' followed by zero to many 'l' followed by 'o' (e.g., eo, elo, ello, elllo).
{M,N}	Обозначает минимальное количество совпадений M и максимальное N. N можно опустить, а M может быть 0: {M} соответствует «точно» M раз; {M,} соответствует «по крайней мере» M раз; {0,N} соответствует «не более» N раз. x* y+ z? таким образом, эквивалентно x{0,} y{1,} z{0,1}.	$string1 = "Hello World\n"; if ($string1 =~ m/l{1,2}/) { print "There exists a substring with at least 1 "; print "and at most 2 l's in $string1\n"; } Выход: There exists a substring with at least 1 and at most 2 l's in Hello World
[…]	Обозначает набор возможных совпадений символов.	$string1 = "Hello World\n"; if ($string1 =~ m/[aeiou]+/) { print "$string1 contains one or more vowels.\n"; } Выход: Hello World contains one or more vowels.
|	Разделяет альтернативные возможности.	$string1 = "Hello World\n"; if ($string1 =~ m/(Hello|Hi|Pogo)/) { print "$string1 contains at least one of Hello, Hi, or Pogo."; } Выход: Hello World contains at least one of Hello, Hi, or Pogo.
\b	Соответствует границе нулевой ширины между символом класса слова (см. далее) и символом класса, не относящимся к слову, или краем; то же, что (^\w|\w$|\W\w|\w\W).	$string1 = "Hello World\n"; if ($string1 =~ m/llo\b/) { print "There is a word that ends with 'llo'.\n"; } Выход: There is a word that ends with 'llo'.
\w	Соответствует буквенно-цифровому символу, включая «_»; то же, что [A-Za-z0-9_] в ASCII и [\p{Alphabetic}\p{GC=Mark}\p{GC=Decimal_Number}\p{GC=Connector_Punctuation}] в Юникоде, где Alphabetic свойство содержит больше латинских букв, а Decimal_Number свойство содержит более арабских цифр.	$string1 = "Hello World\n"; if ($string1 =~ m/\w/) { print "There is at least one alphanumeric "; print "character in $string1 (A-Z, a-z, 0-9, _).\n"; } Выход: There is at least one alphanumeric character in Hello World (A-Z, a-z, 0-9, _).
\W	Соответствует небуквенно -цифровому символу, за исключением "_"; то же, что [^A-Za-z0-9_] в ASCII и [^\p{Alphabetic}\p{GC=Mark}\p{GC=Decimal_Number}\p{GC=Connector_Punctuation}] в Юникод.	$string1 = "Hello World\n"; if ($string1 =~ m/\W/) { print "The space between Hello and "; print "World is not alphanumeric.\n"; } Выход: The space between Hello and World is not alphanumeric.
\s	Соответствует символу пробела, в ASCII это табуляция, перевод строки, перевод страницы, возврат каретки и пробел; в Юникоде также не соответствует пробелы, следующая строка и переменная- ширина пространства (среди прочего).	$string1 = "Hello World\n"; if ($string1 =~ m/\s.*\s/) { print "In $string1 there are TWO whitespace characters, which may"; print " be separated by other characters.\n"; } Выход: In Hello World there are TWO whitespace characters, which may be separated by other characters.
\S	Соответствует чему угодно, кроме пробела.	$string1 = "Hello World\n"; if ($string1 =~ m/\S.*\S/) { print "In $string1 there are TWO non-whitespace characters, which"; print " may be separated by other characters.\n"; } Выход: In Hello World there are TWO non-whitespace characters, which may be separated by other characters.
\d	Соответствует цифре; то же, что [0-9] в ASCII; в Юникоде, так же, как \p{Digit} или \p{GC=Decimal_Number} имущество, которое само по себе то же, что и \p{Numeric_Type=Decimal} свойство.	$string1 = "99 bottles of beer on the wall."; if ($string1 =~ m/(\d+)/) { print "$1 is the first number in '$string1'\n"; } Выход: 99 is the first number in '99 bottles of beer on the wall.'
\D	Соответствует нецифре; то же, что [^0-9] в ASCII или \P{Digit} в Юникод.	$string1 = "Hello World\n"; if ($string1 =~ m/\D/) { print "There is at least one character in $string1"; print " that is not a digit.\n"; } Выход: There is at least one character in Hello World that is not a digit.
^	Соответствует началу строки или строки.	$string1 = "Hello World\n"; if ($string1 =~ m/^He/) { print "$string1 starts with the characters 'He'.\n"; } Выход: Hello World starts with the characters 'He'.
$	Соответствует концу строки или строки.	$string1 = "Hello World\n"; if ($string1 =~ m/rld$/) { print "$string1 is a line or string "; print "that ends with 'rld'.\n"; } Выход: Hello World is a line or string that ends with 'rld'.
\A	Соответствует началу строки (но не внутренней строке).	$string1 = "Hello\nWorld\n"; if ($string1 =~ m/\AH/) { print "$string1 is a string "; print "that starts with 'H'.\n"; } Выход: Hello World is a string that starts with 'H'.
\z	Соответствует концу строки (но не внутренней строке).	$string1 = "Hello\nWorld\n"; if ($string1 =~ m/d\n\z/) { print "$string1 is a string "; print "that ends with 'd\\n'.\n"; } Выход: Hello World is a string that ends with 'd\n'.
[^…]	Соответствует каждому символу, кроме тех, которые находятся внутри скобок.	$string1 = "Hello World\n"; if ($string1 =~ m/[^abc]/) { print "$string1 contains a character other than "; print "a, b, and c.\n"; } Выход: Hello World contains a character other than a, b, and c.

Индукция

Основная статья: Индукция регулярных языков

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

См. также

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

Ссылки

• Ахо, Альфред В. (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, открытая группа