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

Я только что читал вопрос о том, как поместить данные в двойные фигурные скобки ( этот вопрос ), а затем кто-то поднял группы балансировки. Я до сих пор не совсем понимаю, что это такое и как их использовать.

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

Может ли кто-нибудь просто объяснить, что такое балансирующие группы и чем они полезны?

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

В сторону: повторяющиеся группы

Во-первых, вам нужно знать, что .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. Но я сказал, что эта коллекция - стопка . Так можем ли мы оттуда что- нибудь вытрясти?

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

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

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

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

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

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

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

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

Однако этот паттерн не идеален (или не совсем верен).

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

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

(?(condition)truePattern|falsePattern)

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

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

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

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

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

Приложение: Что с (?<A-B>...) синтаксисом?

Кредиты за эту часть принадлежат Коби (подробнее см. Его ответ ниже).

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

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

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

_{Коби предоставил эту Live-демонстрацию в своем ответе}

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

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

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

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

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

Небольшое дополнение к прекрасному ответу М. Бюттнера:

Что случилось с (?<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>)это сильная особенность - она ​​дает вам точный контроль над вашими снимками. Помните об этом, когда пытаетесь извлечь из своего паттерна больше.