Рекурсия в RegEx: как избежать бесконечного цикла и обработать вложенные структуры

Рекурсия в регулярных выражениях долгое время считалась чем-то из разряда магии. Ещё в 2010-х годах большинство разработчиков даже не подозревали, что RegEx-движки могут заходить глубже, чем один уровень вложенности. Сегодня, в 2026 году, рекурсия — это не экзотика, а рабочий инструмент для разбора сбалансированных скобок, вложенных тегов и даже простых грамматик. Но есть нюанс: без чётких условий выхода рекурсия в RegEx превращается в бомбу замедленного действия, которая может положить сервер за секунду.

Недавно на Хабре вышла статья, в которой авторы детально разбирают проблему бесконечной рекурсии и предлагают практичные решения ("Рекурсия в RegEx с условиями выхода"). Разберём, как работает рекурсия внутри регулярных выражений, почему она может «зациклиться» и какие техники помогают держать её под контролем. Без воды, только код и реальные примеры.

Что такое рекурсия в RegEx и зачем она нужна

Классические регулярные выражения (например, в JavaScript или Python-модуле re) не умеют обрабатывать вложенные структуры. Вы не сможете написать шаблон, который найдёт корректно вложенные скобки ((())) — стандартный движок просто не понимает концепции «глубины». Рекурсия добавляет эту возможность.

В PCRE (Perl Compatible Regular Expressions), на котором построены движки PHP, R, и сторонний модуль regex для Python, есть специальные конструкции:

• (?R) — рекурсия на весь шаблон
• (?1), (?2) — рекурсия на первую, вторую группу
• (?&name) — рекурсия на именованную группу

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

\( ( [^()] | (?R) )* \)

Он говорит: найди открывающую скобку, затем любое количество непереносимых символов ИЛИ рекурсивно вызови весь шаблон, затем закрывающую скобку. Красиво, правда? Но здесь скрыта опасность.

Основная проблема: бесконечная рекурсия

Если вы попробуете применить такой шаблон к строке (()), он отработает нормально: на уровне 2 найдёт внутренние скобки и выйдет. А что будет на строке (? Шаблон начнёт разворачивать рекурсию, ожидая закрывающую скобку, и будет уходить всё глубже, пока не кончится стек. В PCRE2 по умолчанию глубина рекурсии ограничена 1000 уровнями — при достижении лимита движок выдаёт ошибку. Но если лимит поднять (а разработчики иногда это делают), можно получить зависание процесса или крах приложения.

Авторы статьи на Хабре приводят пример, когда рекурсивный шаблон без условия выхода приводит к катастрофическому backtracking'у — количество операций растёт экспоненциально, и даже небольшое входное выражение может «подвесить» движок на минуту.

Условия выхода: как остановить рекурсию

Главная идея — заставить рекурсию завершаться, когда дальше рекурсироваться некуда или когда мы достигли некого «терминального» состояния. Есть несколько эффективных приёмов:

1. Отрицательный просмотр вперёд (negative lookahead)

Используйте (?!...), чтобы проверять, что дальше нет символа, который снова запустит рекурсию. Например, для скобок можно запретить рекурсию, если следующий символ тоже открывающая скобка, но мы уже на нужной глубине. На практике это не всегда удобно.

2. Атомарные группы и запрет возврата

Атомарная группа (?>...) запрещает движку откатываться назад. Если рекурсия зашла слишком далеко, атомарная группа не позволит ей «разматываться» — это ограничивает количество возможных путей.

Пример с атомарной обёрткой:

\( ( (?> [^()]+ ) | (?R) )* \)

Здесь (?> [^()]+ ) поглощает все непереносимые символы за один раз, не давая движку пробовать разные варианты. Это снижает вероятность бесконечного backtracking'а, но не решает проблему пустого входа.

3. Условная конструкция (?(condition)yes|no)

Самый надёжный способ — добавить явную проверку: «рекурсировать, только если это не терминальный случай». В PCRE2 можно использовать условные конструкции вместе с рекурсией, например так:

(?P<balanced>\( (?: [^()] | (?P>balanced) )* \) )

Хотя в PCRE нет встроенной проверки на пустоту, можно скомбинировать с просмотром: если после открывающей скобки идёт закрывающая — не рекурсировать. Авторы хабра-статьи предлагают такой шаблон:

\( (?= [^()]* \) ) (?: [^()] | (?R) )* \)

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

Практический пример: разбор вложенных тегов HTML

Возьмём задачу, которая часто встречается на собеседованиях: извлечь содержимое вложенных div-блоков. Разумеется, для полноценного HTML лучше использовать парсеры (BeautifulSoup, lxml), но для быстрой выборки из простого текста рекурсивный RegEx может быть полезен.

Допустим, у нас есть строка:

<div>Привет, <div>мир</div>!</div>

Хотим получить <div>Привет, <div>мир</div>!</div> целиком (внешний блок). Шаблон с рекурсией для PCRE (PHP):

$pattern = '/<div[^>]*> (?: [^<]++

| <(?!/div>) | (?R) )* <\/div>/xs';

Разбираем:
- <div[^>]*> — открывающий тег с атрибутами
- (?: ... )* — содержимое, которое может быть:
- [^<]++ — любой символ кроме < (possessive для скорости)
- <(?!/div>) — открывающий тег <, за которым не следует /div> (другой тег, не закрывающий)
- (?R) — рекурсия на весь шаблон (если встречается вложенный div)
- </div> — закрывающий тег

