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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
Порядок нумерации групп: сначала внешняя, потом вложенные (в порядке [[Обход в глубину, цвета вершин|обхода в глубину]]).
 
Порядок нумерации групп: сначала внешняя, потом вложенные (в порядке [[Обход в глубину, цвета вершин|обхода в глубину]]).
 
==Применение==
 
==Применение==
С помощью обратных ссылок можно составить регулярные выражения для языка тандемных повторов и других языков, где требуется “запоминать” части входящих в язык слов.
+
С помощью обратных ссылок можно составить регулярные выражения для языка тандемных повторов и других языков, где требуется «запоминать» части входящих в язык слов.
  
 
Регулярные выражения в языках программирования зачастую поддерживают обратные ссылки. На практике их можно использовать, например, для парсинга html-выражений (поиск подстрок, содержащихся в определённых тегах).
 
Регулярные выражения в языках программирования зачастую поддерживают обратные ссылки. На практике их можно использовать, например, для парсинга html-выражений (поиск подстрок, содержащихся в определённых тегах).
Строка 43: Строка 43:
 
Рассмотрим один из таких:
 
Рассмотрим один из таких:
  
<tex>S\to A\\A\to BC\\A\to CD</tex>
+
<tex>S\rightarrow A\\A\rightarrow BC\\A\rightarrow CD</tex>
  
 
Очевидно, что эквивалентным будет выражение <tex>((?B)\,(?C)\,|\,(?C)\,(?D))\,</tex>, где <tex>B, C, D</tex> {{---}} группы.
 
Очевидно, что эквивалентным будет выражение <tex>((?B)\,(?C)\,|\,(?C)\,(?D))\,</tex>, где <tex>B, C, D</tex> {{---}} группы.
  
Аналогично с КС-языком, одна из продукций которого представлена в виде <tex>A\to A...,\,</tex> например, регулярное выражение для языка:
+
Аналогично с КС-языком, одна из продукций которого представлена в виде <tex>A\rightarrow A...,\,</tex> например, регулярное выражение для языка:
  
<tex>S\to A\\A\to \varepsilon\\A\to BA\\B\to b\\B\to c</tex>
+
<tex>S\rightarrow A\\A\rightarrow \varepsilon\\A\rightarrow BA\\B\rightarrow b\\B\rightarrow c</tex>
  
 
будет выглядеть так: <tex>((b\,|\,c)\,(?1)?).</tex>
 
будет выглядеть так: <tex>((b\,|\,c)\,(?1)?).</tex>
  
То есть правила вида <tex>A\to BCD...\,</tex> реализуются при помощи ссылок на соответствующие группы, а для правил вида <tex>A\to A...\,</tex> используется обратная ссылка на ту же самую группу, для которой создаётся правило. При наличии нескольких правил в регулярном выражении пишется логическое «или».
+
То есть правила вида <tex>A\rightarrow BCD...\,</tex> реализуются при помощи ссылок на соответствующие группы, а для правил вида <tex>A\rightarrow A...\,</tex> используется обратная ссылка на ту же самую группу, для которой создаётся правило. При наличии нескольких правил в регулярном выражении пишется логическое «или».
  
 
Таким образом, регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные, а также некоторые [[Иерархия Хомского формальных грамматик|контестно-зависимые]].
 
Таким образом, регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные, а также некоторые [[Иерархия Хомского формальных грамматик|контестно-зависимые]].

Версия 21:29, 12 мая 2018

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

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

Порядок нумерации групп: сначала внешняя, потом вложенные (в порядке обхода в глубину).

Применение

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

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

Примеры

[math]L=((0|1)^∗)\backslash 1,[/math]
где «[math]\backslash[/math]» – символ обратной ссылки, который действует на первую группу. Обратная ссылка [math]\backslash 1[/math] показывает, что после группы [math]1[/math][math]((0|1)^∗)[/math] — должен быть описан тот же текст, что содержится в ней.
Данный язык не является регулярным, однако его можно представить с помощью регулярных выражений с использованием обратных ссылок.
  • Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины [math]n=2\cdot m\,[/math] или [math]\,n=2\cdot m+1[/math]:
  1. для чётного [math]n[/math]: [math]\;(.)(.)(.)...(.)\backslash m...\backslash 3\backslash 2\backslash 1;[/math]
  2. для нечётного [math]n[/math]: [math]\;(.)(.)(.)...(.).\backslash m...\backslash 3\backslash 2\backslash 1,\;[/math]
где «[math].[/math]» – любой одиночный символ.
  • Запишем регулярное выражение для языка [math]L=b^kab^kab^ka[/math]. Данный язык не является ни регулярным, ни контекстно-свободным (по лемме о разрастании), но также легко представим с помощью обратных ссылок:
[math]L=(b\{b\}^*a)\backslash 1\backslash 1[/math]
  • Язык [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]\triangleright[/math]

По определению контекстно-свободного языка, любой КС-язык реализуется с помощью продукций нескольких видов; для каждого из них покажем, что его можно реализовать с использованием регулярных выражений с обратными ссылками.

Рассмотрим один из таких:

[math]S\rightarrow A\\A\rightarrow BC\\A\rightarrow CD[/math]

Очевидно, что эквивалентным будет выражение [math]((?B)\,(?C)\,|\,(?C)\,(?D))\,[/math], где [math]B, C, D[/math] — группы.

Аналогично с КС-языком, одна из продукций которого представлена в виде [math]A\rightarrow A...,\,[/math] например, регулярное выражение для языка:

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

будет выглядеть так: [math]((b\,|\,c)\,(?1)?).[/math]

То есть правила вида [math]A\rightarrow BCD...\,[/math] реализуются при помощи ссылок на соответствующие группы, а для правил вида [math]A\rightarrow A...\,[/math] используется обратная ссылка на ту же самую группу, для которой создаётся правило. При наличии нескольких правил в регулярном выражении пишется логическое «или».

Таким образом, регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные, а также некоторые контестно-зависимые.
[math]\triangleleft[/math]

См. также

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