Регулярные выражения: история и применение

Введение

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

Регулярное выражение (сокращенно regex или regexp), иногда называемое рациональным выражением, — это последовательность символов, задающая шаблон для сопоставления с текстом. Обычно такие шаблоны используются алгоритмами поиска строк для операций "найти" или "найти и заменить" в строках, а также для проверки входных данных. Методы регулярных выражений разработаны в теоретической информатике и теории формальных языков. Концепция регулярных выражений возникла в 1950-х годах, когда американский математик Стивен Коул Клин формализовал понятие регулярного языка. Они получили широкое распространение с появлением утилит обработки текста Unix. С 1980-х годов существует несколько синтаксисов для записи регулярных выражений, включая стандарт POSIX и широко используемый синтаксис Perl. Регулярные выражения применяются в поисковых системах, в диалоговых окнах поиска и замены текстовых процессоров и текстовых редакторов, в утилитах обработки текста, таких как sed и AWK, и в лексическом анализе. Регулярные выражения поддерживаются многими языками программирования. Библиотечные реализации часто называют "механизмом", и многие из них доступны для повторного использования.

История

Регулярные выражения возникли в 1951 году, когда математик Стивен Коул Клин описал регулярные языки, используя свою математическую нотацию, называемую регулярными событиями. Они возникли в теоретической информатике, в подразделах теории автоматов (моделей вычислений) и описания и классификации формальных языков. Другие ранние реализации сопоставления с образцом включают язык SNOBOL, который не использовал регулярные выражения, а вместо этого – собственные конструкции сопоставления с образцом. Регулярные выражения получили широкое распространение с 1968 года в двух областях применения: сопоставление с образцом в текстовом редакторе и лексический анализ в компиляторе. Одним из первых примеров использования регулярных выражений в программном обеспечении стало встраивание нотации Клина Кеном Томпсоном в редактор QED для сопоставления с образцом в текстовых файлах. Для повышения скорости Томпсон реализовал сопоставление регулярных выражений с помощью JIT-компиляции (компиляции «на лету») в код IBM 7094 на системе совместного использования времени Compatible Time Sharing System, что стало важным ранним примером JIT-компиляции. Позже он добавил эту возможность в редактор Unix ed, что в конечном итоге привело к использованию регулярных выражений популярным инструментом поиска grep («grep» происходит от команды для поиска регулярных выражений в редакторе ed: g/re/p, означающей «Глобальный поиск по регулярному выражению и печать соответствующих строк»). Примерно в то же время, когда Томпсон разрабатывал QED, группа исследователей, включая Дугласа Т. Росса, реализовала инструмент на основе регулярных выражений, используемый для лексического анализа при разработке компиляторов. Многие вариации этих оригинальных форм регулярных выражений использовались в Unix-программах в Bell Labs в 1970-х годах, включая vi, lex, sed, AWK и expr, а также в других программах, таких как Emacs (который имеет свой собственный, несовместимый синтаксис и поведение). Впоследствии регулярные выражения были приняты широким кругом программ, а эти ранние формы были стандартизированы в стандарте POSIX.2 в 1992 году. В 1980-х годах в Perl появились более сложные регулярные выражения, которые изначально были основаны на библиотеке регулярных выражений, написанной Генри Спенсером (1986), который позже написал реализацию для Tcl под названием Advanced Regular Expressions. Библиотека Tcl представляет собой гибридную реализацию NFA/DFA с улучшенными характеристиками производительности. Проекты, которые приняли реализацию регулярных выражений Tcl Спенсера, включают PostgreSQL. Позже Perl расширил оригинальную библиотеку Спенсера, добавив множество новых функций. Часть работы по разработке Raku (ранее известного как Perl 6) направлена на улучшение интеграции регулярных выражений Perl и расширение их возможностей, чтобы обеспечить определение грамматик выражений для разбора. Результатом стал мини-язык под названием Raku rules, который используется для определения грамматики Raku, а также предоставляет инструмент для программистов на этом языке. Эти правила поддерживают существующие функции регулярных выражений Perl 5.x, но также позволяют определять рекурсивный нисходящий парсер в стиле BNF с помощью подправил. Использование регулярных выражений в структурированных стандартах информации для моделирования документов и баз данных началось в 1960-х годах и расширилось в 1980-х годах, когда были консолидированы отраслевые стандарты, такие как ISO SGML (предшественник ANSI "GCA 101 1983"). Ядро стандартов языка спецификации структуры состоит из регулярных выражений. Это проявляется в синтаксисе группы элементов DTD. До использования регулярных выражений многие языки поиска допускали простые подстановочные знаки, например "*" для соответствия любой последовательности символов и "?" для соответствия одному символу. Следы этого можно найти сегодня в синтаксисе glob для имен файлов и в операторе SQL LIKE. Начиная с 1997 года, Филипп Хейзел разработал PCRE (Perl Compatible Regular Expressions), который стремится точно имитировать функциональность регулярных выражений Perl и используется многими современными инструментами, включая PHP и Apache HTTP Server. Сегодня регулярные выражения широко поддерживаются в языках программирования, программах обработки текста (особенно в лексерах), продвинутых текстовых редакторах и некоторых других программах. Поддержка регулярных выражений является частью стандартной библиотеки многих языков программирования, включая Java и Python, и встроена в синтаксис других, включая Perl и ECMAScript. В конце 2010-х годов несколько компаний начали предлагать аппаратные, FPGA и GPU реализации движков регулярных выражений, совместимых с PCRE, которые быстрее, чем реализации для ЦП.

