Изменения

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

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

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

Для повторного использования '''регулярного выражения''' группы используется обозначение <tex>(?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://ru.wikipedia.org/wiki/Экранирование_символов экранировать].

# Регулярное выражение <tex>(aba?)c(?1)\,</tex> породит язык <tex>L=\{abcab,abacab,abcaba,abacaba\}.\;</tex># Выразим язык тандемных повторов над алфавитом Для сравнения, запишем эквивалентное регулярное выражение без использования механизма обратных ссылок: <tex>\Sigma=\{0,1\},(aba?)c(aba?).</tex> используя механизм обратных ссылок:#: <tex>L=((0\,|\,1)a^∗*)\backslash 1.\,</tex>#: Данный язык не является [[Регулярные языки: два определения и их эквивалентность|регулярным]]Данное регулярное выражение будет допускать только слова, однако его можно представить с помощью регулярных выражений с использованием обратных ссылокв которых количество букв <tex>a</tex> чётно.# Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины <tex>n=2\cdot m\,</tex> или <tex>\,n=2\cdot m+1</tex> над алфавитом <tex>\Sigma=\{0,1\}</tex>:#* для чётного <tex>n</tex>: <tex>\;\underbrace{(a_10\,|\,1)(a_20\,|\,1)(a_30\,|\,1)\dotsc(a_m0\,|\,1)}_{m}\,\backslash m\dotsc\backslash 3\backslash 2\backslash 1;</tex>#* для нечётного <tex>n</tex>: <tex>\;\underbrace{(a_10\,|\,1)(a_20\,|\,1)(a_30\,|\,1)\dotsc(a_m0\,|\,1)a_}_{m+}\,(0\,|\,1})\backslash m\dotsc\backslash 3\backslash 2\backslash 1,\;</tex> #: где <tex>a_i</tex> – любой одиночный символ.

#: <tex>(?1)</tex> ссылается на первую группу {{---}} <tex>(a(?1)?b)</tex>, что равносильно рекурсивной зависимости:

<tex>A\rightarrow BC\leftrightarrow A=\rightarrow ((?1n_B)\,(?2n_C)),\,</tex> где <tex>1(?n_B)</tex> и <tex>2(?n_C)</tex> соответствуют нетерминалам <tex>B</tex> и <tex>C</tex>;

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

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

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

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

<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>(((bc)(a))\,|\,c((d)(?4))\,|\,((?13)(b))\,|\,((e)(?8))?).</tex>

Другой Рассмотрим другой пример:

<tex>S\rightarrow AB\\S\rightarrow\varepsilon\\AS\rightarrow SS(S)S\\BS\rightarrow CD\\C\rightarrow c\\D\rightarrow dS(S)</tex>

Допустим, группа # Приведём её к нормальной форме Хомского:#: <tex>№1S\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>№2</tex> и <tex>№5</tex> {{---}} нетерминалы <tex>A</tex> и <tex>D</tex> соответственно. # Для каждого нетерминала составим регулярное выражениеКаждое правило представим в виде регулярного выражения с обратными ссылками:#: <tex>S\leftrightarrow rightarrow ()\\S\rightarrow ((?2)(?31))\\S\leftrightarrow\varepsilonrightarrow ((?1)(?2))\\A\leftrightarrow rightarrow ((?14)(?13))\\B\leftrightarrow rightarrow ((?41)(?5))\\O\rightarrow (\backslash (\,)\\C\leftrightarrow crightarrow (\backslash )\D\leftrightarrow d,)</tex>

#: <tex>S\leftrightarrow rightarrow (()\,|\,((?2)(?31))\,|\,\varepsilon((?1)(?2)))\\A\leftrightarrow rightarrow ((?14)(?13))\\B\leftrightarrow rightarrow ((?41)(?5))\\O\rightarrow (\backslash (\,)\\C\leftrightarrow crightarrow (\backslash )\D\leftrightarrow d,)</tex># Искомое регулярное выражение соответствует нетерминалу Избавимся от внешних ссылок в регулярном выражении для <tex>S,\,</tex> однако оно ссылается на группы, отличные от :{| class="wikitable" style="display: inline-table; white-space: nowrap; text-align: center;"|+Пошаговый вывод! № || Текущее регулярное выражение|-| 1. || <tex>S.(()\,|\,((\underline{\textbf{?2}})(?1))\,|\,((?1)(\underline{?2})))</tex> Будем рекурсивно заменять такие ссылки на сами регулярные выражения до тех пор, пока в исходном регулярном выражении не останутся только терминалы и ссылки на стартовый нетерминал |-| 2. || <tex>S(()\,|\,(((\underline{\textbf{?4}})(\underline{?3}))(?1))\,|\,((?1)(\underline{?2})))</tex>:#: |-| 3. || <tex>(()\,|\,(((\backslash (\,)(\underline{\textbf{?23}}))(?31))\,|\,((?1)(\varepsilonunderline{?2})))</tex>|-| 4. || <tex>(()\rightarrow,|\,(((\backslash (\,)((?1)(\underline{\textbf{?15}})))(?31))\,|\,((?1)(\varepsilonunderline{?2})))</tex>|-| 5. || <tex>(()\,|\rightarrow,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?41)(\underline{\textbf{?52}})))</tex>|-| 6. || <tex>(()\,|\,(((\varepsilonbackslash (\,)\rightarrow((?1)(\backslash )\,)))(?1))\,|\,((?1)c(?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>(()\,|\,(((\varepsilonbackslash (\,)\rightarrow(((?1)(\backslash )\,)))(?1)cd)\,|\,\varepsilon((?1)(?4))).</tex>

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