Условие выхода здесь неявное: если внутри встречается </div> без предшествующего открывающего, шаблон не сматчится — это и есть проверка. Но что будет, если строка содержит <div> без закрывающего? Рекурсия начнётся, движок будет искать </div> и, не найдя, начнёт возвращаться — опять риск бесконечного backtracking'а.

Авторы хабра-статьи предлагают добавить проверку на существование закрывающего тега с помощью lookahead:

$pattern = '/<div[^>]*> 
(?= (?: [^<]++

| <(?!/div>) | (?R) )* <\/div> )
(?: [^<]++

| <(?!/div>) | (?R) )*
    <\/div>/xs';

Сначала lookahead проверяет, что вся последовательность (включая закрывающий тег) существует в строке. Если нет — совпадение не происходит, рекурсия останавливается. Это добавляет один лишний проход, но предотвращает катастрофический сценарий.

Условия выхода в Python (модуль regex)

Стандартный модуль re не поддерживает рекурсию. Но есть библиотека regex от Matthew Barnett (доступна в pip, активно обновляется в 2026 году). Она полностью совместима с PCRE и добавляет синтаксис (?R), (?&name).

Пример на Python:

import regex

# Шаблон для сбалансированных скобок с условием выхода
pattern = r'''\(
    (?= [^()]* \) )   # проверка, что закрывающая скобка есть
    (?: 
        [^()]++ 
        | (?R) 
    )* 
\)
'''

text = "( ( ) )"
match = regex.search(pattern, text, regex.VERBOSE)
print(match.group() if match else "Совпадений нет")

Обратите внимание на (?= [^()]* \) ) — это и есть условие выхода. Без него пустая строка внутри скобок (()) привела бы к тому, что движок попробует рекурсию на пустом месте и начнёт бесконечно вызывать (?R) на пустой совпадении. С проверкой — если закрывающей нет или она «далеко», рекурсия не запускается.

Тренды 2026 года: PCRE2 и безопасность

В 2025–2026 годах вышло несколько обновлений PCRE2 (версия 10.45+), в которых улучшена обработка рекурсивных шаблонов: добавлены новые опции для ограничения backtracking'а и диагностики. На Хабре авторы отмечают, что теперь можно задавать максимальную глубину рекурсии через (*LIMIT_DEPTH=100) внутри шаблона — это работает даже в тех средах, где глобальный лимит не настроен.

Пример:

(*LIMIT_DEPTH=20) \( (?: [^()] | (?R) )* \)

Если глубина превысит 20, движок прекращает рекурсию и сообщает об ошибке (или возвращает «нет совпадения» в зависимости от флагов). Это надёжная защита от «случайного» бесконечного цикла.

Ещё один тренд — использование (?(DEFINE)...) для определения «безопасных» рекурсивных правил. Эта конструкция позволяет объявить группу, которая не будет участвовать в совпадении, но может быть вызвана через (?&name). Условия выхода прописываются внутри DEFINE:

(?(DEFINE)
    (?<balanced> \( (?: [^()] | (?&balanced) )* \) )
)
(?&balanced)

Здесь нет явной проверки на пустоту, но её можно добавить внутрь <balanced>, например с lookahead. Авторы хабра-статьи демонстрируют именно такой подход — он считается самым читаемым и поддерживаемым.

Когда рекурсия в RegEx — зло, а когда — добро

Не стоит думать, что рекурсия в регулярках — универсальное решение. У неё есть серьёзные ограничения:

• Производительность: рекурсия в PCRE — это вызов подпрограммы с сохранением стека. При глубине >100 может быть заметно медленнее простого парсера.
• Отладка: рекурсивные шаблоны сложно читать и тестировать. Одна лишняя скобка — и всё ломается.
• Неполнота: RegEx не является полноценным парсером для контекстно-свободных грамматик. Разбор HTML, JSON или математических формул лучше оставить специализированным инструментам.

Но для задач «достать все сбалансированные фрагменты из строки» или «проверить корректность скобок» рекурсия в RegEx — элегантный и быстрый способ. Особенно если вы используете условия выхода и лимиты, описанные в статье на Хабре.

Заключение

Рекурсия в регулярных выражениях — мощная, но коварная техника. Без правильных условий выхода она превращается в бесконечный источник багов и падений. Ключевые выводы:

• Всегда проверяйте наличие терминального символа (закрывающей скобки/тега) перед запуском рекурсии с помощью lookahead.
• Используйте атомарные группы и possessive quantifiers для сокращения backtracking'а.
• Задавайте лимиты глубины через (*LIMIT_DEPTH) или настройки движка.
• Рассмотрите конструкцию (?(DEFINE)...) для отделения описания рекурсии от её вызова.

Если вы работаете с Python — установите модуль regex вместо стандартного re, когда нужна рекурсия. В PHP, R, Perl рекурсия встроена изначально. А для самых сложных случаев не бойтесь взять настоящий парсер — иногда 20 строк кода на pyparsing работают быстрее и надёжнее любой регулярки.

Подробный разбор с живыми примерами читайте в оригинальной статье: Рекурсия в RegEx с условиями выхода. Она вышла на Хабре в июле 2026 года и содержит готовые шаблоны, которые можно забирать и использовать в своих проектах.