Регулярные выражения с обратными ссылками — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 21 промежуточная версия 3 участников)
Строка 1: Строка 1:
 +
==Базовые определения==
 +
{{Определение
 +
|id=groupdef
 +
|definition='''Группа''' (англ. ''capture group'') {{---}} часть [[Регулярные языки: два определения и их эквивалентность|регулярного выражения]]. Общепринятое условное обозначение группы {{---}} круглые скобки.
 +
}}
  
== Регулярные выражения с бэкреференсами ==
+
Пример: <tex>aba(ca)ba.\,</tex> В данном регулярном выражении представлена одна группа {{---}} <tex>(ca).</tex>
 +
 
 +
Каждой группе соответствует порядковый номер. Нумерация идёт слева направо: номеру группы соответствует порядковый номер открывающей круглой скобки этой группы в тексте регулярного выражения (исключая случаи, когда скобки являются частью синтаксической конструкции).
 +
 
 +
Пример: <tex>(ab(cd))(ef).</tex> Группа <tex>№1</tex> {{---}} <tex>(ab(cd)),\,</tex> группа <tex>№2</tex> {{---}} <tex>(cd),\,</tex> группа <tex>№3</tex> {{---}} <tex>(ef)</tex>
  
 
{{Определение
 
{{Определение
|id=идентификатор (необязательно), пример: def1.  
+
|id=referencedef
|neat = 1
+
|definition='''Обратная ссылка''' (англ. ''backreference'') {{---}} механизм повторного использования групп или [[Основные определения, связанные со строками|слов]] группы.
|definition=текст
+
}}
 +
 
 +
Для повторного использования '''слова''' группы используется обозначение <tex>\backslash n,\,</tex> где <tex>n</tex> {{---}} номер группы.
 +
 
 +
Пример использования: <tex>((1\,|\,0)^*)\backslash 1.\,</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>\backslash 1</tex> {{---}} обратная ссылка на первую группу, <tex>\backslash\backslash 1</tex> {{---}} слово, состоящее из символа обратной косой черты и единицы.
 +
 
 +
{{Определение
 +
|id=maindef
 +
|definition='''Регулярные выражения с обратными ссылками''' (англ. ''regex with backreferences'') {{---}} регулярные выражения, использующие механизм обратных ссылок.
 +
}}
 +
==Примеры==
 +
# Регулярное выражение <tex>(aba?)c(?1)\,</tex> породит язык <tex>L=\{abcab,abacab,abcaba,abacaba\}.\;</tex> Для сравнения, запишем эквивалентное регулярное выражение без использования механизма обратных ссылок: <tex>(aba?)c(aba?).</tex>
 +
# <tex>(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{(0\,|\,1)(0\,|\,1)(0\,|\,1)\dotsc(0\,|\,1)}_{m}\,\backslash m\dotsc\backslash 3\backslash 2\backslash 1;</tex>
 +
#* для нечётного <tex>n</tex>: <tex>\;\underbrace{(0\,|\,1)(0\,|\,1)(0\,|\,1)\dotsc(0\,|\,1)}_{m}\,(0\,|\,1)\backslash m\dotsc\backslash 3\backslash 2\backslash 1,\;</tex>
 +
# Запишем выражение для языка <tex>L=b^kab^kab^ka,\,k>0.\,</tex> Данный язык не является ни регулярным, ни контекстно-свободным (по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]]), то есть является [[Иерархия Хомского формальных грамматик|контекстно-зависимым]], но также легко представим с помощью обратных ссылок:
 +
#: <tex>L=(bb^*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> раз, то есть осуществление рекурсивного вызова или его окончание.
 +
#: <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)=\dotsc</tex>
 +
#: Очевидно, что все слова из языка <tex>L</tex> удовлетворяют данному регулярному выражению.
 +
==Теорема о КС-языках==
 +
{{Теорема
 +
|id=theorem.
 +
|statement=С помощью механизма обратных ссылок можно представить любой [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный язык]].
 +
|proof=
 +
Любую контекстно-свободную грамматику можно привести к [[Нормальная форма Хомского|нормальной форме Хомского]], следовательно, достаточно доказать, что грамматику, заданную в такой форме, можно преобразовать в регулярное выражение с обратными ссылками. Рассмотрим правила, которые могут содержаться в такой грамматике:
 +
 
 +
<tex>A\rightarrow BC\\A\rightarrow a\\S\rightarrow\varepsilon</tex>
 +
 
 +
Представим каждое из них в виде регулярного выражения с обратными ссылками.
 +
 
 +
Используя ссылки на регулярные выражения, соответствующие нетерминалам <tex>B</tex> и <tex>C</tex>, можно представить первое правило:
 +
 
 +
<tex>A\rightarrow BC\leftrightarrow A\rightarrow ((?n_B)\,(?n_C)),\,</tex> где <tex>(?n_B)</tex> и <tex>(?n_C)</tex> соответствуют нетерминалам <tex>B</tex> и <tex>C</tex>;
 +
 
 +
Второе и третье правила не требуют использования обратных ссылок:
 +
 
 +
<tex>A\rightarrow a\leftrightarrow A\rightarrow (a);\\S\rightarrow\varepsilon\leftrightarrow S\rightarrow ().</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> будет искомым.
 
}}
 
}}
 +
 +
