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