Regular expressions originated in 1951, when mathematician Stephen Cole Kleene described regular languages using his mathematical notation called regular events. These arose in theoretical computer science, in the subfields of automata theory (models of computation) and the description and classification of formal languages. Other early implementations of pattern matching include the SNOBOL language, which did not use regular expressions, but instead its own pattern matching constructs. Regular expressions entered popular use from 1968 in two uses: pattern matching in a text editor and lexical analysis in a compiler. Among the first appearances of regular expressions in program form was when Ken Thompson built Kleene's notation into the editor QED as a means to match patterns in text files. For speed, Thompson implemented regular expression matching by just in time compilation (JIT) to IBM 7094 code on the Compatible Time Sharing System, an important early example of JIT compilation. He later added this capability to the Unix editor ed, which eventually led to the popular search tool grep's use of regular expressions ("grep" is a word derived from the command for regular expression searching in the ed editor: g/re/p meaning "Global search for Regular Expression and Print matching lines"). Around the same time when Thompson developed QED, a group of researchers including Douglas T. Ross implemented a tool based on regular expressions that is used for lexical analysis in compiler design. Many variations of these original forms of regular expressions were used in Unix programs at Bell Labs in the 1970s, including vi, lex, sed, AWK, and expr, and in other programs such as Emacs (which has its own, incompatible syntax and behavior). Regexes were subsequently adopted by a wide range of programs, with these early forms standardized in the POSIX.2 standard in 1992. In the 1980s, the more complicated regexes arose in Perl, which originally derived from a regex library written by Henry Spencer (1986), who later wrote an implementation for Tcl called Advanced Regular Expressions. The Tcl library is a hybrid NFA/DFA implementation with improved performance characteristics. Software projects that have adopted Spencer's Tcl regular expression implementation include PostgreSQL. Perl later expanded on Spencer's original library to add many new features. Part of the effort in the design of Raku (formerly named Perl 6) is to improve Perl's regex integration, and to increase their scope and capabilities to allow the definition of parsing expression grammars. The result is a mini language called Raku rules, which are used to define Raku grammar as well as provide a tool to programmers in the language. These rules maintain existing features of Perl 5. x regexes, but also allow BNF style definition of a recursive descent parser via sub rules. The use of regexes in structured information standards for document and database modeling started in the 1960s and expanded in the 1980s when industry standards like ISO SGML (precursored by ANSI "GCA 101 1983") consolidated. The kernel of the structure specification language standards consists of regexes. Its use is evident in the DTD element group syntax. Prior to the use of regular expressions, many search languages allowed simple wildcards, for example "*" to match any sequence of characters, and "?" to match a single character. Relics of this can be found today in the glob syntax for filenames, and in the SQL LIKE operator. Starting in 1997, Philip Hazel developed PCRE (Perl Compatible Regular Expressions), which attempts to closely mimic Perl's regex functionality and is used by many modern tools including PHP and Apache HTTP Server. Today, regexes are widely supported in programming languages, text processing programs (particularly lexers), advanced text editors, and some other programs. Regex support is part of the standard library of many programming languages, including Java and Python, and is built into the syntax of others, including Perl and ECMAScript. In the late 2010s, several companies started to offer hardware, FPGA, GPU implementations of PCRE compatible regex engines that are faster compared to CPU implementations.

