Коротко — почему плохая идея использовать что-то вроде `/(.)+?/g` для разбора вложенных структур и что лучше использовать.
Проблемы с такими регулярными выражениями
- Нельзя парсить вложенные структуры произвольной глубины: регулярные выражения в JS не поддерживают рекурсию/балансировку, а вложенные структуры — контекстно-свободные (нерегулярные).
- Жадные/ленивые кванттификаторы вводят неоднозначность: `+`, `+?` сами по себе не обеспечивают корректные границы вложений; комбинации приводят к большому числу вариантов для backtracking.
- Катастрофическое backtracking → ReDoS: сложные шаблоны с вложенными квантами (например `(a+)+`) на специально подобранных строках дают экспоненциальную сложность $\mathcal{O}(2^n)$ и могут «повесить» процесс.
- Точка `.` не учитывает границы (например, не совпадает с переводом строки без флага), может захватывать лишнее.
- Глобальный режим `g` + неверные шаблоны могут давать пустые/пересекающиеся совпадения и бесконечные циклы при итерации.
- Без проверки входа и ограничений — уязвимость для DoS и ошибок парсинга (некорректные вложения, повреждённый ввод).
Лучшие альтернативы (безопасно и корректно)
1. Для стандартных форматов — специализированные парсеры:
- JSON: `JSON.parse`.
- XML/HTML: `DOMParser`, `xml2js`, `htmlparser2`, SAX-парсеры.
Эти дают корректный разбор вложенности и защиту от тривиальных ошибок.
2. Для собственных грамматик — полноценные парсер-генераторы / парсер-комбинаторы:
- PEG/парсеры: peg.js, nearley, chevrotain, jison, ANTLR (JS target). Позволяют задать грамматику (включая рекурсивные правила) и генерируют безопасный парсер.
3. Лёгкий ручной разбор (сканер + стек) — если нужно просто извлечь сбалансированные блоки:
- Алгоритм: идти по строке, при встрече открывающего символа увеличивать счётчик/пушить на стек, при закрывающем — уменьшать/поп-поп; при нулевой глубине — завершать фрагмент. Это линейно по времени $O(n)$ и по памяти $O(n)$.
- Минимальный пример (псевдо/JS):
const extract = (s, open='(', close=')') => {
const res = []; let depth = 0, start = -1;
for (let i=0;i<s.length;i++){
if (s[i]===open){ if (depth===0) start=i; depth++; }
else if (s[i]===close){ depth--; if (depth===0) res.push(s.slice(start, i+1)); if (depth<0) throw new Error('unbalanced'); }
}
if (depth!==0) throw new Error('unbalanced');
return res;
};
4. Токенизация + рекурсивный нисходящий парсер (recursive descent): удобен при средней сложности грамматики, прозрачный контроль ошибок и ограничений вложенности.
5. Защита и инструменты:
- Проверять регулярные выражения на уязвимость: npm-пакеты типа safe-regex.
- Ограничивать максимально допустимую длину/глубину ввода и использовать тайм-ауты/контролируемые execution contexts.
- Переписывать проблемные шаблоны, избегая вложенных квантов; в движках с поддержкой атомарных групп/possessive квантов их применять (но в стандартном JS этого нет).
Короткий вывод
- Регулярки (особенно `/(.)+?/g` и подобные) ненадёжны для вложенных структур — возможны логические ошибки и катастрофическое backtracking.
- Для вложенных/рекурсивных структур применяйте реальные парсеры (parser generator, recursive descent, стековый сканер) или специализированные библиотеки (JSON/HTML/XML-парсеры) для безопасности и предсказуемой производительности.