Что такое балансировочные группы регулярных выражений?
Я только что прочитал вопрос о том, как получить данные в двойных фигурных скобках ( этот вопрос), а затем кто-то поднял группы балансировки. Я до сих пор не совсем уверен, что они и как их использовать.
Я прочитал " Определение балансирующей группы", но объяснениям трудно следовать, и я все еще запутался в вопросах, которые упомянул.
Может ли кто-нибудь просто объяснить, что такое уравновешивающие группы и чем они полезны?
2 ответа
Насколько я знаю, балансировочные группы уникальны для вкуса регулярных выражений.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, Но я сказал, что эта коллекция - стек. Так можем ли мы извлечь из этого что-нибудь?
Enter: Балансировка групп
Оказывается, мы можем. Если мы используем группу, как (?<-word>...) тогда последний захват извлекается из стека word если подвыражение ... Матчи. Так что если мы изменим наше предыдущее выражение на
(?<word>\w+)\W+(?<-word>\w+)
Затем вторая группа выскочит захват первой группы, и мы получим пустой CaptureCollection в конце. Конечно, этот пример довольно бесполезен.
Но есть еще одна деталь к синтаксису минус: если стек уже пуст, группа не работает (независимо от ее подшаблона). Мы можем использовать это поведение для подсчета уровней вложенности - и вот откуда берется группа балансировки имен (и где она становится интересной). Скажем, мы хотим сопоставить строки, которые правильно заключены в скобки. Мы помещаем каждую открывающую скобку в стек и добавляем один захват для каждой закрывающей скобки. Если мы встретим одну закрывающую скобку слишком много, она попытается вытолкнуть пустой стек и привести к сбою шаблона:
^(?:[^()]|(?<Open>[(])|(?<-Open>[)]))*$
Таким образом, у нас есть три варианта в повторении. Первая альтернатива потребляет все, что не является скобкой. Вторые альтернативные матчи ( с толкая их в стек. Третьи альтернативные матчи ) s при извлечении элементов из стека (если возможно!).
Примечание: просто чтобы уточнить, мы только проверяем, что нет непревзойденных скобок! Это означает, что строка, не содержащая скобок вообще, будет совпадать, потому что они все еще синтаксически допустимы (в некотором синтаксисе, где вам нужно, чтобы ваши скобки соответствовали). Если вы хотите обеспечить хотя бы один набор скобок, просто добавьте заглядывание (?=.*[(]) сразу после ^ ,
Этот образец не идеален (или не совсем корректен).
Финал: условные паттерны
Есть еще один улов: это не гарантирует, что стек является пустым в конце строки (следовательно, (foo(bar) будет действительным). У.NET (и многих других разновидностей) есть еще одна конструкция, которая нам здесь помогает: условные шаблоны. Общий синтаксис
(?(condition)truePattern|falsePattern)
где falsePattern является необязательным - если он опущен, ложный регистр всегда будет совпадать. Условием может быть либо шаблон, либо имя группы захвата. Я сосредоточусь на последнем случае здесь. Если это название группы захвата, то truePattern используется тогда и только тогда, когда стек захвата для этой конкретной группы не пуст. То есть условный паттерн типа (?(name)yes|no) читает "если name сопоставил и захватил что-то (что все еще в стеке), используйте шаблон yes в противном случае используйте шаблон no ".
Таким образом, в конце вышеприведенного шаблона мы могли бы добавить что-то вроде (?(Open)failPattern) что приводит к сбою всего шаблона, если Open стек не пуст. Самая простая вещь, чтобы сделать шаблон безоговорочно неудачным, это (?!) (пустой отрицательный взгляд). Итак, у нас есть наш последний шаблон:
^(?:[^()]|(?<Open>[(])|(?<-Open>[)]))*(?(Open)(?!))$
Обратите внимание, что этот условный синтаксис сам по себе не имеет ничего общего с балансировкой групп, но необходимо использовать их всю мощь.
Отсюда небо - предел. Возможно много очень сложных применений, и есть некоторые ошибки, когда они используются в сочетании с другими функциями.NET-Regex, такими как lookbehinds переменной длины ( которые я должен был выучить трудным путем сам). Главный вопрос, однако, всегда: ваш код по-прежнему поддерживается при использовании этих функций? Вы должны действительно хорошо документировать это, и быть уверенным, что каждый, кто работает над этим, также знает об этих функциях. В противном случае вам может быть лучше, просто пройдя строку вручную посимвольно и посчитав уровни вложенности в целое число.
Приложение: что с (?<A-B>...) синтаксис?
Кредиты для этой части идут к Коби (см. Его ответ ниже для более подробной информации).
Теперь, учитывая все вышесказанное, мы можем проверить, что строка содержит круглые скобки. Но было бы намного полезнее, если бы мы могли получить (вложенные) захваты для содержимого всех этих скобок. Конечно, мы могли бы вспомнить открывающие и закрывающие скобки в отдельном стеке захвата, который не очищен, а затем выполняли некоторое извлечение подстроки на основе их позиций на отдельном шаге.
Но.NET предоставляет еще одну удобную функцию: если мы используем (?<A-B>subPattern), не только захват выскочил из стека B, но и все, что между этим совали захват B и эта текущая группа помещается в стек A, Поэтому, если мы используем такую группу для закрывающих скобок, одновременно извлекая уровни вложенности из нашего стека, мы также можем поместить содержимое пары в другой стек:
^(?:[^()]|(?<Open>[(])|(?<Content-Open>[)]))*(?(Open)(?!))$
Коби представил это Live-Demo в своем ответе
Итак, взяв все эти вещи вместе, мы можем:
- Запомните сколь угодно много снимков
- Проверить вложенные структуры
- Захватить каждый уровень вложенности
Все в одном регулярном выражении. Если это не интересно...;)
Некоторые ресурсы, которые я нашел полезными, когда впервые узнали о них:
- 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>) это сильная особенность - она дает вам точный контроль над вашими снимками. Имейте это в виду, когда вы пытаетесь получить больше от вашего шаблона.