Как сопоставлять вложенные скобки и сбалансированные теги с помощью балансирующих групп в .NET Regex

Короткий ответ: в .NET каждая группа захвата хранит стек своих захватов, а балансирующая группа позволяет класть в этот стек и снимать с него значения прямо из шаблона. (?<depth>) кладёт значение на открывающей скобке, (?<-depth>) снимает на закрывающей, а условие (?(depth)(?!)) в конце обрывает сопоставление, если в стеке что-то осталось. Вместе это даёт шаблон \((?>[^()]+|\((?<depth>)|\)(?<-depth>))*(?(depth)(?!))\), который сопоставляет одну полную, произвольно вложенную группу в скобках. Все примеры ниже запускались на .NET 11 RC1 (11.0.100-rc.1.26425.128), но эта возможность живёт в System.Text.RegularExpressions без изменений со времён .NET Framework 1.0, так что шаблоны работают и на .NET 8, 9 и 10.

Большинство движков регулярных выражений на это вообще не способны. Классические регулярные выражения описывают регулярные языки, а “сбалансированные скобки” это хрестоматийный пример нерегулярного языка: нужен счётчик, а у конечного автомата его нет. PCRE и Perl решают задачу рекурсией ((?R)). .NET пошёл другим путём и дал вам стек напрямую. Стоит увидеть этот стек, и синтаксис перестаёт выглядеть как шум в строке.

Почему и \(.*\), и \(.*?\) дают неверный результат

Возьмём входную строку f(a(b)c) + g(d) и два шаблона, к которым все тянутся в первую очередь:

// .NET 11, C# 14
using System.Text.RegularExpressions;

var input = "f(a(b)c) + g(d)";

Console.WriteLine(Regex.Match(input, @"\(.*\)").Value);
// (a(b)c) + g(d)    greedy: runs to the LAST ')'

Console.WriteLine(Regex.Match(input, @"\(.*?\)").Value);
// (a(b)             lazy: stops at the FIRST ')'

Ни один не находит “соответствующую )”. Жадный захватывает две отдельные группы, ленивый разрезает вложенную группу пополам. На самом деле нужна “та ), на которой разность числа открытий и закрытий возвращается к нулю”, а для этого требуется счёт. Именно этот счётчик и дают балансирующие группы.

Как группа захвата .NET превращается в стек

Когда именованная группа участвует в сопоставлении более одного раза (например, внутри цикла *), .NET не выбрасывает прежние захваты. Match.Groups["name"].Captures хранит их все по порядку, а движок считает последний захват вершиной стека. Поэтому обратные ссылки вроде \k<name> всегда видят последний захват.

Синтаксис балансирующих групп управляет этим стеком:

Формы с одинарными кавычками (?'open'), (?'-open') и (?'inner-open') идентичны; они нужны, чтобы писать шаблоны в атрибутах XML без экранирования угловых скобок. Нумерованные группы тоже работают: (?<-1>\)) снимает значение со стека группы 1.

Одно правило на этапе разбора: группа, из которой вы снимаете значение, должна существовать где-то в шаблоне. Один лишь ^\)(?<-d>) бросает RegexParseException: Reference to undefined group name 'd' из конструктора Regex, а не просто даёт неудачное сопоставление.

Сопоставление одной сбалансированной группы скобок по шагам

Вот канонический шаблон, записанный с RegexOptions.IgnorePatternWhitespace, чтобы в нём можно было оставить комментарии:

// .NET 11, C# 14
using System.Text.RegularExpressions;

