Изменения

|id=maindefgroupdef|definition='''Регулярные выражения с обратными ссылкамиГруппа''' (англ. ''regex with backreferencescapture group'') {{---}} одна из разновидностей регулярных выражений, дающая возможность использовать в них слова, принадлежащие некоторой группечасть [[Регулярные языки: два определения и их эквивалентность|регулярного выражения]]. Общепринятое условное обозначение группы {{---}} круглые скобки.

Выражение, заключённое в скобки, называется ''группой'' Пример: <tex>aba(англ. ''capture group''ca)ba. Скобки захватывают текст\, сопоставленный регулярным выражением внутри нумерованной группы, который может быть повторно использован с помощью обратной ссылки с указанием номера группы</tex> В данном регулярном выражении представлена одна группа {{---}} <tex>(ca).</tex>

«<tex>\backslash</tex>» – символ обратной ссылки (англКаждой группе соответствует порядковый номер. ''backreference''), который действует на первую группу. Обратная ссылка <tex>\backslash 1</tex> показывает, что после Нумерация идёт слева направо: номеру группы соответствует порядковый номер открывающей круглой скобки этой группы <tex>1</tex> {{---}} <tex>в тексте регулярного выражения (abaисключая случаи, когда скобки являются частью синтаксической конструкции)</tex> {{---}} и символа <tex>c</tex> должен быть описан тот же текст, что содержится в ней.

Порядок нумерации группПример: сначала внешняя, потом вложенные <tex>(ab(cd))(в порядке [[Обход в глубину, цвета вершин|обхода в глубину]]ef).==Примеры==* Запишем [[Регулярные языки: два определения и их эквивалентность|регулярное выражение]] для языка тандемных повторов над алфавитом </tex> Группа <tex>№1</tex> {{---}} <tex>(ab(cd)),\Sigma=\,</tex> группа <tex>№2</tex> {{0---}} <tex>(cd),1\,</tex> группа <tex>№3</tex> {{---}}<tex>(ef)</tex>:

:<tex>L{{Определение|id=referencedef|definition='''Обратная ссылка''' ((0англ. ''backreference'') {{---}} механизм повторного использования групп или [[Основные определения, связанные со строками|1)^∗)\backslash 1</tex>слов]] группы.}}

:Данный язык не является регулярным, однако его можно представить с помощью регулярных выражений с использованием обратных ссылок.* Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины Для повторного использования '''слова''' группы используется обозначение <tex>\backslash n=2\cdot m\,</tex> или <tex>\,n=2\cdot m+1</tex>:# для чётного <tex>n</tex>: <tex>\;(.)(.)(.)...(.)\backslash m...\backslash 3\backslash 2\backslash 1;</tex># для нечётного где <tex>n</tex>: <tex>\;(.)({{---}} номер группы.)(.)...(.).\backslash m...\backslash 3\backslash 2\backslash 1,\;</tex>

Пример использования:где «<tex>((1\,|\,0)^*)\backslash 1.\,</tex>» – любой одиночный символДанное регулярное выражение будет задавать язык тандемных повторов. Несмотря на то, что он не является [[Регулярные языки: два определения и их эквивалентность|регулярным]], его можно представить с помощью механизма обратных ссылок.

* Запишем регулярное выражение для языка Для повторного использования '''регулярного выражения''' группы используется обозначение <tex>L=b^kab^kab^ka(?n),\,</tex> где <tex>n</tex> {{---}} номер группы. Использование круглых скобок обусловленно тем, что <tex>?,</tex>как управляющий символ, уже используется. Данный язык В данном случае круглые скобки следует воспринимать как общепринятое '''условное обозначение''' обратной ссылки; запись <tex>(?n)</tex> не является ни регулярнымзадаёт группу. Например, ни контекстно-свободным в выражении <tex>(aba)(?1)(caba)(?2)\;</tex> ссылке <tex>(?2)</tex> будет соответствовать <tex>(по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]]caba), но также легко представим с помощью обратных ссылок:\,</tex> а не <tex>(?1).</tex>

