32
правки
Изменения
Правки
{{Определение
|id=maindef
|definition='''Регулярные выражения с обратными ссылками''' (англ. ''regex with backreferences'') {{---}} одна из разновидностей регулярных выражений, дающая возможность использовать в них слова, принадлежащие некоторой группе (англ. ''capture group'').
}}
<tex>(aba)c\backslash 1</tex> {{---}} пример такого регулярного выражения. Выражение, заключённое в скобки, называется ''группой''(англ. ''capture group''). Скобки захватывают текст, сопоставленный регулярным выражением внтури внутри нумерованной группы, который может быть повторно использован с помощью обратной ссылки с указанием номера группы. «<tex>\backslash</tex>» – символ обратной ссылки (англ. ''backreference''), который действует на первую группу. Обратная ссылка <tex>\backslash 1</tex> показывает, что после группы <tex>1</tex> {{---}} <tex>(aba)</tex> {{---}} и символа <tex>c</tex> должен быть описан тот же текст, что содержится в ней.
Порядок нумерации групп: сначала внешняя, потом вложенные (в порядке [[Обход в глубину, цвета вершин|обхода в глубину]]).
==Примеры==
* Запишем [[Регулярные языки: два определения и их эквивалентность|регулярное выражение]] для языка тандемных повторов над алфавитом <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>L=b^kab^kab^ka</tex>. Данный язык не является ни регулярным, ни контекстно-свободным (по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]]), но также легко представим с помощью обратных ссылок:
:<tex>L=(b\{b\}^*a)\backslash 1\backslash 1</tex>. :Группа <tex>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>0\,</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> удовлетворяют данному регулярному выражению.
==Теорема о КС-языках==
|statement=С помощью механизма обратных ссылок можно представить любой [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный язык]].
|proof=
<tex>A\rightarrow BC</tex> <tex>
A\rightarrow a</tex> <tex>
S\rightarrow\varepsilon</tex>
Представим каждое из них в виде регулярного выражения с обратными ссылками.
Используя ссылки на регулярные выражения, соответствующие нетерминалам <tex>B</tex> и <tex>C</tex>, можно представить первое правило:
<tex>A\rightarrow BC\leftrightarrow A=((?B)\,(?C)).\,</tex>
Второе и третье правила не требуют использования обратных ссылок:
<tex>A\rightarrow a\leftrightarrow A=a;</tex>
<tex>S\rightarrow\varepsilon\leftrightarrow S=\varepsilon.</tex> Таким образом, регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные грамматики, а также некоторые [[Иерархия Хомского формальных грамматик|контекстно-зависимые]].}} Рассмотрим один из такихследующую КС-грамматику:
<tex>S\rightarrow A\\A\rightarrow BC\\A\rightarrow CD</tex>
Очевидно, что эквивалентным будет выражение <tex>((?B)\,(?C)\,|\,(?C)\,(?D))\,</tex>, где <tex>B, C, D</tex> {{---}} группы.
Регулярные выражения в языках программирования зачастую поддерживают обратные ссылки. На практике их можно использовать, например, для парсинга html-выражений (поиск подстрок, содержащихся в определённых тегах).
==См. также==
* [[Регулярные языки: два определения и их эквивалентность]]
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
* [[Нормальная форма Хомского]]
* [[Иерархия Хомского формальных грамматик]]
