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

"Regex" перенаправляется сюда. Для комиксов см. Re: Gex.
Результаты совпадения шаблона 
(?<=.){2,}(?=[А-Я])
Соответствуют как минимум два пробела, но только если они встречаются непосредственно после точки (.) И перед заглавной буквой.
Стивен Коул Клини, который помог изобрести концепцию
Черный список на Википедия который использует регулярные выражения для определения плохих заголовков

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

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

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

Узоры

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

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

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

Идет перевод то Клини звезда
(s* означает "ноль или более s")

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

История

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

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

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

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

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

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

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

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

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

Логическое "или"
А вертикальная полоса разделяет альтернативы. Например, серый|серый может соответствовать «серому» или «серому».
Группировка
Скобки используются для определения объема и приоритета операторы (среди прочего). Например, серый | серый и гр(а|е)у являются эквивалентными шаблонами, которые оба описывают набор «серого» или «серого».
Количественная оценка
А квантификатор после жетон (например, символ) или группа указывает, как часто может встречаться предыдущий элемент. Наиболее распространенными кванторами являются вопросительный знак ?, то звездочка * (получено из Клини звезда ), а знак плюс + (Клини плюс ).
?Знак вопроса указывает ноль или один появления предыдущего элемента. Например, цвет соответствует как «цвету», так и «цвету».
*Звездочка указывает ноль или больше появления предыдущего элемента. Например, ab * c соответствует "ac", "abc", "abbc", "abbbc" и так далее.
+Знак плюс указывает один или больше появления предыдущего элемента. Например, ab + c соответствует «abc», «abbc», «abbbc» и т. д., но не «ac».
{n}[19]Предыдущий элемент точно соответствует п раз.
{мин,}[19]Предыдущий элемент соответствует мин или более раз.
{мин Макс}[19]Предыдущий элемент соответствует как минимум мин раз, но не более Максимум раз.
Подстановочный знак

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

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

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

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

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

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

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

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

Учитывая регулярные выражения 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 обозначает {"0", "1"}, (Р*) обозначает множество всех конечных двоичные строки (включая пустую строку). Если R обозначает {"ab", "c"}, (Р*) обозначает {ε, «ab», «c», «abab», «abc», «cab», «cc», «ababab», «abcab», ...}.

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

Примеры:

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

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

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

Регулярные выражения в этом смысле могут выражать регулярные языки, в точности класс языков, принятый детерминированные конечные автоматы. Однако есть существенная разница в компактности. Некоторые классы регулярных языков могут быть описаны только детерминированными конечными автоматами, размер которых растет. экспоненциально размером с кратчайшие эквивалентные регулярные выражения. Стандартный пример - это языкиLk состоящий из всех строк в алфавите {а,б} чей kth-от последней буквы равноа. С одной стороны, регулярное выражение, описывающее L4 дан кем-то.

Обобщая этот паттерн на Lk дает выражение:

С другой стороны, известно, что каждый детерминированный конечный автомат, принимающий язык Lk должно быть не менее 2k состояния. К счастью, есть простое отображение регулярных выражений в более общие недетерминированные конечные автоматы (NFAs), что не приводит к такому увеличению размеров; по этой причине NFA часто используются как альтернативные представления обычных языков. NFA - это простая вариация типа 3 грамматики из Иерархия Хомского.[20]

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

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

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

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

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

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

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

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

Синтаксис

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

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

Разделители

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

Стандарты

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

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

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

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

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

МетасимволОписание
^Соответствует начальной позиции в строке. В линейных инструментах он соответствует начальной позиции любой строки.
.Соответствует любому одиночному символу (многие приложения исключают новые строки, и какие именно символы считаются новыми строками, зависит от вкуса, кодировки символов и платформы, но можно с уверенностью предположить, что символ перевода строки включен). В выражениях скобок POSIX символ точки соответствует буквальной точке. Например, a.c соответствует "abc" и т. д., но [a.c] соответствует только "a", "." или "c".
[ ]Выражение в скобках.Соответствует одному символу, заключенному в квадратные скобки. Например, [abc] соответствует «a», «b» или «c». [а-я] указывает диапазон, который соответствует любой строчной букве от «a» до «z». Эти формы можно смешивать: [abcx-z] соответствует "a", "b", "c", "x", "y" или "z", как и [a-cx-z].