Образцы

Фраза «регулярные выражения», или «регексы», часто используется для обозначения конкретного, стандартного текстового синтаксиса для представления шаблонов для сопоставления текста, в отличие от математической нотации, описанной ниже. Каждый символ в регулярном выражении (то есть каждый символ в строке, описывающей его шаблон) является либо метасимволом, имеющим специальное значение, либо обычным символом, имеющим буквальное значение. Например, в регексе `b.`, символ `b` — это буквальный символ, который соответствует только `b`, в то время как `.` — это метасимвол, который соответствует любому символу, кроме символа новой строки. Поэтому этот регекс совпадает, например, с `b%`, или `bx`, или `b5`. Вместе метасимволы и буквальные символы могут использоваться для идентификации текста заданного шаблона или обработки нескольких его экземпляров. Сопоставления шаблонов могут варьироваться от точного равенства до очень общего сходства, контролируемого метасимволами. Например, `[a-z]` (соответствует всем строчным буквам от «a» до «z») является очень общим шаблоном, а `b` — точным шаблоном (соответствует только `b`). Синтаксис метасимволов разработан специально для представления заданных целей в краткой и гибкой форме для направления автоматизации обработки текста различных входных данных в форме, которую легко набрать с помощью стандартной клавиатуры ASCII. Очень простым примером регулярного выражения в этом синтаксисе является поиск слова, написанного двумя разными способами в текстовом редакторе: регулярное выражение `seriali[sz]e` соответствует как `serialise`, так и `serialize`. Символы подстановки (wildcard characters) также позволяют этого достичь, но они более ограничены в том, какие шаблоны они могут задавать, поскольку у них меньше метасимволов и более простая языковая база. Обычно символы подстановки используются для объединения похожих имен в списке файлов, в то время как регексы обычно применяются в приложениях, которые в целом сопоставляют текстовые строки по шаблону. Например, регекс `^[ \t]+|[ \t]+$` соответствует избыточным пробелам в начале или конце строки. Продвинутое регулярное выражение, которое соответствует любому числу, выглядит так: `[+\-]?(\d+(\.\d*)?|\.\d+)([eE][+\-]?\d+)?`. Процессор регексов преобразует регулярное выражение в указанном синтаксисе во внутреннее представление, которое может быть выполнено и сопоставлено со строкой, представляющей текст, в котором выполняется поиск. Один из возможных подходов — алгоритм построения Томпсона для создания недетерминированного конечного автомата (NFA), который затем детерминируется, и полученный детерминированный конечный автомат (DFA) запускается на целевой текстовой строке для распознавания подстрок, соответствующих регулярному выражению. На рисунке показана схема NFA `N(s*)`, полученная из регулярного выражения `s*`, где `s` обозначает более простое регулярное выражение, которое уже рекурсивно преобразовано в NFA `N(s)`.

