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

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

[math](aba)c\backslash 1[/math] — пример такого регулярного выражения.

Выражение, заключённое в скобки, называется группой (англ. capture group). Скобки захватывают текст, сопоставленный регулярным выражением внутри нумерованной группы, который может быть повторно использован с помощью обратной ссылки с указанием номера группы.

«[math]\backslash[/math]» – символ обратной ссылки (англ. backreference), который действует на первую группу. Обратная ссылка [math]\backslash 1[/math] показывает, что после группы [math]1[/math] — [math](aba)[/math] — и символа [math]c[/math] должен быть описан тот же текст, что содержится в ней.

Порядок нумерации групп: сначала внешняя, потом вложенные (в порядке обхода в глубину).

Примеры

  • Выразим язык тандемных повторов над алфавитом [math]\Sigma=\{0,1\},[/math] используя механизм обратных ссылок:
[math]L=((0|1)^∗)\backslash 1[/math]
Данный язык не является регулярным, однако его можно представить с помощью регулярных выражений с использованием обратных ссылок.
  • Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины [math]n=2\cdot m\,[/math] или [math]\,n=2\cdot m+1[/math]:
  1. для чётного [math]n[/math]: [math]\;(.)(.)(.)...(.)\backslash m...\backslash 3\backslash 2\backslash 1;[/math]
  2. для нечётного [math]n[/math]: [math]\;(.)(.)(.)...(.).\backslash m...\backslash 3\backslash 2\backslash 1,\;[/math]
где «[math].[/math]» – любой одиночный символ.
  • Запишем регулярное выражение для языка [math]L=b^kab^kab^ka[/math]. Данный язык не является ни регулярным, ни контекстно-свободным (по лемме о разрастании), но также легко представим с помощью обратных ссылок:
[math]L=(b\{b\}^*a)\backslash 1\backslash 1[/math].
Группа [math]1[/math] — [math](b\{b\}^∗a)[/math] — представляет из себя регулярное выражение для языка [math]L=b^ka,k\gt 0\,[/math], последующие за ней обратные ссылки используются для многократного использования текста группы. Поэтому после «[math]b^ka[/math]» обязан присутствовать текст «[math]b^kab^ka[/math]».
  • Язык [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)=\cdots[/math]
Очевидно, что все слова из языка [math]L[/math] удовлетворяют данному регулярному выражению.

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

Теорема:
С помощью механизма обратных ссылок можно представить любой контекстно-свободный язык.
Доказательство:
[math]\triangleright[/math]

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

[math]A\rightarrow BC[/math]

[math]A\rightarrow a[/math]

[math]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]С[/math];

Второе и третье правила не требуют использования обратных ссылок:

[math]A\rightarrow a\leftrightarrow A=a;[/math]

[math]S\rightarrow\varepsilon\leftrightarrow S=\varepsilon.[/math]

Таким образом, регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные грамматики, а также некоторые контекстно-зависимые.
[math]\triangleleft[/math]

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

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

[math]S\rightarrow A\\A\rightarrow BC\\A\rightarrow CD[/math]

Очевидно, что эквивалентным будет выражение [math]((?1)\,(?2)\,|\,(?2)\,(?3))\,[/math], где группы [math]1, 2, 3[/math] соответствуют [math]B, C, D[/math].


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

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

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

Применение

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

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

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Регулярные_выражения_с_обратными_ссылками&oldid=65543»