O que são grupos de equilíbrio de expressão regular?

Eu estava lendo uma pergunta sobre como obter dados entre chaves duplas ( esta pergunta ), e então alguém mencionou grupos de equilíbrio. Ainda não tenho certeza do que são e como usá-los.

Eu li a Definição do Grupo de Balanceamento , mas a explicação é difícil de acompanhar e ainda estou bastante confuso com as perguntas que mencionei.

Alguém poderia simplesmente explicar o que são grupos de equilíbrio e como eles são úteis?

Até onde eu sei, os grupos de balanceamento são exclusivos do tipo regex do .NET.

À parte: grupos repetidos

Primeiro, você precisa saber que o .NET é (novamente, até onde eu sei) o único tipo de regex que permite acessar várias capturas de um único grupo de captura (não em referências anteriores, mas após a conclusão da correspondência).

Para ilustrar isso com um exemplo, considere o padrão

(.)+

e a corda "abcd".

em todos os outros sabores de regex, a captura de grupo 1simplesmente produzirá um resultado: d(observe, a correspondência completa será abcdcomo o esperado). Isso ocorre porque cada novo uso do grupo de captura sobrescreve a captura anterior.

O .NET, por outro lado, lembra de todos eles. E faz isso em uma pilha. Depois de combinar o regex acima, como

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

Vai descobrir que

m.Groups[1].Captures

É um CaptureCollectioncujos elementos correspondem às quatro capturas

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

onde o número é o índice no CaptureCollection. Então, basicamente, toda vez que o grupo é usado novamente, uma nova captura é colocada na pilha.

Fica mais interessante se estivermos usando grupos de captura nomeados. Como o .NET permite o uso repetido do mesmo nome, poderíamos escrever um regex como

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

para capturar duas palavras no mesmo grupo. Novamente, toda vez que um grupo com um determinado nome é encontrado, uma captura é colocada em sua pilha. Então, aplicando esta regex à entrada "foo bar"e inspecionando

m.Groups["word"].Captures

encontramos duas capturas

0: "foo"
1: "bar"

Isso nos permite até mesmo colocar coisas em uma única pilha de diferentes partes da expressão. Mas, ainda assim, este é apenas o recurso do .NET de ser capaz de rastrear várias capturas que estão listadas aqui CaptureCollection. Mas eu disse, essa coleção é uma pilha . Então, podemos tirar coisas dele?

Entrar: Grupos de Balanceamento

Acontece que podemos. Se usarmos um grupo como (?<-word>...), a última captura é retirada da pilha wordse a subexpressão ...corresponder. Então, se mudarmos nossa expressão anterior para

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

Então o segundo grupo irá estourar a captura do primeiro grupo, e nós receberemos um vazio CaptureCollection no final. Claro, este exemplo é bastante inútil.

Mas há mais um detalhe na sintaxe de menos: se a pilha já estiver vazia, o grupo falha (independentemente de seu subpadrão). Podemos alavancar esse comportamento para contar os níveis de aninhamento - e é daí que vem o nome do grupo de balanceamento (e de onde fica interessante). Digamos que queremos combinar strings que estão corretamente entre parênteses. Empurramos cada parêntese de abertura na pilha e exibimos uma captura para cada parêntese de fechamento. Se encontrarmos muitos parênteses de fechamento, ele tentará estourar uma pilha vazia e fará com que o padrão falhe:

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

Portanto, temos três alternativas em uma repetição. A primeira alternativa consome tudo o que não seja um parêntese. A segunda alternativa corresponde a (s enquanto os empurra para a pilha. A terceira alternativa corresponde a )s enquanto remove elementos da pilha (se possível!).