The phrase regular expressions, or regexes, is often used to mean the specific, standard textual syntax for representing patterns for matching text, as distinct from the mathematical notation described below. Each character in a regular expression (that is, each character in the string describing its pattern) is either a metacharacter, having a special meaning, or a regular character that has a literal meaning. For example, in the regex b., 'b' is a literal character that matches just 'b', while '.' is a metacharacter that matches every character except a newline. Therefore, this regex matches, for example, 'b%', or 'bx', or 'b5'. Together, metacharacters and literal characters can be used to identify text of a given pattern or process a number of instances of it. Pattern matches may vary from a precise equality to a very general similarity, as controlled by the metacharacters. For example, is a very general pattern, [a z] (match all lower case letters from 'a' to 'z') is less general and b is a precise pattern (matches just 'b'). The metacharacter syntax is designed specifically to represent prescribed targets in a concise and flexible way to direct the automation of text processing of a variety of input data, in a form easy to type using a standard ASCII keyboard. A very simple case of a regular expression in this syntax is to locate a word spelled two different ways in a text editor, the regular expression seriali[sz]e matches both "serialise" and "serialize". Wildcard characters also achieve this, but are more limited in what they can pattern, as they have fewer metacharacters and a simple language base. The usual context of wildcard characters is in globbing similar names in a list of files, whereas regexes are usually employed in applications that pattern match text strings in general. For example, the regex ^[ \t]+|[ \t]+$ matches excess whitespace at the beginning or end of a line. An advanced regular expression that matches any numeral is [+ ]? (\d+(\.\d*)?|\.\d+)([eE][+ ]?\d+)?. A regex processor translates a regular expression in the above syntax into an internal representation that can be executed and matched against a string representing the text being searched in. One possible approach is the Thompson's construction algorithm to construct a nondeterministic finite automaton (NFA), which is then made deterministic and the resulting deterministic finite automaton (DFA) is run on the target text string to recognize substrings that match the regular expression. The picture shows the NFA scheme N(s*) obtained from the regular expression s*, where s denotes a simpler regular expression in turn, which has already been recursively translated to the NFA N(s).

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

Как видно из многих примеров выше, существует более одного способа построения регулярного выражения для достижения одинаковых результатов. Можно разработать алгоритм, который для двух заданных регулярных выражений определяет, описывают ли они равные языки; алгоритм сводит каждое выражение к минимальному детерминированному конечному автомату и определяет, изоморфны ли они (эквивалентны). Алгебраические законы для регулярных выражений можно получить методом Гишера, который лучше всего объяснить на примере: чтобы проверить, обозначают ли выражения (X+Y)* и (X* Y*)* один и тот же регулярный язык для всех регулярных выражений X и Y, необходимо и достаточно проверить, обозначают ли конкретные выражения (a+b)* и (a* b*)* один и тот же язык над алфавитом Σ={a,b}. В более общем случае, уравнение E=F между термами регулярных выражений с переменными выполняется тогда и только тогда, когда его конкретизация с различными переменными, замененными различными символьными константами, выполняется. Каждое регулярное выражение можно представить исключительно с использованием звезды Клине и операций объединения над конечными строками. Это на удивление сложная задача. Несмотря на кажущуюся простоту регулярных выражений, не существует метода их систематического приведения к нормальной форме. Отсутствие аксиоматизации в прошлом привело к проблеме высоты звезды. В 1991 году Декстер Козен аксиоматизировал регулярные выражения как алгебру Клине, используя аксиомы равенств и предложения Хорна. Уже в 1964 году Редко доказал, что никакое конечное множество чисто уравнительных аксиом не может характеризовать алгебру регулярных языков.

Синтаксис

Регулярное выражение сопоставляется с целевой строкой. Шаблон состоит из последовательности атомов. Атом – это единственная точка в регулярном выражении, которую оно пытается сопоставить с целевой строкой. Самый простой атом – литерал, но для группировки частей шаблона с целью сопоставления с атомом потребуется использование ( ) в качестве метасимволов. Метасимволы помогают формировать: атомы; квантификаторы, указывающие количество атомов (и является ли квантификатор жадным или нет); логический оператор ИЛИ, предлагающий набор альтернатив, и логический оператор НЕ, отрицающий существование атома; а также обратные ссылки для обращения к предыдущим атомам завершенного шаблона атомов. Сопоставление происходит не тогда, когда сопоставлены все атомы строки, а когда сопоставлены все атомы шаблона в регулярном выражении. Идея заключается в том, чтобы небольшой шаблон символов представлял большое количество возможных строк, а не компилировать большой список всех литеральных возможностей. В зависимости от процессора регулярных выражений существует около четырнадцати метасимволов, которые могут иметь или не иметь буквальное значение в зависимости от контекста или если они "экранированы", то есть им предшествует управляющая последовательность, в данном случае, обратная косая черта \. Современные и расширенные регулярные выражения POSIX чаще используют метасимволы, чем их буквальное значение, поэтому, чтобы избежать "перегрузки обратными косыми чертами" или "синдрома наклоненной зубочистки", они имеют механизм экранирования метасимволов для перевода их в буквальный режим; однако изначально четыре метасимвола в скобках ( ) и { } в основном являются литералами и "экранируются" от этого обычного значения, чтобы стать метасимволами. Распространенные стандарты реализуют оба подхода. Обычные метасимволы: {}[] ^$.|*+? и \. Обычные символы, которые становятся метасимволами при экранировании: dswDSW и N.