Обратите внимание, что символы круглых скобок и обратной косой черты являются управляющими. Чтобы использовать их непосредственно как часть слова, их нужно [https:Группа <tex>1</tex> {{---}} <tex>(b\{b\}^∗a)</tex> {{---}} представляет из себя регулярное выражение для языка <tex>L=b^ka,k>0\,</tex>, последующие за ней обратные ссылки используются для многократного использования ''текста'' группыru.wikipedia. Поэтому после «<tex>b^ka<org/tex>» обязан присутствовать текст «<tex>b^kab^ka<wiki/tex>»Экранирование_символов экранировать].

* Язык <tex>L=a^nb^n,\,n>0\,</tex> можно представить при помощи обратных ссылок: :<tex>L=(aПример экранирования (?1в данном случае в качестве символа экранирования используется символ обратной косой черты)?b),</tex> :где «<tex>?\backslash 1</tex>» – {{---}} обратная ссылкана первую группу, осуществляющая рекурсивный вызов первой группы. Следущий за ссылкой знак вопроса обозначает использование группы <tex>0</tex> или <tex>\backslash\backslash 1</tex> раз, то есть осуществление рекурсивного вызова или его окончание. :<tex>?1</tex> ссылается на первую группу {{---}} <tex>(a(?1)?b)</tex>, что равносильно рекурсивной зависимости: ::::<tex>(a(?1)?b)=</tex>:::<tex>=(a(a(?1)?b)?b)=</tex>::<tex>=(a(a(a(?1)?b)?b)?b)=</tex>:<tex>=(a(a(a(a(?1)?b)?b)?b)?b)=\cdots</tex> :Очевиднослово, что все слова состоящее из языка <tex>L</tex> удовлетворяют данному регулярному выражениюсимвола обратной косой черты и единицы.

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

<tex>A\rightarrow BC\\A\rightarrow a\\S\rightarrow\varepsilon</tex>

Используя ссылки на регулярные выражения, соответствующие нетерминалам <tex>S\rightarrow\varepsilonB</tex>и <tex>C</tex>, можно представить первое правило:

Используя ссылки на регулярные выражения, соответствующие нетерминалам <tex>B</tex> Второе и <tex>C</tex>, можно представить первое правилотретье правила не требуют использования обратных ссылок:

<tex>A\rightarrow BCa\leftrightarrow A=\rightarrow ((?Ba);\\S\rightarrow\varepsilon\,leftrightarrow S\rightarrow (?C)).\,</tex>

Второе и третье правила не требуют использования обратных ссылокЕсли какому-то нетерминалу <tex>A</tex> соответствуют несколько регулярных выражений <tex>r_1, r_2, \dotsc, r_n</tex>, заменить их на одно:<tex>A=(r_1\,|\,r_2\,|\,\dotsc\,|\,r_n)\,</tex> (очевидно, что оно также будет соответствовать этому нетерминалу).

Регулярное выражение для данной КС-грамматики соответствует нетерминалу <tex>AS,\rightarrow a\leftrightarrow A=a;,</tex> однако в нём могут встречаться ссылки на внешние {{---}} отличные от <tex>S</tex>{{---}} группы. Будем обрабатывать такие ссылки, используя метод [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|левостороннего вывода]]. При обработке очередной ссылки:# если эта ссылка встречается впервые, вместо неё подставим соответствующее регулярное выражение и запомним номер его группы в текущем регулярном выражении;# иначе вместо этой ссылки подставим ссылку на соответствующую группу в текущем регулярном выражении.

Таким образом, регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные грамматики, а также некоторые [[Иерархия Хомского формальных грамматик|контекстно-зависимые]]После соответствующих замен регулярное выражение для <tex>S</tex> будет искомым.

