Что такое сбалансированные группы балансировки?

Ответ 1

Насколько я знаю, балансировочные группы уникальны для .NET regex.

Кроме того: Повторные группы

Во-первых, вам нужно знать, что .NET(опять же, насколько мне известно) является единственным ароматом регулярного выражения, который позволяет вам получать доступ к нескольким захватам одной группы захвата (не в обратном направлении, а после завершения матча).

Чтобы проиллюстрировать это примером, рассмотрим шаблон

(.)+

и строку "abcd".

во всех других вариантах регулярных выражений, группа захвата 1 просто даст один результат: d (обратите внимание, что полный матч, конечно, будет abcd, как ожидалось). Это связано с тем, что каждое новое использование группы захвата перезаписывает предыдущий захват.

.NET, с другой стороны, запоминает их все. И он делает это в стеке. После соответствия вышеуказанному регулярному выражению, например

Match m = new Regex(@"(.)+").Match("abcd");

вы обнаружите, что

m.Groups[1].Captures

Является CaptureCollection, элементы которого соответствуют четырем захватам

0: "a"
1: "b"
2: "c"
3: "d"

где число - это индекс в CaptureCollection. Таким образом, каждый раз, когда группа используется снова, в стек помещается новый захват.

Это становится более интересным, если мы используем именованные группы захвата. Поскольку .NET допускает повторное использование одного и того же имени, мы могли бы написать регулярное выражение, например

(?<word>\w+)\W+(?<word>\w+)

чтобы записать два слова в одну группу. Опять же, каждый раз, когда встречается группа с определенным именем, захват помещается в стек. Поэтому, применяя это регулярное выражение к входу "foo bar" и проверяя

m.Groups["word"].Captures

мы находим два захвата

0: "foo"
1: "bar"

Это позволяет нам даже перемещать вещи в один стек из разных частей выражения. Но все же это просто функция .NET, позволяющая отслеживать несколько захватов, перечисленных в этом CaptureCollection. Но я сказал, что эта коллекция - это стек. Так можем ли мы поп-вещи от него?

Введите: балансировочные группы

Оказывается, мы можем. Если мы используем группу типа (?<-word>...), то последний захват выносится из стека word, если соответствует подвыражение .... Поэтому, если мы изменим наше предыдущее выражение на

(?<word>\w+)\W+(?<-word>\w+)

Затем вторая группа выдает первый групповой захват, и в конце мы получим пустой CaptureCollection. Конечно, этот пример довольно бесполезен.

Но есть еще одна деталь для минус-синтаксиса: если стек уже пуст, группа выходит из строя (независимо от ее подшаблона). Мы можем использовать это поведение для подсчета уровней вложенности - и именно здесь возникает группа балансировки имен (и где она становится интересной). Предположим, что мы хотим сопоставить строки, которые правильно скопированы. Мы выталкиваем каждую открывающую скобку в стек и выбираем один захват для каждой закрывающей круглой скобки. Если мы сталкиваемся с одной закрывающей скобкой слишком много, она попытается выставить пустой стек и вызвать сбой шаблона:

^(?:[^()]|(?<Open>[(])|(?<-Open>[)]))*$

Итак, у нас есть три альтернативы в повторении. Первая альтернатива потребляет все, что не является скобкой. Вторая альтернатива соответствует (, одновременно нажимая их на стек. Третья альтернатива соответствует ) при выталкивании элементов из стека (если это возможно!).

