32
правки
Изменения
Правки
Порядок нумерации групп: сначала внешняя, потом вложенные (в порядке [[Обход в глубину, цвета вершин|обхода в глубину]]).
==Примеры==
* Запишем [[Регулярные языки: два определения и их эквивалентность|регулярное выражение]] для языка Выразим язык тандемных повторов над алфавитом <tex>\Sigma=\{0,1\},</tex>используя механизм обратных ссылок:
:<tex>L=((0|1)^∗)\backslash 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>B</tex> и <tex>C</tex>, можно представить первое правило:
<tex>A\rightarrow BC\leftrightarrow A=((?B1)\,(?C2)).,\,</tex> где <tex>1</tex> и <tex>2</tex> соответствуют нетерминалам <tex>B</tex> и <tex>С</tex>;
Второе и третье правила не требуют использования обратных ссылок:
}}
===Примеры преобразования===
Рассмотрим следующую КС-грамматику:
<tex>S\rightarrow A\\A\rightarrow BC\\A\rightarrow CD</tex>
Очевидно, что эквивалентным будет выражение <tex>((?B1)\,(?C2)\,|\,(?C2)\,(?D3))\,</tex>, где группы <tex>1, 2, 3</tex> соответствуют <tex>B, C, D</tex> {{---}} группы.
С помощью обратных ссылок можно составить регулярные выражения для языка тандемных повторов и других языков, где требуется «запоминать» части входящих в язык слов.
Регулярные выражения в языках программирования зачастую поддерживают обратные ссылки. На практике их можно использовать, например, для парсинга <tex>html</tex>-выражений (поиск подстрок, содержащихся в определённых тегах).
==См. также==
* [[Регулярные языки: два определения и их эквивалентность]]
* [https://regexr.com Визуализатор регулярных выражений]
* [https://habr.com/post/171667/ habr.com {{---}} Истинное могущество регулярных выражений]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Базовые понятия о грамматиках]]