Рассмотрим следующую КС<tex>S\rightarrow cA\\S\rightarrow dA\\S\rightarrow cB\\S\rightarrow eB\\A\rightarrow a\\B\rightarrow b</tex>  # Приведём её к нормальной форме Хомского:#: <tex>S\rightarrow CA\\S\rightarrow DA\\S\rightarrow CB\\S\rightarrow EB\\A\rightarrow a\\B\rightarrow b\\C\rightarrow c\\D\rightarrow d\\E\rightarrow e</tex># Каждому нетерминалу поставим в соответствие свой номер:#: <tex>S\leftrightarrow 1, A\leftrightarrow 2, B\leftrightarrow 3, C\leftrightarrow 4, D\leftrightarrow 5, E\leftrightarrow 6</tex># Каждое правило представим в виде регулярного выражения с обратными ссылками: #: <tex>S\rightarrow ((?4)(?2))\\S\rightarrow ((?5)(?2))\\S\rightarrow ((?4)(?3))\\S\rightarrow ((?6)(?3))\\A\rightarrow (a)\\B\rightarrow (b)\\C\rightarrow (c)\\D\rightarrow (d)\\E\rightarrow (e)</tex># Объединим регулярные выражения, соответствующие одинаковым нетерминалам:#: <tex>S\rightarrow (((?4)(?2))\,|\,((?5)(?2))\,|\,((?4)(?3))\,|\,((?6)(?3)))\\A\rightarrow (a)\\B\rightarrow (b)\\C\rightarrow (c)\\D\rightarrow (d)\\E\rightarrow (e)</tex># Избавимся от внешних ссылок в регулярном выражении для <tex>S</tex>:{| class="wikitable" style="display: inline-table; white-space: nowrap; text-align: center;"|+Пошаговый вывод! № || Текущее регулярное выражение|-| 1. || <tex>(((\underline{\textbf{?4}})(\underline{?2}))\,|\,((\underline{?5})(\underline{?2}))\,|\,((\underline{?4})(\underline{?3}))\,|\,((\underline{?6})(\underline{?3})))\,</tex>|-| 2. || <tex>(((c)(\underline{\textbf{?2}}))\,|\,((\underline{?5})(\underline{?2}))\,|\,((\underline{?4})(\underline{?3}))\,|\,((\underline{?6})(\underline{?3})))\,</tex>|-| 3. || <tex>(((c)(a))\,|\,((\underline{\textbf{?5}})(\underline{?2}))\,|\,((\underline{?4})(\underline{?3}))\,|\,((\underline{?6})(\underline{?3})))\,</tex>|-| 4. || <tex>(((c)(a))\,|\,((d)(\underline{\textbf{?2}}))\,|\,((\underline{?4})(\underline{?3}))\,|\,((\underline{?6})(\underline{?3})))\,</tex>|-| 5. || <tex>(((c)(a))\,|\,((d)(?4))\,|\,((\underline{\textbf{?4}})(\underline{?3}))\,|\,((\underline{?6})(\underline{?3})))\,</tex>|-| 6. || <tex>(((c)(a))\,|\,((d)(?4))\,|\,((?3)(\underline{\textbf{?3}}))\,|\,((\underline{?6})(\underline{?3})))\,</tex>|-| 7. || <tex>(((c)(a))\,|\,((d)(?4))\,|\,((?3)(b))\,|\,((\underline{\textbf{?6}})(\underline{?3})))\,</tex>|-| 8. || <tex>(((c)(a))\,|\,((d)(?4))\,|\,((?3)(b))\,|\,((e)(\underline{\textbf{?3}})))\,</tex>|-| 9. || <tex>(((c)(a))\,|\,((d)(?4))\,|\,((?3)(b))\,|\,((e)(?8)))\,</tex>|}{| class="wikitable" style="display: inline-грамматикуtable; white-space: nowrap; text-align: center;" |+№ группы в <tex>S</tex>! <tex>S</tex> || <tex>A</tex> || <tex>B</tex> || <tex>C</tex> || <tex>D</tex> || <tex>E</tex>|-| 1 || || || style="background: #1b5de2; color: white;" | || || |-| 1 || style="background: #1b5de2; color: white;" | || || <b>3</b> || |||-| 1 || <b>4</b> || || 3 || style="background: #1b5de2; color: white;" | || |-| 1 || style="background: #1b5de2; color: white;" | 4 || || 3 || <b>6</b> || |-| 1 || 4 || || style="background: #1b5de2; color: white;" | 3 || 6 || |-| 1 || 4 || style="background: #1b5de2; color: white;" | || 3 || 6 || |-| 1 || 4 || <b>8</b> || 3 || 6 || style="background: #1b5de2; color: white;" | |-| 1 || 4 || style="background: #1b5de2; color: white;" | 8 || 3 || 6 || <b>10</b>|-| 1 || 4 || 8 || 3 || 6 || 10|}'''Напоминание''': круглые скобки в записи обратной ссылки являются синтаксической конструкцией и не задают группу.  Таким образом, регулярное выражение для данной грамматики будет выглядеть так:<tex>(((c)(a))\,|\,((d)(?4))\,|\,((?3)(b))\,|\,((e)(?8))).</tex>