var balanced = new Regex(@"
    \(                      # the outer opening paren
    (?>
        [^()]+              # a run of anything that is not a paren
      | \( (?<depth>)       # an inner '(' pushes onto 'depth'
      | \) (?<-depth>)      # an inner ')' pops 'depth' (fails if empty)
    )*
    (?(depth)(?!))          # if 'depth' is not empty, fail
    \)                      # the outer closing paren
", RegexOptions.IgnorePatternWhitespace);

foreach (Match m in balanced.Matches("f(a(b)c) + g(d) + h((x)"))
    Console.WriteLine($"{m.Value} @{m.Index}");

// (a(b)c) @1
// (d) @12
// (x) @20

Разберём (a(b)c):

1. Литерал \( потребляет внешнюю (. Стек depth пуст.
2. [^()]+ потребляет a.
3. Внутренняя ( попадает во вторую альтернативу, и (?<depth>) кладёт захват. Глубина равна 1.
4. [^()]+ потребляет b.
5. ) попадает в третью альтернативу, и (?<-depth>) снимает значение. Глубина равна 0.
6. [^()]+ потребляет c.
7. Последнюю ) забрала бы третья альтернатива, но стек пуст, поэтому (?<-depth>) не срабатывает. Цикл завершается и возвращает эту ).
8. (?(depth)(?!)) видит пустой стек и не выбирает ни одной ветки, так что условие выполняется.
9. Литерал \) потребляет внешнюю ). Совпадение найдено.

Шаг 7 самый тонкий. Именно отказ снятия значения с пустого стека не даёт циклу съесть внешнюю закрывающую скобку, поэтому шаблон естественным образом останавливается на правильной ).