В - символ рассматривается как буквальный, если он последний или первый (после ^, если есть) в квадратных скобках: [abc-], [-abc]. Обратите внимание, что экранирование обратной косой черты не допускается. В ] можно включить символ в квадратное выражение, если он первый (после ^) персонаж: [] abc].

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

Примеры:

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

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

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

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

Примеры:

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

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

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

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

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

POSIXНестандартныйPerl / TclVimЯваASCIIОписание
[: ascii:][30]п{ASCII}[x00-x7F]Символы ASCII
[: alnum:]п{Альнум}[A-Za-z0-9]Буквенно-цифровые символы
[:слово:][30]шшш[A-Za-z0-9_]Буквенно-цифровые символы плюс "_"
WWW[^ A-Za-z0-9_]Несловесные символы
[:альфа:]ап{Альфа}[A-Za-z]Буквенные символы
[:пустой:]sп{Пустой}[ ]Пробел и табуляция
б< >б(?<=W)(?=ш)|(?<=ш)(?=W)Границы слов
B(?<=W)(?=W)|(?<=ш)(?=ш)Несловные границы
[: cntrl:]п{Cntrl}[x00-x1Fx7F]Управляющие символы
[: цифра:]ddп{Цифра} или же d[0-9]Цифры
DDD[^0-9]Нецифровые
[: график:]п{График}[x21-x7E]Видимые персонажи
[:ниже:]лп{Ниже}[а-я]Строчные буквы
[:Распечатать:]пп{Распечатать}[x20-x7E]Видимые символы и пробел
[: punct:]п{Пункт}[][!"#$%&'()*+,./:;<=>?@^_`{|}~-]Знаки пунктуации
[:Космос:]s_sп{Космос} или же s[ vж ]Пробельные символы
SSS[^ vf]Непробельные символы
[: верхний:]тып{Верхний}[А-Я]Заглавные буквы
[: xdigit:]Иксп{XDigit}[A-Fa-f0-9]Шестнадцатеричные цифры

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

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

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

Perl и PCRE

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

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

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

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

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

соответствует всей строке (потому что вся строка начинается и заканчивается двойной кавычкой) вместо соответствия только первой части, «Ганимед»,. Однако вышеупомянутые количественные показатели могут быть сделаны ленивый или же минимальный или же вынужденный, сопоставив как можно меньше символов, добавив вопросительный знак: ".+?" только совпадения «Ганимед»,.[32]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существует несколько теоретических альтернатив обратному отслеживанию для обратных ссылок, и их «показатели» более укрощены, поскольку они связаны только с количеством обратных ссылок, фиксированным свойством некоторых языков регулярных выражений, таких как POSIX. Один наивный метод, который дублирует NFA без возврата для каждой заметки с обратной ссылкой, имеет сложность время и место для стога сена длиной n и k обратных ссылок в RegExp.[43] Недавняя теоретическая работа, основанная на автоматах памяти, дает более жесткие границы на основе используемых «активных» переменных узлов и полиномиальную возможность для некоторых регулярных выражений с обратными ссылками.[44]

Unicode

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

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

Использует

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

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

Примеры

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

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

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

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

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

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

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

Метасимвол (ы)ОписаниеПример[50]
.Обычно соответствует любому символу, кроме новой строки.
В квадратных скобках точка буквальная.
$ string1 = "Привет, мир";если ($ string1 =~ м /...../) {  Распечатать "$ string1 имеет длину> = 5.";}

Выход:

Hello World имеет длину> = 5.
( )Группирует серию элементов узора в один элемент.
Когда вы сопоставляете шаблон в круглых скобках, вы можете использовать любой из $1, $2, ... позже для ссылки на ранее подобранный шаблон.
$ string1 = "Привет, мир";если ($ string1 =~ м / (H ..). (o ..) /) {  Распечатать «Мы нашли '1 доллар' и '2 доллара'».;}

Выход:

Мы подобрали «Hel» и «o W».
+Один или несколько раз соответствует предыдущему элементу шаблона.
$ string1 = "Привет, мир";если ($ string1 =~ м / л + /) {  Распечатать "В строке $ string1 одна или несколько последовательных букв" l ".";}

Выход:

В Hello World одна или несколько последовательных букв "l".
?Соответствует предыдущему элементу шаблона ноль или один раз.
$ string1 = "Привет, мир";если ($ string1 =~ м / H.? e /) {  Распечатать "Есть буквы" H "и" e ", разделенные" ";  Распечатать «0–1 символы (например, He Hue Hee)».;}

Выход:

Есть буквы «H» и «e», разделенные символами 0–1 (например, He Hue Hee).
?Изменяет *, +, ? или же {M, N}'d регулярное выражение, которое предшествует, чтобы соответствовать как можно меньше раз.
$ string1 = "Привет, мир";если ($ string1 =~ м / (л. + з) /) {  Распечатать "Нежадное совпадение с 'l', за которым следует один или";  Распечатать «больше символов - это llo, а не llo Wo».;}

Выход:

Нежадное соответствие с «l», за которым следует один или несколько символов, - это «llo», а не «llo Wo».
*Соответствует предыдущему элементу шаблона ноль или более раз.
$ string1 = "Привет, мир";если ($ string1 =~ м / эл * о /) {  Распечатать "Ко многим идет буква" е ", за которой следует ноль";  Распечатать «l», за которым следует «o» (например, eo, elo, ello, elllo) ».;}

Выход:

После буквы «е» следует от нуля до многих «l», за которыми следует «o» (например, eo, elo, ello, elllo).
{M, N}Обозначает минимальное M и максимальное количество совпадений N.
N можно опустить, а M может быть 0: {M} соответствует «точно» M раз; {M,} соответствует "не менее" M раз; {0, N} соответствует "не более" N раз.
х * у + г? таким образом эквивалентно х {0,} y {1,} z {0,1}.
$ string1 = "Привет, мир";если ($ string1 =~ м / л {1,2} /) {  Распечатать "Существует подстрока как минимум с 1";  Распечатать "и не более 2 l в $ string1";}

Выход:

В Hello World существует подстрока от 1 до 2 l.
[…]Обозначает набор возможных совпадений символов.
$ string1 = "Привет, мир";если ($ string1 =~ m / [aeiou] + /) {  Распечатать «$ string1 содержит одну или несколько гласных».;}

Выход:

Hello World содержит одну или несколько гласных.
|Разделяет альтернативные возможности.
$ string1 = "Привет, мир";если ($ string1 =~ м / (Привет | Привет | Пого) /) {  Распечатать «$ string1 содержит хотя бы одно из Hello, Hi или Pogo».;}

Выход:

Hello World содержит как минимум одно из Hello, Hi или Pogo.
Соответствует границе нулевой ширины между символом класса слова (см. Далее) и либо символом, не являющимся классом слова, либо ребром; такой же как

(^ w | w $ | Ww | wW).

$ string1 = "Привет, мир";если ($ string1 =~ м / л /) {  Распечатать «Есть слово, оканчивающееся на« лло »».;}

Выход:

Есть слово, оканчивающееся на «лло».
шСоответствует буквенно-цифровому символу, включая «_»;
такой же как [A-Za-z0-9_] в ASCII и
[p {Alphabetic}p {GC = Mark}p {GC = Decimal_Number}p {GC = Connector_Punctuation}]

в Юникоде,[46] где По алфавиту свойство содержит больше латинских букв, а Десятичное число свойство содержит более арабских цифр.

$ string1 = "Привет, мир";если ($ string1 =~ м / ж /) {  Распечатать "Есть хотя бы один буквенно-цифровой";  Распечатать "символ в $ string1 (A-Z, a-z, 0-9, _).";}

Выход:

В Hello World есть хотя бы один буквенно-цифровой символ (A-Z, a-z, 0-9, _).
WСоответствует не-буквенно-цифровой символ, исключая "_";
такой же как [^ A-Za-z0-9_] в ASCII и
[^ p {По алфавиту}p {GC = Mark}p {GC = Decimal_Number}p {GC = Connector_Punctuation}]

в Юникоде.

$ string1 = "Привет, мир";если ($ string1 =~ м / Вт /) {  Распечатать "Пробел между Hello и";  Распечатать «Мир не буквенно-цифровой».;}

Выход:

Пробел между Hello и World не является буквенно-цифровым.
sСоответствует пробельному символу,
которые в ASCII - табуляция, перевод строки, перевод страницы, возврат каретки и пробел;
в Юникоде также соответствует no-пробелы разрыва, следующая строка и переменная-пробелы ширины (среди прочего).
$ string1 = "Привет, мир";если ($ string1 =~ м / с. * с /) {  Распечатать "В $ string1 есть ДВА символа пробела, которые могут";  Распечатать «быть разделенными другими символами».;}

Выход:

В Hello World есть ДВА символа пробела, которые могут быть разделены другими символами.
SСовпадает с чем угодно но пробел.
$ string1 = "Привет, мир";если ($ string1 =~ м / с. * с /) {  Распечатать "В $ string1 есть ДВА непробельных символа, которые";  Распечатать "могут быть разделены другими символами".;}

Выход:

В Hello World есть ДВА непробельных символа, которые могут быть разделены другими символами.
dСоответствует цифре;
такой же как [0-9] в ASCII;
в Юникоде, как и p {Digit} или же p {GC = Decimal_Number} собственность, которая сама по себе такая же, как p {Numeric_Type = Decimal} свойство.
$ string1 = «99 бутылок пива на стене».;если ($ string1 =~ м / (д +) /) {  Распечатать "$ 1 - это первое число в '$ string1'";}

Выход:

99 - это первое число из «99 бутылок пива на стене».
DСоответствует не цифре;
такой же как [^0-9] в ASCII или P {Digit} в Юникоде.
$ string1 = "Привет, мир";если ($ string1 =~ м / д /) {  Распечатать "В $ string1 есть хотя бы один символ";  Распечатать «это не цифра».;}

Выход:

В Hello World есть хотя бы один символ, не являющийся цифрой.
^Соответствует началу строки или строки.
$ string1 = "Привет, мир";если ($ string1 =~ м / ^ He /) {  Распечатать «$ string1 начинается с символов« Он »».;}

Выход:

Hello World начинается с символа «Он».
$Соответствует концу строки или строки.
$ string1 = "Привет, мир";если ($ string1 =~ м / год $ /) {  Распечатать "$ string1 - строка или строка";  Распечатать "который заканчивается на 'rld'.";}

Выход:

Hello World - это строка или строка, заканчивающаяся на 'rld'.
АСоответствует началу строки (но не внутренней строке).
$ string1 = "Привет, мир";если ($ string1 =~ м / AH /) {  Распечатать "$ string1 - строка";  Распечатать "который начинается с 'H'.";}

Выход:

HelloWorld - это строка, начинающаяся с буквы «H».
zСоответствует концу строки (но не внутренней строке).[51]
$ string1 = "Привет, мир";если ($ string1 =~ м / дз /) {  Распечатать "$ string1 - строка";  Распечатать "который заканчивается на 'd  n'.";}

Выход:

HelloWorld - это строка, заканчивающаяся на d.
[^…]Соответствует всем символам, кроме заключенных в квадратные скобки.
$ string1 = "Привет, мир";если ($ string1 =~ м / [^ abc] /) { Распечатать "$ string1 содержит символ, отличный от"; Распечатать «а, б и в».;}

Выход:

Hello World содержит символы, отличные от a, b и c.

Индукция

Основная статья: Индукция обычных языков

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

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

Примечания

  1. ^ Гойвертс, янв. «Учебник по регулярным выражениям - узнайте, как использовать регулярные выражения». www.regular-expressions.info. Архивировано из оригинал на 2016-11-01. Получено 2016-10-31.
  2. ^ Митков, Руслан (2003). Оксфордский справочник по компьютерной лингвистике. Издательство Оксфордского университета. п. 754. ISBN  978-0-19-927634-9. В архиве из оригинала на 28.02.2017. Получено 2016-07-25.
  3. ^ Лоусон, Марк В. (17 сентября 2003 г.). Конечные автоматы. CRC Press. С. 98–100. ISBN  978-1-58488-255-8. В архиве из оригинала 27 февраля 2017 г.. Получено 25 июля 2016.
  4. ^ Клини 1951.
  5. ^ Люн, Хинг (16 сентября 2010 г.). «Регулярные языки и конечные автоматы» (PDF). Государственный университет Нью-Мексико. Архивировано из оригинал (PDF) 5 декабря 2013 г.. Получено 13 августа 2019. Концепция регулярных событий была введена Клини через определение регулярных выражений.
  6. ^ а б Томпсон 1968.
  7. ^ а б Джонсон и др. 1968 г..
  8. ^ Керниган, Брайан (2007-08-08). "Средство сопоставления регулярных выражений". Красивый код. O'Reilly Media. С. 1–2. ISBN  978-0-596-51004-6. В архиве из оригинала на 07.10.2020. Получено 2013-05-15.
  9. ^ Ричи, Деннис М. «Неполная история текстового редактора QED». Архивировано из оригинал на 1999-02-21. Получено 9 октября 2013.
  10. ^ а б Ахо и Ульман 1992, 10.11 Библиографические примечания к главе 10, с. 589.
  11. ^ Эйкок 2003, 2. Методы JIT-компиляции, 2.1 Genesis, стр. 98.
  12. ^ Раймонд, Эрик С. цитируя Деннис Ричи (2003). "Файл жаргона 4.4.7: grep". Архивировано из оригинал на 2011-06-05. Получено 2009-02-17.
  13. ^ «Новые возможности регулярных выражений в Tcl 8.1». В архиве из оригинала 07.10.2020. Получено 2013-10-11.
  14. ^ «Документация по PostgreSQL 9.3.1: 9.7. Сопоставление с образцом». В архиве из оригинала на 07.10.2020. Получено 2013-10-12.
  15. ^ Стена, Ларри и команда разработчиков Perl 5 (2006 г.). "perlre: регулярные выражения Perl". В архиве из оригинала 31 декабря 2009 г.. Получено 2006-10-10.
  16. ^ а б Стена (2002)
  17. ^ "GROVF | Ускорение аналитики больших данных". grovf.com. В архиве из оригинала на 07.10.2020. Получено 2019-10-22.
  18. ^ "CUDA grep". bkase.github.io. В архиве из оригинала на 07.10.2020. Получено 2019-10-22.
  19. ^ а б c grep (1) справочная страница
  20. ^ а б Хопкрофт, Мотвани и Ульман (2000)
  21. ^ Сипсер (1998)
  22. ^ Гелад и Невен (2008)
  23. ^ Грубер и Хольцер (2008)
  24. ^ Джей Л. Гишер (1984). (Название неизвестно) (Технический отчет). Стэнфордский университет, кафедра комп. Sc.
  25. ^ Джон Э. Хопкрофт, Раджив Мотвани и Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления. Река Аппер Сэдл / Нью-Джерси: Аддисон Уэсли. ISBN  978-0-201-44124-6. Здесь: раздел 3.4.6, с.117-120. - Это свойство не обязательно должно соблюдаться для расширенных регулярных выражений, даже если они не описывают более широкий класс, чем обычные языки; ср. стр.121.
  26. ^ Козен (1991)[страница нужна ]
  27. ^ В.Н. Редько (1964). «Об определении соотношений для алгебры регулярных событий». Украинский математический журнал. 16 (1): 120–126. В архиве из оригинала на 2018-03-29. Получено 2018-03-28. (На русском)
  28. ^ ИСО / МЭК 9945-2: 1993 Информационные технологии - Интерфейс переносимой операционной системы (POSIX) - Часть 2: Оболочка и служебные программы, последовательно пересматривается как ISO / IEC 9945-2: 2002 Информационные технологии. Интерфейс переносимой операционной системы (POSIX). Часть 2. Системные интерфейсы., ISO / IEC 9945-2: 2003 и в настоящее время ISO / IEC / IEEE 9945: 2009 Информационные технологии - Базовые спецификации интерфейса переносимой операционной системы (POSIX®), выпуск 7
  29. ^ Единая спецификация Unix (версия 2)
  30. ^ а б "33.3.1.2 Классы символов - Руководство Emacs Lisp - Версия 25.1". gnu.org. 2016. В архиве из оригинала на 07.10.2020. Получено 2017-04-13.
  31. ^ "Документация по регулярным выражениям Perl". perldoc.perl.org. В архиве с оригинала 31 декабря 2009 г.. Получено 8 января, 2012.
  32. ^ а б «Синтаксис регулярного выражения». Документация Python 3.5.0. Фонд программного обеспечения Python. Архивировано из оригинал 18 июля 2018 г.. Получено 10 октября 2015.
  33. ^ а б «Основные классы: регулярные выражения: квантификаторы: различия между жадными, неохотными и притяжательными квантификаторами». Учебники по Java. Oracle. В архиве из оригинала 7 октября 2020 г.. Получено 23 декабря 2016.
  34. ^ «Атомная группировка». Учебник по регулярным выражениям. В архиве из оригинала 7 октября 2020 г.. Получено 24 ноября 2019.
  35. ^ Цезарь Кампеану, Кай Саломаа и Шэн Ю (декабрь 2003 г.). «Формальное изучение практических регулярных выражений». Международный журнал основ информатики. 14 (6): 1007–1018. Дои:10.1142 / S012905410300214X. В архиве из оригинала от 04.07.2015. Получено 2015-07-03. Теорема 3 (стр.9)
  36. ^ «Сопоставление регулярных выражений Perl - сложная задача». perl.plover.com. В архиве из оригинала на 07.10.2020. Получено 2019-11-21.
  37. ^ Блуждающая логика. «Как смоделировать опережающий и опережающий взгляд в конечных автоматах?». Обмен стеками информатики. В архиве из оригинала 7 октября 2020 г.. Получено 24 ноября 2019.
  38. ^ Кокс (2007)
  39. ^ Лаурикари (2009)
  40. ^ "gnulib / lib / dfa.c". Если сканер обнаруживает переход по обратной ссылке, он возвращает своего рода «полууспех», указывающий на то, что совпадение должно быть проверено с помощью механизма поиска с возвратом.
  41. ^ Кирнс, Стивен (август 2013 г.). «Сублинейное сопоставление с конечными автоматами с использованием обратного суффиксного сканирования». arXiv:1308.3822 [cs.DS ].
  42. ^ Наварро, Гонсало (10 ноября 2001 г.). «NR ‐ grep: быстрый и гибкий инструмент сопоставления с образцом» (PDF). Программное обеспечение: практика и опыт. 31 (13): 1265–1312. Дои:10.1002 / spe.411. В архиве (PDF) из оригинала 7 октября 2020 г.. Получено 21 ноября 2019.
  43. ^ "travisdowns / polyregex". 5 июля 2019. В архиве из оригинала 14 сентября 2020 г.. Получено 21 ноября 2019.
  44. ^ Шмид, Маркус Л. (март 2019 г.). «Регулярные выражения с обратными ссылками: методы сопоставления за полиномиальное время». arXiv:1903.05896 [cs.FL ].
  45. ^ "Документация Vim: шаблон". Vimdoc.sourceforge.net. В архиве из оригинала на 07.10.2020. Получено 2013-09-25.
  46. ^ а б "UTS № 18 о регулярных выражениях Unicode, приложение A: блоки символов". В архиве из оригинала на 07.10.2020. Получено 2010-02-05.
  47. ^ Горовиц, Брэдли (24 октября 2011 г.). "Осенний взмах". Блог Google. В архиве из оригинала 21 октября 2018 г.. Получено 4 мая 2019.
  48. ^ Символ "m" не всегда требуется для указания Perl операция сопоставления. Например, м / [^ abc] / также может отображаться как / [^ abc] /. 'M' требуется только в том случае, если пользователь желает указать операцию сопоставления без использования косой черты в качестве регулярного выражения. разделитель. Иногда полезно указать альтернативный разделитель регулярных выражений, чтобы избежать "коллизия разделителей ". Видеть 'Perldoc Perlre В архиве 2009-12-31 на Wayback Machine ' Больше подробностей.
  49. ^ Например, см. Ява в двух словах, п. 213; Python Сценарии для вычислительной науки, п. 320; Программирование PHP, п. 106.
  50. ^ Обратите внимание, что все операторы if возвращают ИСТИННОЕ значение.
  51. ^ Конвей, Дамиан (2005). «Регулярные выражения, конец строки». Лучшие практики Perl. О'Рейли. п. 240. ISBN  978-0-596-00173-5. В архиве из оригинала на 07.10.2020. Получено 2017-09-10.

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

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