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

Базовые определения

Определение:

Группа (англ. capture group) — часть регулярного выражения. Группа заключается в круглые скобки.

Каждой группе соответствует порядковый номер. Нумерация идёт слева направо: номеру группы соответствует порядковый номер открывающей круглой скобки этой группы в тексте регулярного выражения.

Пример: [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](a^*)\backslash 1.\,[/math] Данное регулярное выражение будет допускать только слова, в которых количество букв [math]a[/math] чётно.

Для повторного использования регулярного выражения группы используется обозначение [math](?n),\,[/math] где [math]n[/math] — номер группы. Использование круглых скобок обусловленно тем, что [math]?[/math] как управляющий символ уже используется.

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

Пример экранирования (в данном случае в качестве символа экранирования используется символ обратной косой черты): [math]\backslash 1[/math] — обратная ссылка на первую группу, [math]\backslash\backslash 1[/math] — слово, состоящее из символа обратной косой черты и единицы.

Определение:

Регулярные выражения с обратными ссылками (англ. regex with backreferences) — регулярные выражения, использующие механизм обратных ссылок.

Примеры

1. Регулярное выражение [math](aba?)c(?1)\,[/math] породит язык [math]L=\{abcab,abacab,abcaba,abacaba\}.[/math]
2. Выразим язык тандемных повторов над алфавитом [math]\Sigma=\{0,1\},[/math] используя механизм обратных ссылок:

   [math]L=((0\,|\,1)^∗)\backslash 1.[/math]

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

3. Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины [math]n=2\cdot m\,[/math] или [math]\,n=2\cdot m+1[/math]:
   • для чётного [math]n[/math]: [math]\;(a_1)(a_2)(a_3)\dotsc(a_m)\backslash m\dotsc\backslash 3\backslash 2\backslash 1;[/math]
   • для нечётного [math]n[/math]: [math]\;(a_1)(a_2)(a_3)\dotsc(a_m)a_{m+1}\backslash m\dotsc\backslash 3\backslash 2\backslash 1,\;[/math]

   где [math]a_i[/math] – любой одиночный символ.

4. Запишем выражение для языка [math]L=b^kab^kab^ka,\,k\gt 0.\,[/math] Данный язык не является ни регулярным, ни контекстно-свободным (по лемме о разрастании), то есть является контекстно-зависимым, но также легко представим с помощью обратных ссылок:

   [math]L=(bb^*a)\backslash 1\backslash 1[/math].

5. Язык [math]L=a^nb^n,\,n\gt 0\,[/math] можно представить при помощи обратных ссылок:

   [math]L=(a(?1)?b).[/math]

   Следущий за ссылкой [math](?1)[/math] знак вопроса обозначает использование группы [math]0[/math] или [math]1[/math] раз, то есть осуществление рекурсивного вызова или его окончание.

   [math]?1[/math] ссылается на первую группу — [math](a(?1)?b)[/math], что равносильно рекурсивной зависимости:

   [math](a(?1)?b)=[/math]

   [math]=(a(a(?1)?b)?b)=[/math]

   [math]=(a(a(a(?1)?b)?b)?b)=[/math]

   [math]=(a(a(a(a(?1)?b)?b)?b)?b)=\dotsc[/math]

   Очевидно, что все слова из языка [math]L[/math] удовлетворяют данному регулярному выражению.

Теорема о КС-языках

Теорема:

С помощью механизма обратных ссылок можно представить любой контекстно-свободный язык.

Доказательство:

[math]\triangleright[/math]

Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского, следовательно, достаточно доказать, что грамматику, заданную в такой форме, можно преобразовать в регулярное выражение с обратными ссылками. Рассмотрим правила, которые могут содержаться в такой грамматике: [math]A\rightarrow BC\\A\rightarrow a\\S\rightarrow\varepsilon[/math] Представим каждое из них в виде регулярного выражения с обратными ссылками. Используя ссылки на регулярные выражения, соответствующие нетерминалам [math]B[/math] и [math]C[/math], можно представить первое правило: [math]A\rightarrow BC\leftrightarrow A=((?1)\,(?2)),\,[/math] где [math]1[/math] и [math]2[/math] соответствуют нетерминалам [math]B[/math] и [math]C[/math]; Второе и третье правила не требуют использования обратных ссылок: [math]A\rightarrow a\leftrightarrow A=a;\\S\rightarrow\varepsilon\leftrightarrow S=\varepsilon.[/math] Если какому-то нетерминалу [math]A[/math] соответствуют несколько регулярных выражений [math]r_1, r_2, \dotsc, r_n[/math], заменить их на одно: [math]A=((r_1)\,|\,(r_2)\,|\,\dotsc\,|\,(r_n))\,[/math] (очевидно, что оно также будет соответствовать этому нетерминалу). Регулярное выражение для [math]S[/math] будет искомым.

[math]\triangleleft[/math]

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

Примеры преобразования

Рассмотрим следующую КС-грамматику:

[math]S\rightarrow A\\A\rightarrow\varepsilon\\A\rightarrow BA\\B\rightarrow b\\B\rightarrow c[/math]

Эквивалентным будет выражение [math](((b\,|\,c)\,(?1)?)?).[/math]

Другой пример:

[math]S\rightarrow AB\\S\rightarrow\varepsilon\\A\rightarrow SS\\B\rightarrow CD\\C\rightarrow c\\D\rightarrow d[/math]

Допустим, группа [math]№1[/math] соответствует нетерминалу [math]S,\,[/math] группы [math]№2[/math] и [math]№5[/math] — нетерминалы [math]A[/math] и [math]D[/math] соответственно.

1. Для каждого нетерминала составим регулярное выражение:

   [math]S\leftrightarrow ((?2)(?3))\\S\leftrightarrow\varepsilon\\A\leftrightarrow ((?1)(?1))\\B\leftrightarrow ((?4)(?5))\\C\leftrightarrow c\\D\leftrightarrow d[/math]

2. Объединим регулярные выражения, соответствующие одинаковым нетерминалам:

   [math]S\leftrightarrow (((?2)(?3))\,|\,\varepsilon)\\A\leftrightarrow ((?1)(?1))\\B\leftrightarrow ((?4)(?5))\\C\leftrightarrow c\\D\leftrightarrow d[/math]

3. Искомое регулярное выражение соответствует нетерминалу [math]S,\,[/math] однако оно ссылается на группы, отличные от [math]S.[/math] Будем рекурсивно заменять такие ссылки на сами регулярные выражения до тех пор, пока в исходном регулярном выражении не останутся только терминалы и ссылки на стартовый нетерминал [math]S[/math]:

   [math](((?2)(?3))\,|\,\varepsilon)\rightarrow(((?1)(?1)(?3))\,|\,\varepsilon)\rightarrow(((?1)(?1)(?4)(?5))\,|\,\varepsilon)\rightarrow(((?1)(?1)c(?5))\,|\,\varepsilon)\rightarrow(((?1)(?1)cd)\,|\,\varepsilon).[/math]

Таким образом, регулярное выражение для этой грамматики будет выглядеть так: [math](((?1)(?1)cd)\,|\,\varepsilon).[/math]

Применение

С помощью обратных ссылок можно составить регулярные выражения для языка тандемных повторов и других языков, где требуется «запоминать» части входящих в язык слов.

Регулярные выражения в языках программирования зачастую поддерживают обратные ссылки. На практике их можно использовать, например, для парсинга [math]html[/math]-выражений (поиск подстрок, содержащихся в определённых тегах).

См. также

• Регулярные языки: два определения и их эквивалентность
• Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
• Нормальная форма Хомского
• Иерархия Хомского формальных грамматик

Источники информации

• Работа с обратными ссылками в Java
• Визуализатор регулярных выражений
• habr.com — Истинное могущество регулярных выражений