Изменения

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

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

«Пример: <tex>\backslash</tex>» – символ обратной ссылки (англ. ''backreference''ab(cd))(ef), который действует на первую группу. Обратная ссылка </tex>\backslash 1Группа №1 {{---}} </tex> показывает(ab(cd)),\, что после группы <tex>1</tex> группа №2 {{---}} <tex>(abacd),\,</tex> группа №3 {{---}} и символа <tex>c(ef)</tex> должен быть описан тот же текст, что содержится в ней.

Порядок нумерации {{Определение|id=referencedef|definition='''Обратная ссылка''' (англ. ''backreference'') {{---}} механизм повторного использования групп: сначала внешняя, потом вложенные (в порядке или [[Обход в глубинуОсновные определения, цвета вершинсвязанные со строками|обхода в глубинуслов]])группы.==Примеры==* Выразим язык тандемных повторов над алфавитом <tex>\Sigma=\{0,1\},</tex> используя механизм обратных ссылок:}

:Для повторного использования '''слова''' группы используется обозначение <tex>L=((0|1)^∗)\backslash 1n,\,</tex> где <tex>n</tex>{{---}} номер группы.

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

:Для повторного использования '''регулярного выражения''' группы используется обозначение <tex>(?n),\,</tex> где «<tex>n</tex> {{---}} номер группы.Использование круглых скобок обусловленно тем, что <tex>?</tex>» – любой одиночный как управляющий символуже используется.

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

Пример экранирования (в данном случае в качестве символа экранирования используется символ обратной косой черты):Группа <tex>\backslash 1</tex> {{---}} <tex>(b\{b\}^∗a)</tex> {{---}} представляет из себя регулярное выражение для языка <tex>L=b^kaобратная ссылка на первую группу,k>0\,</tex>, последующие за ней обратные ссылки используются для многократного использования ''текста'' группы. Поэтому после «<tex>b^ka</tex>» обязан присутствовать текст «<tex>b^kab^ka</tex>». * Язык <tex>L=a^nb^n,\,n>0backslash\,</tex> можно представить при помощи обратных ссылок: :<tex>L=(a(?backslash 1)?b),</tex> :где «<tex>?1</tex>» – ссылка, осуществляющая рекурсивный вызов первой группы. Следущий за ссылкой знак вопроса обозначает использование группы <tex>0</tex> или <tex>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>A\rightarrow a</tex> <tex>S\rightarrow\varepsilon</tex> Представим каждое из них в виде регулярного выражения с обратными ссылками.

<tex>A\rightarrow a\leftrightarrow A=a;\\S\rightarrow\varepsilon\leftrightarrow S=\varepsilon.</tex>

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

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

Очевидно, что эквивалентным Эквивалентным будет выражение <tex>(((b\,|\,c)\,(?1)?)?).</tex>