_{Примечание.. Чтобы уточнить, мы проверяем, нет ли совпадающих круглых скобок! Это означает, что строка, содержащая никакие круглые скобки, будет соответствовать, потому что они все еще синтаксически действительны (в некотором синтаксисе, где вам нужны ваши скобки для соответствия). Если вы хотите обеспечить хотя бы один набор круглых скобок, просто добавьте lookahead (?=.*[(]) сразу после ^.}

Этот шаблон не является совершенным (или полностью правильным).

Финал: условные шаблоны

Есть еще один улов: это не гарантирует, что стек пуст в конце строки (следовательно, (foo(bar) будет действительным)..NET(и многие другие варианты) имеют еще одну конструкцию, которая помогает нам здесь: условные шаблоны. Общий синтаксис

(?(condition)truePattern|falsePattern)

где falsePattern является необязательным - если он опущен, false-case всегда будет соответствовать. Условие может быть либо шаблоном, либо именем группы захвата. Здесь я остановлюсь на последнем случае. Если это имя группы захвата, то truePattern используется тогда и только тогда, когда стек захвата для этой конкретной группы не пуст. То есть условный шаблон, такой как (?(name)yes|no), читает "если name что-то сопоставил и что-то захватил (который все еще находится в стеке), используйте шаблон yes иначе используйте шаблон no".

Итак, в конце нашего шаблона мы могли бы добавить что-то вроде (?(Open)failPattern), из-за чего весь шаблон терпит неудачу, если Open -stack не пуст. Простейшей причиной безусловного отказа шаблона является (?!) (пустой отрицательный результат). Итак, у нас есть наш окончательный шаблон:

^(?:[^()]|(?<Open>[(])|(?<-Open>[)]))*(?(Open)(?!))$

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

Отсюда небо - предел. Возможно много очень сложных применений, и есть некоторые ошибки при использовании в сочетании с другими функциями .NET-Regex, такими как переменные длины lookbehinds (которые я должен был усвоить самому себе). Однако главный вопрос: всегда ли ваш код поддерживается при использовании этих функций? Вам нужно документировать его очень хорошо, и убедитесь, что все, кто работает над этим, также знают об этих функциях. В противном случае вам может быть лучше, просто перемещая строку вручную по символу и подсчитывая уровни вложенности в целое число.

Добавление: что с синтаксисом (?<A-B>...)?

Кредиты для этой части идут на Kobi (см. его ответ ниже для более подробной информации).

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

Но .NET предоставляет еще одну удобную функцию: если мы используем (?<A-B>subPattern), это не только захват, полученный из стека B, но и все, что произошло между этим всплывающим захватом B, и эта текущая группа нажата стек A. Поэтому, если мы используем такую ​​группу для закрывающих круглых скобок, одновременно добавляя уровни вложенности из нашего стека, мы также можем подталкивать содержимое пары в другой стек:

^(?:[^()]|(?<Open>[(])|(?<Content-Open>[)]))*(?(Open)(?!))$

_{Kobi предоставил этот Live-Demo в своем ответе}

Итак, взяв все эти вещи вместе, мы можем:

• Помните произвольно много захватов
• Проверять вложенные структуры
• Захват каждого уровня вложенности

Все в одном регулярном выражении. Если это не интересно...;)

Некоторые ресурсы, которые я нашел полезными, когда я впервые узнал о них:

• http://blog.stevenlevithan.com/archives/balancing-groups
• MSDN в группах балансировки
• MSDN для условных шаблонов
• http://kobikobi.wordpress.com/tag/balancing-group/ (немного академический, но имеет несколько интересных приложений)

Ответ 2

Просто небольшое дополнение к М. Буэттнеру отличный ответ:

Что связано с синтаксисом (?<A-B>)?

(?<A-B>x) тонко отличается от (?<-A>(?<B>x)). Они приводят к одному и тому же потоку управления ^* но они различаются по-разному.
Например, рассмотрим шаблон для сбалансированных фигурных скобок:

(?:[^{}]|(?<B>{)|(?<-B>}))+(?(B)(?!))

В конце матча у нас есть сбалансированная строка, но это все, что у нас есть - мы не знаем, где фигурные скобки связаны с тем, что стек B пуст. Тяжелая работа, которую движок сделал для нас, исчез.
_{(пример в Regex Storm)}

(?<A-B>x) является решением этой проблемы. Как? Он не записывает x в $A: он захватывает содержимое между предыдущим захватом B и текущей позицией.

Позвольте использовать его в нашем шаблоне:

(?:[^{}]|(?<Open>{)|(?<Content-Open>}))+(?(Open)(?!))

Это зафиксировало бы в $Content строки между фигурными скобками (и их положениями) для каждой пары по пути.
Для строки {1 2 {3} {4 5 {6}} 7} было бы четыре захвата: 3, 6, 4 5 {6} и 1 2 {3} {4 5 {6}} 7 - намного лучше, чем ничего или } } } }.
_{( пример - перейдите на вкладку table и посмотрите ${Content}, запишите)}

Фактически, его можно использовать без балансировки вообще: (?<A>).(.(?<Content-A>).) фиксирует первые два символа, даже если они разделены группами.
(здесь чаще используется просмотр, но он не всегда масштабируется: он может дублировать вашу логику.)

(?<A-B>) - это сильная функция - она ​​дает вам точный контроль над вашими захватами. Помните об этом, когда вы пытаетесь получить больше от вашего шаблона.