_{Nota: Apenas para esclarecer, estamos apenas verificando se não há parênteses incompatíveis! Isso significa que a string não contém parênteses vai combinar, porque eles ainda são sintaticamente válido (em alguns sintaxe, onde você precisa de seus parênteses à partida). Se você quiser garantir pelo menos um conjunto de parênteses, basta adicionar um lookahead (?=.*[(])logo após o ^.}

No entanto, esse padrão não é perfeito (ou totalmente correto).

Final: Padrões Condicionais

Há mais um problema: isso não garante que a pilha esteja vazia no final da string (portanto, (foo(bar)seria válida). .NET (e muitos outros sabores) tem mais uma construção que nos ajuda aqui: padrões condicionais. A sintaxe geral é

(?(condition)truePattern|falsePattern)

onde o falsePatterné opcional - se for omitido, o caso falso sempre corresponderá. A condição pode ser um padrão ou o nome de um grupo de captura. Vou me concentrar no último caso aqui. Se for o nome de um grupo de captura, truePatternserá usado se e somente se a pilha de captura para aquele grupo específico não estiver vazia. Ou seja, um padrão condicional como (?(name)yes|no)lê "se namecombinou e capturou algo (que ainda está na pilha), use o padrão, yescaso contrário, use o padrão no".

Portanto, no final do nosso padrão acima, poderíamos adicionar algo como (?(Open)failPattern)que faz com que todo o padrão falhe, se a Openpilha não estiver vazia. A coisa mais simples para fazer o padrão falhar incondicionalmente é (?!)(um lookahead negativo vazio). Portanto, temos nosso padrão final:

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

Observe que essa sintaxe condicional não tem nada a ver com grupos de balanceamento, mas é necessário aproveitar todo o seu poder.

A partir daqui, o céu é o limite. Muitos usos muito sofisticados são possíveis e há alguns truques quando usados ​​em combinação com outros recursos .NET-Regex como lookbehinds de comprimento variável ( que eu tive que aprender da maneira mais difícil ). A principal questão, entretanto, é sempre: seu código ainda pode ser mantido ao usar esses recursos? Você precisa documentar muito bem e certificar-se de que todos que trabalham nele também estão cientes desses recursos. Caso contrário, você pode se sair melhor, apenas percorrendo a string manualmente, caractere por caractere, e contando os níveis de aninhamento em um inteiro.

Adendo: O que há com o (?<A-B>...) sintaxe?

Os créditos por esta parte vão para Kobi (veja sua resposta abaixo para mais detalhes).

Agora, com todos os itens acima, podemos validar se uma string está corretamente entre parênteses. Mas seria muito mais útil se pudéssemos realmente obter capturas (aninhadas) para o conteúdo de todos os parênteses. Claro, poderíamos nos lembrar de abrir e fechar parênteses em uma pilha de captura separada que não é esvaziada e, em seguida, fazer alguma extração de substring com base em suas posições em uma etapa separada.

Mas o .NET fornece mais um recurso de conveniência aqui: se usarmos (?<A-B>subPattern), não apenas uma captura é removida da pilha B, mas também tudo entre essa captura suspensa Be este grupo atual é colocado na pilha A. Portanto, se usarmos um grupo como este para fechar os parênteses, ao retirar os níveis de aninhamento de nossa pilha, também podemos enviar o conteúdo do par para outra pilha:

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

_{Kobi forneceu esta demonstração ao vivo em sua resposta}

Então, juntando todas essas coisas, podemos:

• Lembre-se de muitas capturas arbitrariamente
• Validar estruturas aninhadas
• Capture cada nível de aninhamento

Tudo em uma única expressão regular. Se isso não for emocionante ...;)

Alguns recursos que achei úteis quando os conheci:

• http://blog.stevenlevithan.com/archives/balancing-groups
• MSDN sobre grupos de balanceamento
• MSDN sobre padrões condicionais
• http://kobikobi.wordpress.com/tag/balancing-group/ (um pouco acadêmico, mas tem algumas aplicações interessantes)

Apenas um pequeno acréscimo à excelente resposta de M. Buettner:

Qual é o problema com a (?<A-B>)sintaxe?

(?<A-B>x)é sutilmente diferente de (?<-A>(?<B>x)). Eles resultam no mesmo fluxo de controle ^* , mas capturam de forma diferente.
Por exemplo, vamos examinar um padrão para chaves balanceadas:

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

No final da partida, temos uma string balanceada, mas é tudo o que temos - não sabemos onde estão as chaves porque a Bpilha está vazia. O trabalho árduo que o motor fez por nós acabou.
_{( exemplo em Regex Storm )}

(?<A-B>x)é a solução para esse problema. Quão? Ele não capturar xem $A: ele captura o conteúdo entre a captura anterior Be a posição atual.

Vamos usá-lo em nosso padrão:

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

Isso seria capturado nas $Contentcordas entre as chaves (e suas posições), para cada par ao longo do caminho.
Para a cadeia {1 2 {3} {4 5 {6}} 7}haveria quatro capturas: 3, 6, 4 5 {6}, e 1 2 {3} {4 5 {6}} 7- muito melhor do que nada ou } } } }.
_{( exemplo - clique na tableguia e veja as ${Content}capturas )}

Na verdade, ele pode ser usado sem qualquer equilíbrio: (?<A>).(.(?<Content-A>).)captura os dois primeiros personagens, mesmo que eles estejam separados por grupos.
(um lookahead é mais comumente usado aqui, mas nem sempre é dimensionado: pode duplicar sua lógica.)

(?<A-B>)é um recurso forte - dá a você controle exato sobre suas capturas. Lembre-se disso quando estiver tentando obter mais do seu padrão.