===Пример преобразования===
 +
Рассмотрим следующую КС-грамматику:
 +
 +
<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 (S)S\\S\rightarrow S(S)</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>(()\,|\,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?1)(?4))).</tex>
 +
 +
==Применение==
 +
Регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные грамматики, а также некоторые контекстно-зависимые (например, язык тандемных повторов).
 +
 +
Регулярные выражения в языках программирования зачастую поддерживают обратные ссылки. На практике их можно использовать, например, для парсинга <tex>html</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 {{---}} Истинное могущество регулярных выражений]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Автоматы и регулярные языки]]

Текущая версия на 19:37, 4 сентября 2022

Базовые определения

Определение:
Группа (англ. capture group) — часть регулярного выражения. Общепринятое условное обозначение группы — круглые скобки.


Пример: [math]aba(ca)ba.\,[/math] В данном регулярном выражении представлена одна группа — [math](ca).[/math]

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

Пример: [math](ab(cd))(ef).[/math] Группа [math]№1[/math][math](ab(cd)),\,[/math] группа [math]№2[/math][math](cd),\,[/math] группа [math]№3[/math][math](ef)[/math]


Определение:
Обратная ссылка (англ. backreference) — механизм повторного использования групп или слов группы.


Для повторного использования слова группы используется обозначение [math]\backslash n,\,[/math] где [math]n[/math] — номер группы.

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

Для повторного использования регулярного выражения группы используется обозначение [math](?n),\,[/math] где [math]n[/math] — номер группы. Использование круглых скобок обусловленно тем, что [math]?,[/math] как управляющий символ, уже используется. В данном случае круглые скобки следует воспринимать как общепринятое условное обозначение обратной ссылки; запись [math](?n)[/math] не задаёт группу. Например, в выражении [math](aba)(?1)(caba)(?2)\;[/math] ссылке [math](?2)[/math] будет соответствовать [math](caba),\,[/math] а не [math](?1).[/math]


Обратите внимание, что символы круглых скобок и обратной косой черты являются управляющими. Чтобы использовать их непосредственно как часть слова, их нужно экранировать.

Пример экранирования (в данном случае в качестве символа экранирования используется символ обратной косой черты): [math]\backslash 1[/math] — обратная ссылка на первую группу, [math]\backslash\backslash 1[/math] — слово, состоящее из символа обратной косой черты и единицы.


Определение:
Регулярные выражения с обратными ссылками (англ. regex with backreferences) — регулярные выражения, использующие механизм обратных ссылок.