Обратите внимание на последнюю входную строку, h((x). Первая ( так и не закрывается, поэтому сопоставление не может начаться с неё. Движок идёт дальше, начинает со второй ( и возвращает корректную (x) с индексом 20. Обычно это именно то, что нужно при поиске полных групп в тексте.

Почему проверка (?(depth)(?!)) обязательна

Соблазнительно убрать условие, потому что внешние \(...\) вроде бы уже ограничивают шаблон. Это не так. Сравним два шаблона на ((a):

// .NET 11, C# 14
var noCheck   = new Regex(@"\((?>[^()]+|\((?<d>)|\)(?<-d>))*\)");
var withCheck = new Regex(@"\((?>[^()]+|\((?<d>)|\)(?<-d>))*(?(d)(?!))\)");

Console.WriteLine(noCheck.Match("((a)").Value);    // ((a)   unbalanced!
Console.WriteLine(withCheck.Match("((a)").Value);  // (a)

Без проверки внешняя \( берёт первую (, цикл кладёт в стек вторую (, потребляет a и снимает значение на ). Теперь завершающей \) нечего сопоставлять, поэтому движок откатывается: цикл возвращает последнюю итерацию (отменяя снятие), и завершающая \) забирает эту ). Сопоставление завершается успешно, а одна ( остаётся в стеке. Стек гарантирует лишь “не закрывать больше, чем открыто”. Требование “закрыть всё открытое” выполняет условие.

Проверка, что вся строка сбалансирована

Чтобы ответить на вопрос “сбалансирована ли эта строка?”, а не “найти в ней сбалансированные группы”, закрепите оба конца и уберите внешние литералы скобок:

// .NET 11, C# 14
var valid = new Regex(@"^(?>[^()]+|\((?<d>)|\)(?<-d>))*(?(d)(?!))$");

foreach (var s in new[] { "a(b(c)d)e", "a(b(c)d", "a)b(c", "", "())(" })
    Console.WriteLine($"'{s}': {valid.IsMatch(s)}");

// 'a(b(c)d)e': True
// 'a(b(c)d': False    one '(' left on the stack
// 'a)b(c': False      ')' with an empty stack
// '': True
// '())(': False

Захват содержимого между каждой сопоставленной парой

Форма с двумя именами (?<inner-open>\)) снимает значение с open и записывает текст между снятой ( и текущей ) как захват группы inner. Вы получаете содержимое каждого уровня вложенности, начиная с самого внутреннего:

// .NET 11, C# 14
var inner = new Regex(@"(?>[^()]+|(?<open>\()|(?<inner-open>\)))*(?(open)(?!))");

Match m = inner.Match("x(a(b)c)(d)");
foreach (Capture c in m.Groups["inner"].Captures)
    Console.WriteLine($"{c.Value} @{c.Index}");

// b @4
// a(b)c @2
// d @9

Порядок соответствует порядку, в котором пары закрываются, поэтому b идёт раньше a(b)c. Если нужны только самые внешние группы, отфильтруйте захваты, проверяя, что диапазон никакого другого захвата не содержит текущий, либо вернитесь к шаблону с одной группой из предыдущего раздела и используйте Matches.

Сопоставление вложенных тегов <div>

Та же структура работает для любой пары разделителей, в том числе многосимвольных. Меняется только ветка “всё остальное”: вместо класса символов используйте (?!</?div\b)., чтобы она потребляла по одному символу, но никогда не начало открывающего или закрывающего тега div.

// .NET 11, C# 14
var divs = new Regex(@"
    <div\b[^>]*>
    (?>
        <div\b[^>]*>  (?<depth>)
      | </div>        (?<-depth>)
      | (?!</?div\b) .
    )*
    (?(depth)(?!))
    </div>",
    RegexOptions.IgnorePatternWhitespace | RegexOptions.Singleline | RegexOptions.IgnoreCase);

var html = "<p>x</p><div class=\"a\">1<div>2</div>3</div><div>4</div>";
foreach (Match m in divs.Matches(html))
    Console.WriteLine(m.Value);

// <div class="a">1<div>2</div>3</div>
// <div>4</div>

RegexOptions.Singleline здесь важен: без него . не сопоставляется с \n, и шаблон молча не срабатывает на любом div, занимающем несколько строк.

Это годится для шаблонных фрагментов, вывода журналов или разметки, которую вы генерируете сами. Но это не HTML-парсер. Комментарии с <div>, атрибуты со знаком >, CDATA и незакрытые пустые элементы собьют его с толку. Для реального HTML используйте AngleSharp или HtmlAgilityPack.

Подводные камни, с которыми вы столкнётесь

Без атомарной группы получается катастрофический откат

(?>...) вокруг альтернации это не украшение. Если написать (?:...) и [^()]* вместо [^()]+, при неудачном сопоставлении движок может разбить последовательность обычных символов экспоненциальным числом способов и перебрать их все, прежде чем сдаться. Я измерил это на .NET 11 RC1 с тайм-аутом сопоставления 2 секунды и входной строкой из 29 символов:

// .NET 11, C# 14
var input = "(" + new string('a', 25) + "(((";
var timeout = TimeSpan.FromSeconds(2);

var bad  = new Regex(@"^\((?:[^()]*|\((?<d>)|\)(?<-d>))*(?(d)(?!))\)$", RegexOptions.None, timeout);
var good = new Regex(@"^\((?>[^()]+|\((?<d>)|\)(?<-d>))*(?(d)(?!))\)$", RegexOptions.None, timeout);

// bad.IsMatch(input)  -> RegexMatchTimeoutException after 2000 ms
// good.IsMatch(input) -> False in 0 ms

Два исправления, применяйте оба: оберните альтернацию в (?>...), чтобы каждая итерация фиксировала то, что потребила, и используйте + вместо * внутри цикла, чтобы итерация никогда не могла сопоставиться с пустой строкой. Если шаблон работает с недоверенным вводом, также передайте тайм-аут сопоставления или задайте REGEX_DEFAULT_MATCH_TIMEOUT для домена приложения.

RegexOptions.NonBacktracking отвергает балансирующие группы

Движок с линейным временем, появившийся в .NET 7, не имеет стеков, поэтому отвергает такие шаблоны уже в конструкторе:

System.NotSupportedException: RegexOptions.NonBacktracking is not supported in
conjunction with expressions containing: 'balancing group (?<name1-name2>subexpression)
or (?'name1-name2' subexpression)'.

С тем же исключением он отвергает атомарные группы (?>...) и условия по группе захвата (?(name)...), так что переписыванием это не обойти. Если нужно гарантированное линейное время на враждебном вводе, напишите вместо этого цикл со стеком в 15 строк, показанный ниже. Команда OpenTelemetry столкнулась с похожей ловушкой этого движка, о чём рассказывает разбор исправления wildcard NotSupportedException в OpenTelemetry .NET 1.19.1.

[GeneratedRegex] работает без проблем

Генератор исходного кода поддерживает балансирующие группы, атомарные группы и условия, так что эти шаблоны можно перенести на этап компиляции без изменений:

// .NET 11, C# 14
using System.Text.RegularExpressions;

Console.WriteLine(Patterns.Call().Match("call(foo(1, bar(2)), 3);").Value);
// call(foo(1, bar(2)), 3)

static partial class Patterns
{
    [GeneratedRegex(@"\w+\((?>[^()]+|\((?<d>)|\)(?<-d>))*(?(d)(?!))\)")]
    public static partial Regex Call();
}

Если вы ещё не перешли, руководство по замене new Regex(…) на [GeneratedRegex] описывает анализатор и исправление кода, которые сделают это за вас.

Отдельные стеки не гарантируют порядок скобок

Очевидное расширение для (), [] и {} это по одному стеку на каждый тип скобок:

// .NET 11, C# 14
var multi = new Regex(@"^(?>
      [^()\[\]{}]+
    | (?<p>\() | (?<-p>\))
    | (?<b>\[) | (?<-b>\])
    | (?<c>\{) | (?<-c>\})
  )*(?(p)(?!))(?(b)(?!))(?(c)(?!))$", RegexOptions.IgnorePatternWhitespace);

Console.WriteLine(multi.IsMatch("{[()]}"));  // True
Console.WriteLine(multi.IsMatch("(]"));      // False
Console.WriteLine(multi.IsMatch("{[(])}"));  // True   <- wrong

Каждый стек правильно считает свой тип, но между ними нет никакой связи, поэтому {[(])} проходит проверку: ] снимает значение со стека b, хотя последней открытой была (. Чтобы обеспечить правильное чередование, нужно знать, какой тип лежит на вершине единого общего стека, и именно здесь regex перестаёт быть подходящим инструментом. Обычный Stack<char> справляется за один проход, и это легко читать:

// .NET 11, C# 14
static bool IsBalanced(ReadOnlySpan<char> s)
{
    var stack = new Stack<char>();
    foreach (char ch in s)
    {
        switch (ch)
        {
            case '(' or '[' or '{': stack.Push(ch); break;
            case ')': if (!stack.TryPop(out var a) || a != '(') return false; break;
            case ']': if (!stack.TryPop(out var b) || b != '[') return false; break;
            case '}': if (!stack.TryPop(out var c) || c != '{') return false; break;
        }
    }
    return stack.Count == 0;
}

// IsBalanced("{[()]}") -> True
// IsBalanced("{[(])}") -> False

Если на горячем пути нужно лишь найти следующую скобку в длинной строке, SearchValues с IndexOfAny это быстрый способ пропускать участки обычного текста между ними.

Кавычки и экранирование внутри скобок

f("(", x) содержит несбалансированную ( внутри строкового литерала. Чтобы пропускать строки в кавычках, добавьте перед остальными альтернативу, потребляющую строку целиком, например "(?:[^"\\]|\\.)*", и исключите " из класса “всё остальное”: [^()"]+. Каждое дополнительное лексическое правило (комментарии, символьные литералы, дословные строки) это ещё одна альтернатива, и после двух-трёх таких правил рукописный токенизатор проще поддерживать.

Якоря по строкам

Если вы проверяете многострочный ввод с помощью ^...$ и RegexOptions.Multiline, помните, что по умолчанию $ распознаёт только \n. RegexOptions.AnyNewLine в .NET 11 решает случаи с \r\n и разделителями строк Unicode без хаков с \r?.

Когда вообще стоит обращаться к балансирующим группам

Балансирующие группы это правильный инструмент, когда вы уже находитесь в задаче, естественной для regex: поиск и замена по исходным файлам, фильтр журнала, атрибут валидации, диалог поиска в редакторе, принимающий шаблоны .NET. Они позволяют одному выражению обработать вложенность, которая иначе заставила бы писать парсер. Когда нужен порядок между несколькими типами скобок, обработка экранирования или позиции ошибок (“неожиданная ) в столбце 14”), пишите цикл. Стек, который вы имитировали внутри regex, в C# занимает одну строку.

Источники

• Grouping constructs: balancing group definitions, MS Learn
• Alternation constructs: conditional matching with a named group, MS Learn
• Regular expression options: NonBacktracking mode, MS Learn
• Backtracking in regular expressions, MS Learn
• .NET regular expression source generators, MS Learn