Другой пример# Приведём её к нормальной форме Хомского:#: <tex>S\rightarrow\varepsilon\\S\rightarrow AS\\S\rightarrow SA\\A\rightarrow OB\\B\rightarrow SC\\O\rightarrow (\\C\rightarrow\; )</tex># Каждому нетерминалу поставим в соответствие свой номер:#: <tex>S\leftrightarrow 1, A\leftrightarrow 2, B\leftrightarrow 3, O\leftrightarrow 4, C\leftrightarrow 5</tex># Каждое правило представим в виде регулярного выражения с обратными ссылками: #: <tex>S\rightarrow ()\\S\rightarrow ((?2)(?1))\\S\rightarrow ((?1)(?2))\\A\rightarrow ((?4)(?3))\\B\rightarrow ((?1)(?5))\\O\rightarrow (\backslash (\,)\\C\rightarrow (\backslash )\,)</tex># Объединим регулярные выражения, соответствующие одинаковым нетерминалам:#: <tex>S\rightarrow (()\,|\,((?2)(?1))\,|\,((?1)(?2)))\\A\rightarrow ((?4)(?3))\\B\rightarrow ((?1)(?5))\\O\rightarrow (\backslash (\,)\\C\rightarrow (\backslash )\,)</tex># Избавимся от внешних ссылок в регулярном выражении для <tex>S</tex>:{| class="wikitable" style="display: inline-table; white-space: nowrap; text-align: center;"|+Пошаговый вывод! № || Текущее регулярное выражение|-| 1. || <tex>(()\,|\,((\underline{\textbf{?2}})(?1))\,|\,((?1)(\underline{?2})))</tex>|-| 2. || <tex>(()\,|\,(((\underline{\textbf{?4}})(\underline{?3}))(?1))\,|\,((?1)(\underline{?2})))</tex>|-| 3. || <tex>(()\,|\,(((\backslash (\,)(\underline{\textbf{?3}}))(?1))\,|\,((?1)(\underline{?2})))</tex>|-| 4. || <tex>(()\,|\,(((\backslash (\,)((?1)(\underline{\textbf{?5}})))(?1))\,|\,((?1)(\underline{?2})))</tex>|-| 5. || <tex>(()\,|\,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?1)(\underline{\textbf{?2}})))</tex>|-| 6. || <tex>(()\,|\,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?1)(?4)))</tex>|}{| class="wikitable" style="display: inline-table; white-space: nowrap; text-align: center;" |+№ группы в <tex>S</tex>! <tex>S</tex> || <tex>A</tex> || <tex>B</tex> || <tex>O</tex> || <tex>C</tex>|-| 1 || style="background: #1b5de2; color: white;" | || || || |-| 1 || <b>4</b> || || style="background: #1b5de2; color: white;" | || |-|-| 1 || 4 || style="background: #1b5de2; color: white;" | || <b>5</b> || |-| 1 || 4 || <b>6</b> || 5 || style="background: #1b5de2; color: white;" ||-| 1 || style="background: #1b5de2; color: white;" | 4 || 6 || 5 || <b>7</b>|-| 1 || 4 || 6 || 5 || 7|}

Таким образом, регулярное выражение для данной грамматики будет выглядеть так: <tex>S(()\rightarrow A,|\,(((\Abackslash (\rightarrow,)((?1)(\varepsilonbackslash )\,)))(?1))\A,|\rightarrow BA\\B\rightarrow b\\B\rightarrow c,((?1)(?4))).</tex>

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

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