Регулярные выражения с обратными ссылками
Базовые определения
Определение: |
Группа (англ. capture group) — часть регулярного выражения. Группа заключается в круглые скобки. |
Каждой группе соответствует порядковый номер. Нумерация идёт слева направо: номеру группы соответствует порядковый номер открывающей круглой скобки этой группы в тексте регулярного выражения.
Пример:
Группа — группа — группа —
Определение: |
Обратная ссылка (англ. backreference) — механизм повторного использования групп или слов группы. |
Для повторного использования слова группы используется обозначение где — номер группы.
Пример использования:
Данное регулярное выражение будет допускать только слова, в которых количество букв чётно.Для повторного использования регулярного выражения группы используется обозначение
где — номер группы. Использование круглых скобок обусловленно тем, что как управляющий символ уже используется.
Обратите внимание, что символы круглых скобок и обратной косой являются управляющими. Чтобы использовать их непосредственно как часть слова, их нужно экранировать.
Пример экранирования (в данном случае в качестве символа экранирования используется символ обратной косой черты):
— обратная ссылка на первую группу, — слово, состоящее из символа обратной косой черты и единицы.
Определение: |
Регулярные выражения с обратными ссылками (англ. regex with backreferences) — регулярные выражения, использующие механизм обратных ссылок. |
Примеры
- Регулярное выражение породит язык
- Выразим язык тандемных повторов над алфавитом
- Данный язык не является регулярным, однако его можно представить с помощью регулярных выражений с использованием обратных ссылок.
используя механизм обратных ссылок:
- Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины
- для чётного :
- для нечётного :
- где – любой одиночный символ.
или :
- Запишем выражение для языка лемме о разрастании), то есть является контекстно-зависимым, но также легко представим с помощью обратных ссылок:
- .
Данный язык не является ни регулярным, ни контекстно-свободным (по - Язык
- Следущий за ссылкой знак вопроса обозначает использование группы или раз, то есть осуществление рекурсивного вызова или его окончание.
-
- Очевидно, что все слова из языка удовлетворяют данному регулярному выражению.
можно представить при помощи обратных ссылок:
Теорема о КС-языках
Теорема: |
С помощью механизма обратных ссылок можно представить любой контекстно-свободный язык. |
Доказательство: |
Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского, следовательно, достаточно доказать, что грамматику, заданную в такой форме, можно преобразовать в регулярное выражение с обратными ссылками. Рассмотрим правила, которые могут содержаться в такой грамматике:
Представим каждое из них в виде регулярного выражения с обратными ссылками. Используя ссылки на регулярные выражения, соответствующие нетерминалам и , можно представить первое правило:где и соответствуют нетерминалам и ; Второе и третье правила не требуют использования обратных ссылок:
Если какому-то нетерминалу Регулярное выражение для соответствуют несколько регулярных выражений , заменить их на одно: (очевидно, что оно также будет соответствовать этому нетерминалу). будет искомым. |
Регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные грамматики, а также некоторые контекстно-зависимые (см. пример 4).
Примеры преобразования
Рассмотрим следующую КС-грамматику:
Эквивалентным будет выражение
Другой пример:
Допустим, группа
соответствует нетерминалу группы — нетерминалам соответственно.- Для каждого нетерминала составим регулярное выражение:
- Объединим регулярные выражения, соответствующие одинаковым нетерминалам:
- Искомое регулярное выражение соответствует нетерминалу
Таким образом, регулярное выражение для этой грамматики будет выглядеть так:
Применение
С помощью обратных ссылок можно составить регулярные выражения для языка тандемных повторов и других языков, где требуется «запоминать» части входящих в язык слов.
Регулярные выражения в языках программирования зачастую поддерживают обратные ссылки. На практике их можно использовать, например, для парсинга
-выражений (поиск подстрок, содержащихся в определённых тегах).