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