32
правки
Изменения
Нет описания правки
{{Определение
|id=maindef
|definition='''Регулярные выражения с обратными ссылками''' (англ. ''regex with backreferences'') {{---}} одна из разновидностей регулярных выражений, дающая возможность использовать в них слова, принадлежащие некоторой группе (англ. ''capture group'').
}}
Выражение, заключённое в скобки, называется ''группой''. Скобки захватывают текст, сопоставленный регулярным выражением внтури нумерованной группы, который может быть повторно использован с помощью обратной ссылки с указанием номера группы.
Порядок нумерации групп: сначала внешняя, потом вложенные (в порядке обхода в глубину).
==Применение==
С помощью обратных ссылок можно составить регулярные выражения для языка тандемных поворотов и других языков, где требуется “запоминать” части входящих в язык слов.
Регулярные выражения в языках программирования зачастую поддерживают обратные ссылки. На практике их можно использовать, например, для парсинга html-выражений (поиск подстрок, содержащихся в определённых тегах).
==Примеры==
* Запишем регулярное выражение для языка тандемных поворотов над алфавитом <tex>\Sigma=\{0,1\}</tex>:
:<tex>L=((0|1)^∗)\backslash 1,</tex>
:где “<tex>\backslash</tex>” – символ обратной ссылки, который действует на первую группу. Обратная ссылка <tex>\backslash 1</tex> показывает, что после группы <tex>1</tex> {{---}} <tex>((0|1)^∗)</tex> {{---}} должен быть описан тот же текст, что содержится в ней.
:Данный язык не является регулярным, однако его можно представить с помощью регулярных выражений с использованием обратных ссылок.
* Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины <tex>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>.</tex>" – любой одиночный символ.
* Запишем регулярное выражение для языка <tex>L=b^kab^kab^ka</tex>. Данный язык не является ни регулярным, ни контекстно-свободным (по лемме о разрастании), но также легко представим с помощью обратных ссылок:
:<tex>L=(b\{b\}^*a)\backslash 1\backslash 1</tex>
* Язык <tex>L=a^nb^n,\,n>0\,</tex> можно представить при помощи обратных ссылок:
:<tex>L=(a(?1)?b),</tex>
:где <tex>?1</tex> – ссылка, осуществляющая рекурсивный вызов первой группы. Следущий за ссылкой знак вопроса обозначает использование группы <tex>0</tex> или <tex>1</tex> раз, то есть осуществление рекурсивного вызова или его окончание.
==Теорема о КС-языках==
{{Теорема
|id=theorem.
|statement=С помощью механизма обратных ссылок можно представить любой контекстно-свободный язык.
|proof=
По модулю определения контекстно-свободных языков.
Любой КС-язык реализуется с помощью продукций нескольких видов; для каждого из них покажем, что его можно реализовать с использованием регулярных выражений с обратными ссылками.
Рассмотрим один из таких:
<tex>S\to A\\A\to BC\\A\to CD</tex>
Очевидно, что эквивалентным будет выражение <tex>((?B)\,(?C)\,|\,(?C)\,(?D))\,</tex>, где <tex>B, C, D</tex> {{---}} группы.
Аналогично с КС-языком, одна из продукций которого представлена в виде <tex>A\to A...,\,</tex> например, регулярное выражение для языка:
<tex>S\to A\\A\to \varepsilon\\A\to BA\\B\to b\\B\to c</tex>
будет выглядеть так: <tex>((b\,|\,c)\,(?1)?).</tex>
}}
==См. также==
* [[Регулярные языки: два определения и их эквивалентность]]
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
==Источники информации==
* [https://stackoverflow.com/questions/3644266/how-can-we-match-an-bn-with-java-regex/3644267#3644267 Работа с обратными ссылками в Java]
* [https://regexr.com Визуализатор регулярных выражений]
* [https://habr.com/post/171667/ habr.com {{---}} Истинное могущество регулярных выражений]
