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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Правки)
Строка 7: Строка 7:
 
Каждой группе соответствует порядковый номер. Нумерация идёт слева направо: номеру группы соответствует порядковый номер открывающей круглой скобки этой группы в тексте регулярного выражения.
 
Каждой группе соответствует порядковый номер. Нумерация идёт слева направо: номеру группы соответствует порядковый номер открывающей круглой скобки этой группы в тексте регулярного выражения.
  
Пример: <tex>(ab(cd))(ef).</tex> Группа №1 {{---}} <tex>(ab(cd)),\,</tex> группа №2 {{---}} <tex>(cd),\,</tex> группа №3 {{---}} <tex>(ef)</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>
  
 
{{Определение
 
{{Определение
Строка 32: Строка 32:
 
# Регулярное выражение <tex>(aba?)c(?1)\,</tex> породит язык <tex>L=\{abcab,abacab,abcaba,abacaba\}.</tex>
 
# Регулярное выражение <tex>(aba?)c(?1)\,</tex> породит язык <tex>L=\{abcab,abacab,abcaba,abacaba\}.</tex>
 
# Выразим язык тандемных повторов над алфавитом <tex>\Sigma=\{0,1\},</tex> используя механизм обратных ссылок:
 
# Выразим язык тандемных повторов над алфавитом <tex>\Sigma=\{0,1\},</tex> используя механизм обратных ссылок:
#: <tex>L=((0|1)^∗)\backslash 1.</tex>
+
#: <tex>L=((0\,|\,1)^∗)\backslash 1.</tex>
 
#: Данный язык не является [[Регулярные языки: два определения и их эквивалентность|регулярным]], однако его можно представить с помощью регулярных выражений с использованием обратных ссылок.
 
#: Данный язык не является [[Регулярные языки: два определения и их эквивалентность|регулярным]], однако его можно представить с помощью регулярных выражений с использованием обратных ссылок.
 
# Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины <tex>n=2\cdot m\,</tex> или <tex>\,n=2\cdot m+1</tex>:
 
# Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины <tex>n=2\cdot m\,</tex> или <tex>\,n=2\cdot m+1</tex>:
Строка 68: Строка 68:
 
<tex>A\rightarrow a\leftrightarrow A=a;\\S\rightarrow\varepsilon\leftrightarrow S=\varepsilon.</tex>
 
<tex>A\rightarrow a\leftrightarrow A=a;\\S\rightarrow\varepsilon\leftrightarrow S=\varepsilon.</tex>
  
Если какому-то нетерминалу <tex>A</tex> соответствуют несколько регулярных выражений <tex>r_1, r_2, \dotsc, r_n</tex>, заменить их на одно: <tex>A=((r_1)|(r_2)|\dotsc|(r_n))\,</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> будет искомым.
Строка 81: Строка 81:
  
 
Эквивалентным будет выражение <tex>(((b\,|\,c)\,(?1)?)?).</tex>
 
Эквивалентным будет выражение <tex>(((b\,|\,c)\,(?1)?)?).</tex>
 +
  
 
Другой пример:
 
Другой пример:
Строка 86: Строка 87:
 
<tex>S\rightarrow AB\\S\rightarrow\varepsilon\\A\rightarrow SS\\B\rightarrow CD\\C\rightarrow c\\D\rightarrow d</tex>
 
<tex>S\rightarrow AB\\S\rightarrow\varepsilon\\A\rightarrow SS\\B\rightarrow CD\\C\rightarrow c\\D\rightarrow d</tex>
  
Регулярное выражение для этой грамматики будет выглядеть так: <tex>((?1?1cd)\,|\,\varepsilon).</tex>
+
Допустим, группа <tex>№1</tex> соответствует нетерминалу <tex>S,\,</tex> группы <tex>№2-№5</tex> {{---}} нетерминалам <tex>A-D</tex> соответственно.
 +
# Для каждого нетерминала составим регулярное выражение:
 +
#: <tex>S\leftrightarrow ((?2)(?3))\\S\leftrightarrow\varepsilon\\A\leftrightarrow ((?1)(?1))\\B\leftrightarrow ((?4)(?5))\\C\leftrightarrow c\\D\leftrightarrow d</tex>
 +
# Объединим регулярные выражения, соответствующие одинаковым нетерминалам:
 +
#: <tex>S\leftrightarrow (((?2)(?3))\,|\,\varepsilon)\\A\leftrightarrow ((?1)(?1))\\B\leftrightarrow ((?4)(?5))\\C\leftrightarrow c\\D\leftrightarrow d</tex>
 +
# Искомое регулярное выражение соответствует нетерминалу <tex>S,\,</tex> однако оно ссылается на группы, отличные от <tex>S.</tex> Будем рекурсивно заменять такие ссылки на сами регулярные выражения до тех пор, пока в исходном регулярном выражении не останутся только терминалы и ссылки на стартовый нетерминал <tex>S</tex>:
 +
#: <tex>(((?2)(?3))\,|\,\varepsilon)\rightarrow(((?1)(?1)(?3))\,|\,\varepsilon)\rightarrow(((?1)(?1)(?4)(?5))\,|\,\varepsilon)\rightarrow(((?1)(?1)c(?5))\,|\,\varepsilon)\rightarrow(((?1)(?1)cd)\,|\,\varepsilon).</tex>
 +
 
 +
Таким образом, регулярное выражение для этой грамматики будет выглядеть так: <tex>(((?1)(?1)cd)\,|\,\varepsilon).</tex>
 
==Применение==
 
==Применение==
 
С помощью обратных ссылок можно составить регулярные выражения для языка тандемных повторов и других языков, где требуется «запоминать» части входящих в язык слов.
 
С помощью обратных ссылок можно составить регулярные выражения для языка тандемных повторов и других языков, где требуется «запоминать» части входящих в язык слов.

Версия 20:18, 29 мая 2018

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

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


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

Пример: [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](a^*)\backslash 1.\,[/math] Данное регулярное выражение будет допускать только слова, в которых количество букв [math]a[/math] чётно.

Для повторного использования регулярного выражения группы используется обозначение [math](?n),\,[/math] где [math]n[/math] — номер группы. Использование круглых скобок обусловленно тем, что [math]?[/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]
  2. Выразим язык тандемных повторов над алфавитом [math]\Sigma=\{0,1\},[/math] используя механизм обратных ссылок:
    [math]L=((0\,|\,1)^∗)\backslash 1.[/math]
    Данный язык не является регулярным, однако его можно представить с помощью регулярных выражений с использованием обратных ссылок.
  3. Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины [math]n=2\cdot m\,[/math] или [math]\,n=2\cdot m+1[/math]:
    • для чётного [math]n[/math]: [math]\;(a_1)(a_2)(a_3)\dotsc(a_m)\backslash m\dotsc\backslash 3\backslash 2\backslash 1;[/math]
    • для нечётного [math]n[/math]: [math]\;(a_1)(a_2)(a_3)\dotsc(a_m)a_{m+1}\backslash m\dotsc\backslash 3\backslash 2\backslash 1,\;[/math]
    где [math]a_i[/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=((?1)\,(?2)),\,[/math] где [math]1[/math] и [math]2[/math] соответствуют нетерминалам [math]B[/math] и [math]C[/math];

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

[math]A\rightarrow a\leftrightarrow A=a;\\S\rightarrow\varepsilon\leftrightarrow S=\varepsilon.[/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]\triangleleft[/math]

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

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

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

[math]S\rightarrow A\\A\rightarrow\varepsilon\\A\rightarrow BA\\B\rightarrow b\\B\rightarrow c[/math]

Эквивалентным будет выражение [math](((b\,|\,c)\,(?1)?)?).[/math]


Другой пример:

[math]S\rightarrow AB\\S\rightarrow\varepsilon\\A\rightarrow SS\\B\rightarrow CD\\C\rightarrow c\\D\rightarrow d[/math]

Допустим, группа [math]№1[/math] соответствует нетерминалу [math]S,\,[/math] группы [math]№2-№5[/math] — нетерминалам [math]A-D[/math] соответственно.

  1. Для каждого нетерминала составим регулярное выражение:
    [math]S\leftrightarrow ((?2)(?3))\\S\leftrightarrow\varepsilon\\A\leftrightarrow ((?1)(?1))\\B\leftrightarrow ((?4)(?5))\\C\leftrightarrow c\\D\leftrightarrow d[/math]
  2. Объединим регулярные выражения, соответствующие одинаковым нетерминалам:
    [math]S\leftrightarrow (((?2)(?3))\,|\,\varepsilon)\\A\leftrightarrow ((?1)(?1))\\B\leftrightarrow ((?4)(?5))\\C\leftrightarrow c\\D\leftrightarrow d[/math]
  3. Искомое регулярное выражение соответствует нетерминалу [math]S,\,[/math] однако оно ссылается на группы, отличные от [math]S.[/math] Будем рекурсивно заменять такие ссылки на сами регулярные выражения до тех пор, пока в исходном регулярном выражении не останутся только терминалы и ссылки на стартовый нетерминал [math]S[/math]:
    [math](((?2)(?3))\,|\,\varepsilon)\rightarrow(((?1)(?1)(?3))\,|\,\varepsilon)\rightarrow(((?1)(?1)(?4)(?5))\,|\,\varepsilon)\rightarrow(((?1)(?1)c(?5))\,|\,\varepsilon)\rightarrow(((?1)(?1)cd)\,|\,\varepsilon).[/math]

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

Применение

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

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

См. также

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