Ограничители

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

Стандарт IEEE POSIX

Стандарт IEEE POSIX имеет три набора соответствия: BRE (базовые регулярные выражения), ERE (расширенные регулярные выражения) и SRE (простые регулярные выражения). SRE устарел в пользу 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, ( ) и { } рассматриваются как метасимволы, если они не экранированы; другие метасимволы воспринимаются как литералы или символы исключительно на основе контекста. Дополнительные возможности включают ленивое сопоставление, обратные ссылки, именованные группы захвата и рекурсивные шаблоны.

Классы символов

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

Описание | POSIX | Perl/Tcl | Vim | Java | ASCII
------- | -------- | -------- | -------- | -------- | --------
ASCII символы | `\p{ASCII}` | `[\x00-\x7F]` | | | `[\x00-\x7F]`
Алфавитно-цифровые символы | `[:alnum:]` | `\p{Alnum}` | `[A-Za-z0-9]` | | `[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]` | | `[\x00-\x1F\x7F]`
Цифры | `[:digit:]` | `\d` | `\d` | `\p{Digit}` или `\d` | `[0-9]`
Не цифры | `\D` | `\D` | `\D` | | `[^0-9]`
Видимые символы | `[:graph:]` | `\p{Graph}` | `[\x21-\x7E]` | | `[\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 называет скобочными выражениями.

Perl и PCRE

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

Ленивый совпадение

В Python и некоторых других реализациях (например, Java), три общих квантификатора (*, + и ?) по умолчанию являются жадными, поскольку они сопоставляют как можно больше символов. Регулярное выражение ".+" (включая двойные кавычки), примененное к строке "Ганимед", – продолжил он, – "является самой большой луной в Солнечной системе", сопоставляет всю строку (потому что вся строка начинается и заканчивается двойной кавычкой), а не только первую часть, "Ганимед". Однако вышеупомянутые квантификаторы могут быть сделаны ленивыми, минимальными или нехотливыми, сопоставляя как можно меньше символов, путем добавления вопросительного знака: ".+?" сопоставляет только "Ганимед". Квантификаторы могут быть сделаны притяжательными, добавляя знак плюс, который отключает возврат (в движке обратного отслеживания), даже если это позволит общему совпадению завершиться успешно: в то время как регулярное выражение ". *" при применении к строке "Ганимед", – продолжил он, – "является самой большой луной в Солнечной системе" сопоставляет всю строку, регулярное выражение ". *+" не сопоставляет ничего, поскольку . *+ поглощает весь ввод, включая конечную точку. Таким образом, притяжательные квантификаторы наиболее полезны с отрицательными классами символов, например, "[^"]*+", который сопоставляет "Ганимед" при применении к той же строке. Другим распространенным расширением, выполняющим ту же функцию, является атомарная группировка, которая отключает обратное отслеживание для группы в скобках. Типичный синтаксис: например, while сопоставляет как , так и , то сопоставляет только , поскольку движку запрещено возвращаться назад и, следовательно, он не может попытаться установить группу на "w" после сопоставления "wi". Притяжательные квантификаторы легче реализовать, чем жадные и ленивые квантификаторы, и обычно более эффективны во время выполнения.

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

Многие функции, присутствующие практически во всех современных библиотеках регулярных выражений, обеспечивают выразительную силу, превосходящую возможности регулярных языков. Например, многие реализации позволяют группировать подвыражения с помощью скобок и ссылаться на значение, которое они сопоставили, в том же выражении (обратные ссылки). Это означает, что, в частности, шаблон может сопоставлять строки, состоящие из повторяющихся слов, такие как "папа" или "WikiWiki", которые в теории формальных языков называются квадратами. Шаблон для таких строк — `(.+)\1`. Язык квадратов не является регулярным и не является контекстно-свободным из-за леммы о выкачивании. Однако сопоставление с образцом с неограниченным количеством обратных ссылок, поддерживаемое многими современными инструментами, все еще является контекстно-зависимым. Общая задача сопоставления любого количества обратных ссылок является NP-полной, а время выполнения известных алгоритмов экспоненциально возрастает с увеличением числа используемых групп обратных ссылок. Тем не менее, многие инструменты, библиотеки и движки, предоставляющие такие конструкции, по-прежнему используют термин «регулярное выражение» для обозначения своих шаблонов. Это привело к тому, что термин «регулярное выражение» имеет разные значения в теории формальных языков и в сопоставлении с образцом. По этой причине некоторые люди стали использовать термины «regex», «regexp» или просто «шаблон» для обозначения последнего. Ларри Уолл, автор языка программирования Perl, пишет в эссе о дизайне Raku:

«Регулярные выражения» [ ] лишь косвенно связаны с настоящими регулярными выражениями. Тем не менее, этот термин расширился вместе с возможностями наших механизмов сопоставления с образцом, поэтому я не буду пытаться бороться с языковой необходимостью. Однако я обычно называю их «регексами» (или «регексенами», когда я в англосаксонском настроении), а также некоторые более сложные расширения, такие как lookaround, появившиеся в 1994 году. Lookaround определяет окружение совпадения и не включается в само совпадение — функция, актуальная только для поиска строк. Некоторые из них можно имитировать в регулярном языке, рассматривая окружение как часть языка. Конструкции `(?= )` и `(?! )` известны, по крайней мере, с 1994 года, начиная с Perl 5. Lookbehind assertions `(?<= )` и `(?<! )` появились в 1997 году в коммите Ильи Захаревича для Perl 5.005.

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

Существует по крайней мере три различных алгоритма, определяющих, соответствует ли данный регулярное выражение строке и каким образом. Самый старый и быстрый основан на результате из теории формальных языков, позволяющем преобразовать любой недетерминированный конечный автомат (NFA) в детерминированный конечный автомат (DFA). DFA может быть построен явно, а затем запущен на входной строке по одному символу за раз. Построение DFA для регулярного выражения размера m требует времени и памяти O(2m), но его выполнение на строке размера n занимает время O(n). Следует отметить, что размер выражения – это размер после раскрытия сокращений, таких как численные квантификаторы. Альтернативный подход заключается в непосредственной симуляции NFA, по сути, создании каждого состояния DFA по требованию и последующем его отбрасывании на следующем шаге. Это позволяет сохранить DFA неявным и избежать экспоненциальных затрат на построение, однако стоимость выполнения возрастает до O(mn). Явный подход называется алгоритмом DFA, а неявный – алгоритмом NFA. Добавление кэширования к алгоритму NFA часто называют алгоритмом "ленивого DFA" или просто алгоритмом DFA без проведения различий. Эти алгоритмы быстры, но их использование для восстановления сгруппированных подвыражений, ленивой квантификации и подобных возможностей является сложной задачей. Современные реализации включают семейства re1, re2 и sregex, основанные на коде Кокса. Третий алгоритм заключается в сопоставлении шаблона с входной строкой посредством обратного отслеживания. Этот алгоритм обычно называют NFA, но такая терминология может быть вводящей в заблуждение. Его время выполнения может быть экспоненциальным, что демонстрируют простые реализации при сопоставлении с выражениями, содержащими как альтернацию, так и неограниченную квантификацию, заставляя алгоритм рассматривать экспоненциально возрастающее число подслучаев. Такое поведение может привести к проблеме безопасности, известной как отказ в обслуживании из-за регулярного выражения (ReDoS). Хотя реализации с обратным отслеживанием гарантируют только экспоненциальное время выполнения в худшем случае, они обеспечивают гораздо большую гибкость и выразительность. Например, любая реализация, позволяющая использовать обратные ссылки или реализующая различные расширения, представленные в Perl, должна включать в себя ту или иную форму обратного отслеживания. Некоторые реализации пытаются объединить лучшее из обоих алгоритмов, сначала запуская быстрый алгоритм DFA и переключаясь на потенциально более медленный алгоритм обратного отслеживания только при обнаружении обратной ссылки во время сопоставления. GNU grep (и лежащий в его основе gnulib DFA) использует такую стратегию. Достижение сублинейного времени выполнения стало возможным благодаря алгоритмам, основанным на Boyer-Moore (BM), и связанным с ними методам оптимизации DFA, таким как обратное сканирование. GNU grep, поддерживающий широкий спектр синтаксисов и расширений POSIX, использует BM для предварительной фильтрации на первом проходе, а затем использует неявный DFA. Wu agrep, реализующий приблизительное сопоставление, объединяет предварительную фильтрацию в DFA в BDM (backward DAWG matching). BNDM в NR grep расширяет технику BDM с использованием побитового параллелизма сдвига или побитовых операций. Существуют несколько теоретических альтернатив обратному отслеживанию для обратных ссылок, и их "экспоненты" более управляемы, поскольку они связаны только с количеством обратных ссылок – фиксированным свойством некоторых языков регулярных выражений, таких как POSIX. Один наивный метод, дублирующий NFA без обратного отслеживания для каждой обратной ссылки, имеет сложность O(n^{2k+2}) по времени и O(n^{2k+1}) по памяти для строки длиной n и k обратных ссылок в регулярном выражении. Недавняя теоретическая работа, основанная на автоматах памяти, дает более точную границу, основанную на используемых "активных" переменных узлах, и полиномиальную возможность для некоторых регулярных выражений с обратными ссылками.

There are at least three different algorithms that decide whether and how a given regex matches a string. The oldest and fastest relies on a result in formal language theory that allows every nondeterministic finite automaton (NFA) to be transformed into a deterministic finite automaton (DFA). The DFA can be constructed explicitly and then run on the resulting input string one symbol at a time. Constructing the DFA for a regular expression of size m has the time and memory cost of O(2m), but it can be run on a string of size n in time O(n). Note that the size of the expression is the size after abbreviations, such as numeric quantifiers, have been expanded. An alternative approach is to simulate the NFA directly, essentially building each DFA state on demand and then discarding it at the next step. This keeps the DFA implicit and avoids the exponential construction cost, but running cost rises to O(mn). The explicit approach is called the DFA algorithm and the implicit approach the NFA algorithm. Adding caching to the NFA algorithm is often called the "lazy DFA" algorithm, or just the DFA algorithm without making a distinction. These algorithms are fast, but using them for recalling grouped subexpressions, lazy quantification, and similar features is tricky. Modern implementations include the re1 re2 sregex family based on Cox's code. The third algorithm is to match the pattern against the input string by backtracking. This algorithm is commonly called NFA, but this terminology can be confusing. Its running time can be exponential, which simple implementations exhibit when matching against expressions like that contain both alternation and unbounded quantification and force the algorithm to consider an exponentially increasing number of sub cases. This behavior can cause a security problem called Regular expression Denial of Service (ReDoS). Although backtracking implementations only give an exponential guarantee in the worst case, they provide much greater flexibility and expressive power. For example, any implementation which allows the use of backreferences, or implements the various extensions introduced by Perl, must include some kind of backtracking. Some implementations try to provide the best of both algorithms by first running a fast DFA algorithm, and revert to a potentially slower backtracking algorithm only when a backreference is encountered during the match. GNU grep (and the underlying gnulib DFA) uses such a strategy. Sublinear runtime algorithms have been achieved using Boyer Moore (BM) based algorithms and related DFA optimization techniques such as the reverse scan. GNU grep, which supports a wide variety of POSIX syntaxes and extensions, uses BM for a first pass prefiltering, and then uses an implicit DFA. Wu agrep, which implements approximate matching, combines the prefiltering into the DFA in BDM (backward DAWG matching). NR grep's BNDM extends the BDM technique with Shift Or bit level parallelism. A few theoretical alternatives to backtracking for backreferences exist, and their "exponents" are tamer in that they are only related to the number of backreferences, a fixed property of some regexp languages such as POSIX. One naive method that duplicates a non backtracking NFA for each backreference note has a complexity of {\mathrm O}(n^{2k+2}) time and {\mathrm O}(n^{2k+1}) space for a haystack of length n and k backreferences in the RegExp. A very recent theoretical work based on memory automata gives a tighter bound based on "active" variable nodes used, and a polynomial possibility for some backreferenced regexps.

Юникод

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

In theoretical terms, any token set can be matched by regular expressions as long as it is pre defined. In terms of historical implementations, regexes were originally written to use ASCII characters as their token set though regex libraries have supported numerous other character sets. Many modern regex engines offer at least some support for Unicode. In most respects it makes no difference what the character set is, but some issues do arise when extending regexes to support Unicode. Supported encoding. Some regex libraries expect to work on some particular encoding instead of on abstract Unicode characters. Many of these require the UTF 8 encoding, while others might expect UTF 16, or UTF 32. In contrast, Perl and Java are agnostic on encodings, instead operating on decoded characters internally. Supported Unicode range. Many regex engines support only the Basic Multilingual Plane, that is, the characters which can be encoded with only 16 bits. Currently (as of as of 2016) only a few regex engines (e. g., Perl's and Java's) can handle the full 21 bit Unicode range. Extending ASCII oriented constructs to Unicode. For example, in ASCII based implementations, character ranges of the form [x y] are valid wherever x and y have code points in the range [0x00,0x7F] and codepoint(x) ≤ codepoint(y). The natural extension of such character ranges to Unicode would simply change the requirement that the endpoints lie in [0x00,0x7F] to the requirement that they lie in [0x0000,0x10FFFF]. However, in practice this is often not the case. Some implementations, such as that of gawk, do not allow character ranges to cross Unicode blocks. A range like [0x61,0x7F] is valid since both endpoints fall within the Basic Latin block, as is [0x0530,0x0560] since both endpoints fall within the Armenian block, but a range like [0x0061,0x0532] is invalid since it includes multiple Unicode blocks. Other engines, such as that of the Vim editor, allow block crossing but the character values must not be more than 256 apart. Case insensitivity. Some case insensitivity flags affect only the ASCII characters. Other flags affect all characters. Some engines have two different flags, one for ASCII, the other for Unicode. Exactly which characters belong to the POSIX classes also varies. Cousins of case insensitivity. As ASCII has case distinction, case insensitivity became a logical feature in text searching. Unicode introduced alphabetic scripts without case like Devanagari. For these, case sensitivity is not applicable. For scripts like Chinese, another distinction seems logical: between traditional and simplified. In Arabic scripts, insensitivity to initial, medial, final, and isolated position may be desired. In Japanese, insensitivity between hiragana and katakana is sometimes useful. Normalization. Unicode has combining characters. Like old typewriters, plain base characters (white spaces, punctuation characters, symbols, digits, or letters) can be followed by one or more non spacing symbols (usually diacritics, like accent marks modifying letters) to form a single printable character; but Unicode also provides a limited set of precomposed characters, i. e. characters that already include one or more combining characters. A sequence of a base character + combining characters should be matched with the identical single precomposed character (only some of these combining sequences can be precomposed into a single Unicode character, but infinitely many other combining sequences are possible in Unicode, and needed for various languages, using one or more combining characters after an initial base character; these combining sequences may include a base character or combining characters partially precomposed, but not necessarily in canonical order and not necessarily using the canonical precompositions). The process of standardizing sequences of a base character + combining characters by decomposing these canonically equivalent sequences, before reordering them into canonical order (and optionally recomposing some combining characters into the leading base character) is called normalization. New control codes. Unicode introduced amongst others, byte order marks and text direction markers. These codes might have to be dealt with in a special way. Introduction of character classes for Unicode blocks, scripts, and numerous other character properties. Block properties are much less useful than script properties, because a block can have code points from several different scripts, and a script can have code points from several different blocks. In Perl and the library, properties of the form \p{InX} or \p{Block=X} match characters in block X and \P{InX} or \P{Block=X} matches code points not in that block. Similarly, \p{Armenian}, \p{IsArmenian}, or \p{Script=Armenian} matches any character in the Armenian script. In general, \p{X} matches any character with either the binary property X or the general category X. For example, \p{Lu}, \p{Uppercase Letter}, or \p{GC=Lu} matches any uppercase letter. Binary properties that are not general categories include \p{White Space}, \p{Alphabetic}, \p{Math}, and \p{Dash}. Examples of non binary properties are \p{Bidi Class=Right to Left}, \p{Word Break=A Letter}, and \p{Numeric Value=10}.

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

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

Применение

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

Индукция

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