Что такое обратные ссылки в регулярных выражениях
Истинное могущество регулярных выражений
«Ты не можешь парсить HTML с помощью регулярных выражений, потому что HTML не является регулярным. Используй XML парсер, и будет тебе счастье»
Что же на самом деле означает «регулярный»?
В контексте теории формальных языков что-то называется «регулярным», когда оно имеет грамматику, в которой любое правило вывода имеет одну из следующих форм:
Всё это, возможно, звучит несколько абстрактно, поэтому давайте рассмотрим пример: определение натуральных чисел как грамматики.
Эта грамматика говорит о том, что:
В этом примере цифры от 0 до 9 будут терминалами (поскольку их нельзя разбить на составляющие), а N будет единственным нетерминалом (поскольку его можно разделять дальше).
Другой момент, на который вы могли обратить внимание, это то, что несмотря на описание грамматикой таких простых вещей, она уже весьма раздута. Разве не было бы лучше, если бы мы могли выразить ту же концепцию, но в более сжатой форме?
И тут на сцену выходят регулярные выражения: грамматика выше эквивалентна регэкспу 4+ (который чертовски проще). И преобразование такого типа можно применить к любой регулярной грамматике: каждая из них имеет соответствующее регулярное выражение, описывающее все допустимые для неё строки.
Что могут описывать регулярные выражения
Итак, возникает закономерный вопрос: регулярные выражения могут описывать только регулярные грамматики, или они способны на большее? Ответом на него будет и да, и нет.
Регулярные выражения в смысле формальных грамматик могут (по определению) описывать только регулярные грамматики и ничего более.
Но когда программисты говорят о «регулярных выражениях», они не подразумевают формальные грамматики. Они говорят о производных регулярных выражениях, реализованных в их языках программирования. И эти реализации регэкспов весьма поверхностно связаны с изначальным понятием регулярности.
Любая современная разновидность регэкспов может описывать гораздо больше, чем просто регулярные языки. Уточнение того, насколько больше, — тема дальнейшего повествования.
Для сохранения простоты, я сфокусируюсь только на PCRE-реализации регэкспов. Просто потому, что я знаю её лучше всего (поскольку она используется в PHP). Множество прочих реализаций весьма с ней схожи, поэтому большую часть нижеизложенного можно применить и к ним тоже.
Иерархия языков
Для анализа того, что можно, а что нельзя описать с помощью регулярных выражений, прежде всего рассмотрим, какие ещё существуют типы языков. Хорошей точкой отсчёта для этого будет иерархия Хомского:
Как видите, она делит формальные языки на четыре типа: регулярные языки (тип 3) — наименее мощные, за которыми следуют контекстно-свободные языки (тип 2), контекстно-зависимые языки (тип 1) и, наконец, всемогущие неограниченные языки (тип 0).
Иерархия Хомского — контейнерная, поэтому маленькие коробочки на картинке полностью заключены в большие коробки. Т.е. любой регулярный язык является также контекстно-свободным (но не наоборот!).
Итак, давайте поднимемся на ступеньку вверх по иерархии. Мы уже знаем, что регулярным выражением можно описать любой регулярный язык. А возможно ли это для контекстно-свободных языков?
(Напоминание: когда я говорю «регулярные выражения», я подразумеваю их в программистском смысле, а не в смысле теории формальных языков).
Описание контекстно-свободных языков
Ответ на вопрос выше: да, возможно!
Следовательно, регулярные выражения способны описывать как минимум некоторые не регулярные, контекстно-свободные грамматики. Но могут ли они описать их все? Чтобы ответить на этот вопрос, посмотрим прежде на определение контекстно-свободных грамматик.
В контекстно-свободной грамматике все правила вывода имеют вид:
Здесь A — снова нетерминальный символ, а β — произвольная строка из терминалов и нетерминалов. Таким образом, каждое правило контекстно-свободной грамматики имеет нетерминал в левой части и строку из произвольных символов справа.
В качестве примера рассмотрим следующую грамматику:
Это отрывок из PHP-грамматики (всего лишь несколько простых правил). Синтаксис немного отличается от того, что мы использовали раньше, но его можно легко понять. Один из аспектов, который стоит отметить, состоит в том, что имена T_SOMETHING здесь также являются терминальными символами. Такие символы обычно называют токенами, они кодируют собой более абстрактные понятия. Например, T_FUNCTION представляет из себя ключевое слово function, а T_STRING — токен-метка (подобно getUserById или some_other_name).
Я использую этот пример, чтобы продемонстрировать одну вещь: контекстно-свободные грамматики уже достаточно мощны, чтобы кодировать достаточно сложные языки. Вот почему почти все языки программирования имеют контекстно-свободные грамматики. В этот перечень входит и синтаксически корректный HTML.
Возвращаясь к актуальному вопросу: так могут ли регулярные выражения связывать все контекстно-свободные грамматики? Снова ответ: да!
Это чрезвычайно легко доказать, поскольку регулярные выражения (по крайней мере, PCRE и ему подобные) предоставляют синтаксис для построения грамматик, очень похожий на приведённый выше:
То, что вы видите выше — это регулярное выражение для описания e-mail адреса с помощью RFC 5322. Оно построено с помощью простого преобразования БНФ-правил из RFC в нотацию, которую понимает PCRE.
Синтаксис чрезвычайно прост: все определения правил оборачиваются в DEFINE-утверждение, которое в основном означает, что все эти правила не должны непосредственно чему-то соответствовать, их достаточно просто декларировать. Только часть ^(?&addr_spec)$ в самом конце определяет, что же в конце-концов тут описывается.
Таким образом, приведённый выше синтаксис позволяет просто отобразить грамматику на регулярное выражение:
Единственная загвоздка в том, что регулярные выражения не поддерживают левостороннюю рекурсию. Т.е., если взять приведённое выше определение списка параметров:
Вы не сможете в точности конвертировать его в основанный на грамматике регэксп. Следующее не сработает:
Причина этого в том, что non_empty_parameter_list появляется в крайней левой части своего собственного определения. Это называется левосторонней рекурсией и очень часто встречается в определениях грамматик. Причина в том, что LALR(1) парсеры, которые чаще всего используются для разбора, обычно обрабатывают левостороннюю рекурсию лучше, чем правостороннюю.
Но не пугайтесь, это не в коей мере не влияет на мощь регулярных выражений. Каждая леворекурсивная грамматика может быть преобразована в праворекурсивную. В примере выше достаточно просто поменять местами две части:
Теперь должно быть абсолютно ясно, что регулярные выражения способны описывать любой контекстно-свободный язык (и, следовательно, почти все языки, с которыми сталкиваются программисты). Единственная проблема: несмотря на то, что регулярные выражения могут описывать контекстно-свободные грамматики, они обычно не могут разбирать их. Разбор подразумевает преобразование какой-либо строки в абстрактное синтаксическое дерево. Для этого невозможно использовать регулярные выражения, по крайней мере PCRE (хотя, конечно, в Perl’e, где есть возможность вставлять произвольный код в регулярное выражение, вы можете практически всё. ).
А сейчас позвольте мне снова заострить внимание на том, о чём я мимоходом упоминал ранее: синтаксически корректный HTML — контекстно-свободен. Следовательно, вы можете описывать его, используя регулярные выражения, в противовес распространённому мнению. Просто не забывайте о двух вещах: во-первых, большая часть HTML, с которым вы сталкиваетесь, не синтаксически корректная (обычно, она даже не является закрытой). И во-вторых, только то, что вы можете, не означает, что вы должны. Вы можете писать свой софт на Brainfuck, однако существуют причины, почему вы этого не делаете, верно?
Моё мнение по теме таково: где бы вы не нуждались в общей HTML-обработке, используйте DOM-библиотеку на свой вкус. Она правильно обработает некорректный HTML и примет на себя всю тяжесть разбора. С другой стороны, если вы имеете дело со специфическими случаями, то быстрые регулярные выражения часто наилучший выход. И я должен признаться: хотя я обычно говорю людям не разбирать HTML с помощью регулярных выражений, сам я, как известно, делаю это частенько. Просто потому, что часто сталкиваюсь со специфическими ситуациями, когда использовать регэкспы элементарно проще.
Контекстно-зависимые грамматики
Теперь, когда мы подробно рассмотрели контекстно-свободные языки, давайте поднимемся вверх на ещё одну ступеньку в иерархии Хомского: к контекстно-зависимым языкам.
Для них структурные правила будут иметь следующую форму:
Чтобы сделать изложенное более понятным, попробуем интерпретировать следующие правила:
По-русски это будет звучать так:
Заменить `A` на `c`, но только в том случае, если у него имеется `a b` слева.
Заменить `B` на `Q H`, но только в том случае, если у него имеется `a` слева и `c` справа.
Заменить `B` на `C`, но только если у него есть `H` слева.
Контекстно-зависимые языки — это то, что вы редко встретите в «нормальном» программировании. Они более важны в области обработки естественных языков (поскольку естественные языки определённо не являются контекстно-свободными. Слова имеют различное значение в зависимости от контекста). Но даже люди, занимающиеся обработкой естественных языков, работают с так называемыми «мягко контекстно-зависимыми языками», поскольку для моделирования их достаточно, а разбор происходит намного быстрее.
Для понимания того, насколько могуществены контекстно-зависимые грамматики, давайте рассмотрим другой класс грамматик, обладающий точно такой же выразительной силой, как и контекстно-зависимые: неукорачивающие грамматики.
Эти отношения (эквивалентные для контекстно-зависимых и неудлиняющих грамматик) делают абсолютно ясным, что с помощью контекстно-зависимых грамматик вы можете практически всё. Просто не укорачивайте 🙂
Чтобы получить понятие, почему обе грамматики имеют одинаковую выразительную силу, посмотрите на следующий пример преобразований:
Ладно, вернёмся к регулярным выражениям. Могут ли они так же описывать и контекстно-зависимые языки?
На этот раз я не смогу вам дать определённого ответа. Конечно, они могут описывать некоторые контекстно-зависимые языки, но я понятия не имею, могут ли они описывать их все.
PCRE-регэксп для этого языка следующий:
В приведённом выше регэкспе вы также можете увидеть, как реализована концепция контекста в регулярных выражениях с использованием утверждений. Если мы теперь вернёмся к определению контекстно-зависимой грамматики, то вы можете сказать, что правило вывода вида
можно преобразовать в следующее DEFINE-правило регэкспов:
Но факт невозможности прямого преобразования контекстно-зависимой грамматики в регэксп сам по себе не означает, что регулярные выражения на могут описывать их все. Например, приведённый выше язык
Так что же мы в конце-концов можем сказать? Регэкспы могут описывать как минимум некоторые контекстно-зависимые языки, но неизвестно, способны ли они описать их все.
Неограниченные грамматики
Следующий класс грамматик в иерархии Хомского — неограниченные грамматики. В набор языков, которые могут формироваться с их помощью, входят все рекурсивно-перечислимые языки.
Насколько в точности сильны неограниченные грамматики? Настолько, что сильнее их не бывает: они Тьюринг-полны. Существует даже «язык программирования», основанный на неограниченных грамматиках: Thue. Поскольку он Тьюринг-полный, то может делать всё, на что способны остальные языки программирования.
Одним из следствий Тьюринг-полноты является то, что проблема проверки на принадлежность определённой строки некоторой грамматике в общем случае неразрешима.
К сожалению, я не могу рассказать ещё что бы то ни было о том, как связаны регулярные выражения и неограниченные грамматики. Чёрт, я даже не смог найти пример адекватной неограниченной грамматики (которая не была бы неукорачивающей).
Но сейчас, поскольку мы заговорили о Тьюринг-полноте, перейдём к следующему моменту:
Регулярные выражения с обратными ссылками являются NP-полными
Вот ещё одно очень мощное свойство регулярных выражений, о котором я не упоминал ранее: обратные ссылки.
Т.е. содержащие вот такой очень простой регэксп:
То, что этот регэксп описывает, называется «языком копий» и является ещё одним типичным примером контекстно-зависимых языков.
Аналогичным образом вы можете описать с помощью обратных ссылок прочие примеры грамматик, приведённые выше:
Объяснение того, как это работает, выходит за рамки данной статьи, но вы можете прочитать об этом прекрасный топик на StackOverflow.
Как видите, простое добавление обратной ссылки (без поддержки рекурсивной подмаски) уже увеличивает силу регулярных выражений. Оно в принципе настолько могущественно, что делает описание регулярными выражениями NP-полной задачей.
Что означает «NP-полная»? NP-полнота — это один из классов в теории сложности вычислений для решения задач, в который впадают многие «тяжёлые» проблемы. Примерами NP-полных задач являются задача коммивояжера (TSP), задача выполнимости булевых формул (SAT) и задача о ранце (BKP).
Другое важное условие для того, чтобы называть задачу NP-полной, это возможность свести к ней любую другую NP-задачу. Таким образом, все NP-полные задачи в основном взаимозаменяемы. Если найдёте быстрое решение одной из них, то вы будете иметь быстрое решение для них всех.
Так что если кто-то найдёт быстрое решение для NP-полной задачи, то практически все сложные вычислительные задачи человечества будут решены одним махом. Что, как мы знаем, будет означать конец цивилизации.
Чтобы доказать, что регулярные выражения с обратными ссылками в точности NP-полны, можно просто взять одну из хорошо известных NP-полных задач и доказать, что она может быть решена с помощью использования регулярных выражений. В качестве примера я выбрал 3-CNF SAT задачу.
3-CNF SAT расшифровывается как «Задача выполнимости булевых формул в 3-конъюнктивной нормальной форме» и достаточно проста для понимания. Имеется булева формула следующего вида:
Она состоит из ряда условий, разделённых операторами И. Каждое из этих условий состоит из трёх переменных (или их отрицаний), разделённых операторами ИЛИ. 3-CNF SAT спрашивает: существует ли решение у этой булевой формулы (например, истина)?
Приведённую выше булеву формулу можно преобразовать в следующее регулярное выражение:
Теперь дело за движком. Он проверяет различные пути для связывания строки до тех пор, пока или решение не будет найдено, или он не сдастся.
Подводя итог
Но не забывайте: из того, что вы можете, не следует, что вы должны. Обработка HTML с помощью регулярных выражений — действительно плохая идея в некоторых случаях. А в других — это, возможно, лучшее, что можно сделать.
Просто прикиньте, каково простейшее решение для вашей конкретной задачи, и используйте его. Если вы выберите решать задачу с помощью регулярных выражений, не забывайте о x-модификаторе, который позволяет вам сделать более красивым формат ваших регэкспов. Для сложных регулярных выражений так же не забывайте использовать DEFINE-утверждения и именованные подмаски, чтобы сохранить ваш код чистым и читаемым.
От переводчика: возможные замечания по поводу перевода, пожалуйста, пишите в личку. Я буду за них очень признательна.
Конструкции обратных ссылок в регулярных выражениях
Обратные ссылки предоставляют удобный способ идентификации повторяющегося символа или подстроки в строке. Например, если входная строка содержит несколько экземпляров произвольной подстроки, можно найти первое вхождение с помощью группы записи, а затем использовать обратную ссылку для поиска последующих вхождений подстроки.
Для ссылки на именованные и нумерованные захватываемые группы в строках замены используется отдельный синтаксис. Для получения дополнительной информации см. Подстановки.
.NET определяет отдельные элементы языка для ссылки на нумерованные и именованные захватываемые группы. Дополнительные сведения о группах записи см. в статье Конструкции группирования.
Нумерованные обратные ссылки
Нумерованная обратная ссылка использует следующий синтаксис:
где число — это порядковое положение захватываемой группы в регулярном выражении. Например, \4 соответствует содержимому четвертой захватываемой группы. Если параметр число не определен в шаблоне регулярного выражения, возникает ошибка синтаксического анализа, и обработчик регулярных выражений создает исключение ArgumentException. Например, регулярное выражение \b(\w+)\s\1 является допустимым, поскольку (\w+) — это первая и единственная захватываемая группа в выражении. С другой стороны, выражение \b(\w+)\s\2 недопустимо и создает исключение аргумента, так как захватываемая группа с номером \2 отсутствует. Кроме того, если число определяет захватываемую группу с определенным порядковым номером, но захватываемой группе назначено числовое имя, отличное от ее порядкового номера, то анализатор регулярных выражений также создает исключение ArgumentException.
Следует отметить неоднозначность такой записи, которая может означать как восьмеричные escape-коды (например, \16 ), так и \ число для обратных ссылок. Эта неопределенность разрешается следующим образом:
Выражения с \1 по \9 всегда интерпретируются как обратные ссылки, а не как восьмеричные коды.
Если первая цифра многоразрядного выражения — 8 или 9 (например, \80 или \91 ), выражение интерпретируется как литерал.
Выражения от \10 и более считаются обратными ссылками, если имеется обратная ссылка, соответствующая этому номеру. В противном случае они интерпретируются как восьмеричные коды.
Если регулярное выражение содержит обратную ссылку на неопределенный номер группы, возникает ошибка синтаксического анализа, и обработчик регулярных выражений создает исключение ArgumentException.
| Элемент | Описание: |
|---|---|
| (\w) | Совпадение со словообразующим символом и его назначение первой захватываемой группе. |
| \1 | Совпадение со следующим символом, значение которого совпадает с первой захватываемой группой. |
Именованные обратные ссылки
Именованная обратная ссылка задается с помощью следующего синтаксиса:
где name— это имя захватываемой группы, определенное в шаблоне регулярного выражения. Если параметр имя не определен в шаблоне регулярного выражения, возникает ошибка синтаксического анализа, и обработчик регулярных выражений создает исключение ArgumentException.
Именованные числовые обратные ссылки
В именованной обратной ссылке с \k имя также может быть строковым представлением числа. Например, далее используется регулярное выражение (? \w)\k для поиска в строке двойных словообразующих символов. В этом случае в примере определяется захватываемая группа, которая явно названа «2», и обратная ссылка, соответственно названная «2».
Однако, если имя является строковым представлением числа и захватываемой группе на этой позиции явно назначено числовое имя, обработчик регулярных выражений не сможет идентифицировать захватываемую группу по ее порядковому номеру. Вместо этого он создаст исключение ArgumentException. Единственная захватываемая группа в следующем примере имеет имя «2». Поскольку конструкция \k используется для определения обратных ссылок с именем «1», обработчик регулярных выражений не может идентифицировать первую группу записи и вызывает исключение.
С чем сопоставляются обратные ссылки
Обратная ссылка относится к самому недавнему определению группы (самому ближнему слева определению при обработке слева направо). Если из группы создается несколько шаблонов для поиска, обратная ссылка относится к самому последнему шаблону.
При сравнении регулярного выражения с входной строкой («aababb») обработчик регулярных выражений выполняет указанные далее операции.
В этом примере * является циклическим квантификатором — он вычисляется многократно до тех пор, пока обработчик регулярных выражений не сможет обнаружить соответствие заданному им шаблону. Квантификаторы циклов не удаляют определения групп.
| Шаблон | Описание: |
|---|---|
| \b | Сопоставление начинается на границе слова. |
| (\p | Совпадение с двумя прописными буквами. Это первая группа записи. |
| (\d<2>)? | Совпадение с нулевым или единичным вхождением двух десятичных цифр. Это вторая группа записи. |
| (\p | Совпадение с двумя прописными буквами. Это третья группа записи. |
| \b | Сопоставление заканчивается на границе слова. |
Входная строка может соответствовать этому регулярному выражению, даже если отсутствуют две десятичные цифры, которые заданы второй захватываемой группой. В следующем примере показано, что даже несмотря на то, что сопоставление является успешным, между двумя группами успешной записи найдена пустая группа.
Регулярные выражения с обратными ссылками
Содержание
Базовые определения [ править ]
| Определение: |
| Группа (англ. capture group) — часть регулярного выражения. Общепринятое условное обозначение группы — круглые скобки. |
Пример: [math]aba(ca)ba.\,[/math] В данном регулярном выражении представлена одна группа — [math](ca).[/math]
Каждой группе соответствует порядковый номер. Нумерация идёт слева направо: номеру группы соответствует порядковый номер открывающей круглой скобки этой группы в тексте регулярного выражения (исключая случаи, когда скобки являются частью синтаксической конструкции).
Пример: [math](ab(cd))(ef).[/math] Группа [math]№1[/math] — [math](ab(cd)),\,[/math] группа [math]№2[/math] — [math](cd),\,[/math] группа [math]№3[/math] — [math](ef)[/math]
| Определение: |
| Обратная ссылка (англ. backreference) — механизм повторного использования групп или слов группы. |
Для повторного использования слова группы используется обозначение [math]\backslash n,\,[/math] где [math]n[/math] — номер группы.
Пример использования: [math]((1\,|\,0)^*)\backslash 1.\,[/math] Данное регулярное выражение будет задавать язык тандемных повторов. Несмотря на то, что он не является регулярным, его можно представить с помощью механизма обратных ссылок.
Для повторного использования регулярного выражения группы используется обозначение [math](?n),\,[/math] где [math]n[/math] — номер группы. Использование круглых скобок обусловленно тем, что [math]?,[/math] как управляющий символ, уже используется. В данном случае круглые скобки следует воспринимать как общепринятое условное обозначение обратной ссылки; запись [math](?n)[/math] не задаёт группу. Например, в выражении [math](aba)(?1)(caba)(?2)\;[/math] ссылке [math](?2)[/math] будет соответствовать [math](caba),\,[/math] а не [math](?1).[/math]
Обратите внимание, что символы круглых скобок и обратной косой черты являются управляющими. Чтобы использовать их непосредственно как часть слова, их нужно экранировать.
Пример экранирования (в данном случае в качестве символа экранирования используется символ обратной косой черты): [math]\backslash 1[/math] — обратная ссылка на первую группу, [math]\backslash\backslash 1[/math] — слово, состоящее из символа обратной косой черты и единицы.
| Определение: |
| Регулярные выражения с обратными ссылками (англ. regex with backreferences) — регулярные выражения, использующие механизм обратных ссылок. |
Примеры [ править ]
Теорема о КС-языках [ править ]
Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского, следовательно, достаточно доказать, что грамматику, заданную в такой форме, можно преобразовать в регулярное выражение с обратными ссылками. Рассмотрим правила, которые могут содержаться в такой грамматике:
[math]A\rightarrow BC\\A\rightarrow a\\S\rightarrow\varepsilon[/math]
Представим каждое из них в виде регулярного выражения с обратными ссылками.
[math]A\rightarrow BC\leftrightarrow A\rightarrow ((?n_B)\,(?n_C)),\,[/math] где [math](?n_B)[/math] и [math](?n_C)[/math] соответствуют нетерминалам [math]B[/math] и [math]C[/math] ;
Второе и третье правила не требуют использования обратных ссылок:
[math]A\rightarrow a\leftrightarrow A\rightarrow (a);\\S\rightarrow\varepsilon\leftrightarrow S\rightarrow ().[/math]
Регулярное выражение для данной КС-грамматики соответствует нетерминалу [math]S,\,[/math] однако в нём могут встречаться ссылки на внешние — отличные от [math]S[/math] — группы. Будем обрабатывать такие ссылки, используя метод левостороннего вывода. При обработке очередной ссылки:
После соответствующих замен регулярное выражение для [math]S[/math] будет искомым.
Пример преобразования [ править ]
Рассмотрим следующую КС-грамматику:
[math]S\rightarrow cA\\S\rightarrow dA\\S\rightarrow cB\\S\rightarrow eB\\A\rightarrow a\\B\rightarrow b[/math]
Напоминание: круглые скобки в записи обратной ссылки являются синтаксической конструкцией и не задают группу.
Таким образом, регулярное выражение для данной грамматики будет выглядеть так: [math](((c)(a))\,|\,((d)(?4))\,|\,((?3)(b))\,|\,((e)(?8))).[/math]
Рассмотрим другой пример:
[math]S\rightarrow\varepsilon\\S\rightarrow (S)S\\S\rightarrow S(S)[/math]
Таким образом, регулярное выражение для данной грамматики будет выглядеть так: [math](()\,|\,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?1)(?4))).[/math]
Применение [ править ]
Регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные грамматики, а также некоторые контекстно-зависимые (например, язык тандемных повторов).