Примеры

  1. Регулярное выражение [math](aba?)c(?1)\,[/math] породит язык [math]L=\{abcab,abacab,abcaba,abacaba\}.\;[/math] Для сравнения, запишем эквивалентное регулярное выражение без использования механизма обратных ссылок: [math](aba?)c(aba?).[/math]
  2. [math](a^*)\backslash 1.\,[/math] Данное регулярное выражение будет допускать только слова, в которых количество букв [math]a[/math] чётно.
  3. Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины [math]n=2\cdot m\,[/math] или [math]\,n=2\cdot m+1[/math] над алфавитом [math]\Sigma=\{0,1\}[/math]:
    • для чётного [math]n[/math]: [math]\;\underbrace{(0\,|\,1)(0\,|\,1)(0\,|\,1)\dotsc(0\,|\,1)}_{m}\,\backslash m\dotsc\backslash 3\backslash 2\backslash 1;[/math]
    • для нечётного [math]n[/math]: [math]\;\underbrace{(0\,|\,1)(0\,|\,1)(0\,|\,1)\dotsc(0\,|\,1)}_{m}\,(0\,|\,1)\backslash m\dotsc\backslash 3\backslash 2\backslash 1,\;[/math]
  4. Запишем выражение для языка [math]L=b^kab^kab^ka,\,k\gt 0.\,[/math] Данный язык не является ни регулярным, ни контекстно-свободным (по лемме о разрастании), то есть является контекстно-зависимым, но также легко представим с помощью обратных ссылок:
    [math]L=(bb^*a)\backslash 1\backslash 1[/math].
  5. Язык [math]L=a^nb^n,\,n\gt 0\,[/math] можно представить при помощи обратных ссылок:
    [math]L=(a(?1)?b).[/math]
    Следущий за ссылкой [math](?1)[/math] знак вопроса обозначает использование группы [math]0[/math] или [math]1[/math] раз, то есть осуществление рекурсивного вызова или его окончание.
    [math](?1)[/math] ссылается на первую группу — [math](a(?1)?b)[/math], что равносильно рекурсивной зависимости:
    [math](a(?1)?b)=[/math]
    [math]=(a(a(?1)?b)?b)=[/math]
    [math]=(a(a(a(?1)?b)?b)?b)=[/math]
    [math]=(a(a(a(a(?1)?b)?b)?b)?b)=\dotsc[/math]
    Очевидно, что все слова из языка [math]L[/math] удовлетворяют данному регулярному выражению.

Теорема о КС-языках

Теорема:
С помощью механизма обратных ссылок можно представить любой контекстно-свободный язык.
Доказательство:
[math]\triangleright[/math]

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

[math]A\rightarrow BC\\A\rightarrow a\\S\rightarrow\varepsilon[/math]

Представим каждое из них в виде регулярного выражения с обратными ссылками.

Используя ссылки на регулярные выражения, соответствующие нетерминалам [math]B[/math] и [math]C[/math], можно представить первое правило:

[math]A\rightarrow BC\leftrightarrow A\rightarrow ((?n_B)\,(?n_C)),\,[/math] где [math](?n_B)[/math] и [math](?n_C)[/math] соответствуют нетерминалам [math]B[/math] и [math]C[/math];

Второе и третье правила не требуют использования обратных ссылок:

[math]A\rightarrow a\leftrightarrow A\rightarrow (a);\\S\rightarrow\varepsilon\leftrightarrow S\rightarrow ().[/math]

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

Регулярное выражение для данной КС-грамматики соответствует нетерминалу [math]S,\,[/math] однако в нём могут встречаться ссылки на внешние — отличные от [math]S[/math] — группы. Будем обрабатывать такие ссылки, используя метод левостороннего вывода. При обработке очередной ссылки:

  1. если эта ссылка встречается впервые, вместо неё подставим соответствующее регулярное выражение и запомним номер его группы в текущем регулярном выражении;
  2. иначе вместо этой ссылки подставим ссылку на соответствующую группу в текущем регулярном выражении.


После соответствующих замен регулярное выражение для [math]S[/math] будет искомым.
[math]\triangleleft[/math]

Пример преобразования

Рассмотрим следующую КС-грамматику:

[math]S\rightarrow cA\\S\rightarrow dA\\S\rightarrow cB\\S\rightarrow eB\\A\rightarrow a\\B\rightarrow b[/math]


  1. Приведём её к нормальной форме Хомского:
    [math]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[/math]
  2. Каждому нетерминалу поставим в соответствие свой номер:
    [math]S\leftrightarrow 1, A\leftrightarrow 2, B\leftrightarrow 3, C\leftrightarrow 4, D\leftrightarrow 5, E\leftrightarrow 6[/math]
  3. Каждое правило представим в виде регулярного выражения с обратными ссылками:
    [math]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)[/math]
  4. Объединим регулярные выражения, соответствующие одинаковым нетерминалам:
    [math]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)[/math]
  5. Избавимся от внешних ссылок в регулярном выражении для [math]S[/math]:
Пошаговый вывод
Текущее регулярное выражение
1. [math](((\underline{\textbf{?4}})(\underline{?2}))\,|\,((\underline{?5})(\underline{?2}))\,|\,((\underline{?4})(\underline{?3}))\,|\,((\underline{?6})(\underline{?3})))\,[/math]
2. [math](((c)(\underline{\textbf{?2}}))\,|\,((\underline{?5})(\underline{?2}))\,|\,((\underline{?4})(\underline{?3}))\,|\,((\underline{?6})(\underline{?3})))\,[/math]
3. [math](((c)(a))\,|\,((\underline{\textbf{?5}})(\underline{?2}))\,|\,((\underline{?4})(\underline{?3}))\,|\,((\underline{?6})(\underline{?3})))\,[/math]
4. [math](((c)(a))\,|\,((d)(\underline{\textbf{?2}}))\,|\,((\underline{?4})(\underline{?3}))\,|\,((\underline{?6})(\underline{?3})))\,[/math]
5. [math](((c)(a))\,|\,((d)(?4))\,|\,((\underline{\textbf{?4}})(\underline{?3}))\,|\,((\underline{?6})(\underline{?3})))\,[/math]
6. [math](((c)(a))\,|\,((d)(?4))\,|\,((?3)(\underline{\textbf{?3}}))\,|\,((\underline{?6})(\underline{?3})))\,[/math]
7. [math](((c)(a))\,|\,((d)(?4))\,|\,((?3)(b))\,|\,((\underline{\textbf{?6}})(\underline{?3})))\,[/math]
8. [math](((c)(a))\,|\,((d)(?4))\,|\,((?3)(b))\,|\,((e)(\underline{\textbf{?3}})))\,[/math]
9. [math](((c)(a))\,|\,((d)(?4))\,|\,((?3)(b))\,|\,((e)(?8)))\,[/math]
№ группы в [math]S[/math]
[math]S[/math] [math]A[/math] [math]B[/math] [math]C[/math] [math]D[/math] [math]E[/math]
1
1 3
1 4 3
1 4 3 6
1 4 3 6
1 4 3 6
1 4 8 3 6
1 4 8 3 6 10
1 4 8 3 6 10

Напоминание: круглые скобки в записи обратной ссылки являются синтаксической конструкцией и не задают группу.


Таким образом, регулярное выражение для данной грамматики будет выглядеть так: [math](((c)(a))\,|\,((d)(?4))\,|\,((?3)(b))\,|\,((e)(?8))).[/math]


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

[math]S\rightarrow\varepsilon\\S\rightarrow (S)S\\S\rightarrow S(S)[/math]

  1. Приведём её к нормальной форме Хомского:
    [math]S\rightarrow\varepsilon\\S\rightarrow AS\\S\rightarrow SA\\A\rightarrow OB\\B\rightarrow SC\\O\rightarrow (\\C\rightarrow\; )[/math]
  2. Каждому нетерминалу поставим в соответствие свой номер:
    [math]S\leftrightarrow 1, A\leftrightarrow 2, B\leftrightarrow 3, O\leftrightarrow 4, C\leftrightarrow 5[/math]
  3. Каждое правило представим в виде регулярного выражения с обратными ссылками:
    [math]S\rightarrow ()\\S\rightarrow ((?2)(?1))\\S\rightarrow ((?1)(?2))\\A\rightarrow ((?4)(?3))\\B\rightarrow ((?1)(?5))\\O\rightarrow (\backslash (\,)\\C\rightarrow (\backslash )\,)[/math]
  4. Объединим регулярные выражения, соответствующие одинаковым нетерминалам:
    [math]S\rightarrow (()\,|\,((?2)(?1))\,|\,((?1)(?2)))\\A\rightarrow ((?4)(?3))\\B\rightarrow ((?1)(?5))\\O\rightarrow (\backslash (\,)\\C\rightarrow (\backslash )\,)[/math]
  5. Избавимся от внешних ссылок в регулярном выражении для [math]S[/math]:
Пошаговый вывод
Текущее регулярное выражение
1. [math](()\,|\,((\underline{\textbf{?2}})(?1))\,|\,((?1)(\underline{?2})))[/math]
2. [math](()\,|\,(((\underline{\textbf{?4}})(\underline{?3}))(?1))\,|\,((?1)(\underline{?2})))[/math]
3. [math](()\,|\,(((\backslash (\,)(\underline{\textbf{?3}}))(?1))\,|\,((?1)(\underline{?2})))[/math]
4. [math](()\,|\,(((\backslash (\,)((?1)(\underline{\textbf{?5}})))(?1))\,|\,((?1)(\underline{?2})))[/math]
5. [math](()\,|\,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?1)(\underline{\textbf{?2}})))[/math]
6. [math](()\,|\,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?1)(?4)))[/math]
№ группы в [math]S[/math]
[math]S[/math] [math]A[/math] [math]B[/math] [math]O[/math] [math]C[/math]
1
1 4
1 4 5
1 4 6 5
1 4 6 5 7
1 4 6 5 7

Таким образом, регулярное выражение для данной грамматики будет выглядеть так: [math](()\,|\,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?1)(?4))).[/math]

Применение

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

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

См. также

Источники информации