Que sont les groupes d'équilibrage des expressions régulières?

Je lisais juste une question sur la façon d'obtenir des données dans des doubles accolades ( cette question ), puis quelqu'un a évoqué des groupes d'équilibrage. Je ne sais toujours pas ce qu'ils sont et comment les utiliser.

J'ai lu la définition du groupe d'équilibrage , mais l'explication est difficile à suivre, et je suis encore assez confus sur les questions que j'ai mentionnées.

Quelqu'un pourrait-il simplement expliquer ce que sont les groupes d'équilibrage et en quoi ils sont utiles?

Autant que je sache, les groupes d'équilibrage sont uniques à la saveur regex de .NET.

À part: groupes répétés

Tout d'abord, vous devez savoir que .NET est (encore une fois, pour autant que je sache) la seule saveur regex qui vous permet d'accéder à plusieurs captures d'un seul groupe de capture (pas dans les références arrière mais après la fin du match).

Pour illustrer cela avec un exemple, considérons le modèle

(.)+

et la chaîne "abcd".

dans toutes les autres saveurs de regex, la capture de groupe 1donnera simplement un résultat: d(notez que la correspondance complète sera bien sûr abcdcomme prévu). En effet, chaque nouvelle utilisation du groupe de capture remplace la capture précédente.

.NET en revanche se souvient de tous. Et il le fait dans une pile. Après avoir fait correspondre l'expression régulière ci-dessus comme

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

tu trouveras que

m.Groups[1].Captures

Est un CaptureCollectiondont les éléments correspondent aux quatre captures

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

où le nombre est l'index dans le CaptureCollection. Donc, chaque fois que le groupe est à nouveau utilisé, une nouvelle capture est poussée sur la pile.

Cela devient plus intéressant si nous utilisons des groupes de capture nommés. Parce que .NET permet une utilisation répétée du même nom, nous pourrions écrire une expression régulière comme

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

pour capturer deux mots dans le même groupe. Encore une fois, chaque fois qu'un groupe avec un certain nom est rencontré, une capture est poussée sur sa pile. Donc, en appliquant cette expression régulière à l'entrée "foo bar"et en inspectant

m.Groups["word"].Captures

on trouve deux captures

0: "foo"
1: "bar"

Cela nous permet même de pousser les choses sur une seule pile à partir de différentes parties de l'expression. Mais encore, il ne s'agit que de la fonctionnalité .NET de pouvoir suivre plusieurs captures répertoriées dans ce document CaptureCollection. Mais j'ai dit, cette collection est une pile . Alors pouvons-nous en sortir des choses?

Entrez: Groupes d'équilibrage

Il s'avère que nous pouvons. Si nous utilisons un groupe comme (?<-word>...), la dernière capture est extraite de la pile wordsi la sous-expression ...correspond. Donc, si nous changeons notre expression précédente en

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

Ensuite, le deuxième groupe fera apparaître la capture du premier groupe, et nous recevrons un vide CaptureCollectionà la fin. Bien sûr, cet exemple est assez inutile.

Mais il y a un autre détail à la syntaxe moins: si la pile est déjà vide, le groupe échoue (quel que soit son sous-modèle). Nous pouvons tirer parti de ce comportement pour compter les niveaux d'imbrication - et c'est de là que vient le groupe d'équilibrage de noms (et où cela devient intéressant). Disons que nous voulons faire correspondre les chaînes correctement entre parenthèses. Nous poussons chaque parenthèse ouvrante sur la pile et faisons apparaître une capture pour chaque parenthèse fermante. Si nous rencontrons une parenthèse fermante de trop, cela essaiera de faire apparaître une pile vide et provoquera l'échec du modèle:

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

Nous avons donc trois alternatives dans une répétition. La première alternative consomme tout ce qui n'est pas une parenthèse. La deuxième alternative correspond aux (s tout en les poussant sur la pile. La troisième alternative correspond à )s tout en extrayant des éléments de la pile (si possible!).

_{Remarque: Juste pour clarifier, nous vérifions seulement qu'il n'y a pas de parenthèses sans correspondance! Cela signifie que la chaîne ne contenant pas entre parenthèses tout sera match, car ils sont encore syntaxiquement valides (dans une syntaxe où vous avez besoin de vos parenthèses en conséquence ). Si vous souhaitez garantir au moins un jeu de parenthèses, ajoutez simplement une anticipation (?=.*[(])juste après le ^.}

Ce modèle n'est cependant pas parfait (ou entièrement correct).

Finale: Modèles conditionnels

Il y a un autre hic: cela ne garantit pas que la pile est vide à la fin de la chaîne (donc (foo(bar)serait valide). .NET (et de nombreuses autres versions) ont une autre construction qui nous aide ici: les modèles conditionnels. La syntaxe générale est

(?(condition)truePattern|falsePattern)

où le falsePatternest facultatif - s'il est omis, le faux-cas correspondra toujours. La condition peut être soit un modèle, soit le nom d'un groupe de capture. Je vais me concentrer sur ce dernier cas ici. S'il s'agit du nom d'un groupe de capture, alors truePatternest utilisé si et seulement si la pile de capture pour ce groupe particulier n'est pas vide. Autrement dit, un modèle conditionnel comme (?(name)yes|no)lit "si namea correspondu et a capturé quelque chose (qui est toujours sur la pile), utilisez pattern yessinon utilisez pattern no".

Donc, à la fin de notre modèle ci-dessus, nous pourrions ajouter quelque chose comme (?(Open)failPattern)qui provoque l'échec du modèle entier, si le Open-stack n'est pas vide. La chose la plus simple pour faire échouer le modèle sans condition est (?!)(une anticipation négative vide). Nous avons donc notre modèle final:

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

Notez que cette syntaxe conditionnelle n'a rien à voir en soi avec les groupes d'équilibrage mais elle est nécessaire pour exploiter leur pleine puissance.

De là, le ciel est la limite. De nombreuses utilisations très sophistiquées sont possibles et il y a quelques pièges lorsqu'elles sont utilisées en combinaison avec d'autres fonctionnalités .NET-Regex telles que les lookbacks de longueur variable ( que j'ai dû apprendre à la dure moi-même ). La question principale est cependant toujours: votre code est-il toujours maintenable lorsque vous utilisez ces fonctionnalités? Vous devez bien le documenter et vous assurer que tous ceux qui y travaillent sont également conscients de ces fonctionnalités. Sinon, vous feriez peut-être mieux de parcourir la chaîne manuellement caractère par caractère et de compter les niveaux d'imbrication dans un entier.

Addendum: Quelle est la (?<A-B>...)syntaxe?

Les crédits pour cette partie vont à Kobi (voir sa réponse ci-dessous pour plus de détails).

Maintenant, avec tout ce qui précède, nous pouvons valider qu'une chaîne est correctement entre parenthèses. Mais ce serait beaucoup plus utile si nous pouvions réellement obtenir des captures (imbriquées) pour tous les contenus de ces parenthèses. Bien sûr, nous pourrions nous souvenir d'ouvrir et de fermer les parenthèses dans une pile de capture séparée qui n'est pas vidée, puis de faire une extraction de sous-chaînes en fonction de leurs positions dans une étape distincte.

Mais .NET fournit une fonctionnalité de plus ici: si nous utilisons (?<A-B>subPattern), non seulement une capture est extraite de la pile B, mais aussi tout ce qui se trouve entre cette capture sautée Bet ce groupe actuel est poussé sur la pile A. Donc, si nous utilisons un groupe comme celui-ci pour les parenthèses fermantes, tout en sautant les niveaux d'imbrication de notre pile, nous pouvons également pousser le contenu de la paire sur une autre pile:

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

_{Kobi a fourni cette démo en direct dans sa réponse}

Donc, en prenant toutes ces choses ensemble, nous pouvons:

• Rappelez-vous arbitrairement de nombreuses captures
• Valider les structures imbriquées
• Capturez chaque niveau d'imbrication

Le tout dans une seule expression régulière. Si ce n'est pas excitant ...;)

Quelques ressources que j'ai trouvées utiles lorsque j'ai appris à leur sujet:

• http://blog.stevenlevithan.com/archives/balancing-groups
• MSDN sur les groupes d'équilibrage
• MSDN sur les modèles conditionnels
• http://kobikobi.wordpress.com/tag/balancing-group/ (légèrement académique, mais a quelques applications intéressantes)

Juste un petit ajout à l'excellente réponse de M. Buettner:

Quel est le problème avec la (?<A-B>)syntaxe?

(?<A-B>x)est subtilement différent de (?<-A>(?<B>x)). Ils aboutissent au même flux de contrôle ^* , mais ils capturent différemment.
Par exemple, regardons un modèle d'accolades équilibrées:

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

À la fin de la correspondance, nous avons une chaîne équilibrée, mais c'est tout ce que nous avons - nous ne savons pas où se trouvent les accolades car la Bpile est vide. Le travail acharné que le moteur a fait pour nous est terminé.
_{( exemple sur Regex Storm )}

(?<A-B>x)est la solution à ce problème. Comment? Il ne capture pasx en $A: il capture le contenu entre la capture précédente Bet la position actuelle.

Utilisons-le dans notre modèle:

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

Cela capturerait dans $Contentles chaînes entre les accolades (et leurs positions), pour chaque paire en cours de route.
Pour la chaîne {1 2 {3} {4 5 {6}} 7}il y aurait quatre captures: 3, 6, 4 5 {6}et 1 2 {3} {4 5 {6}} 7- beaucoup mieux que rien ou } } } }.
_{( exemple - cliquez sur l' tableonglet et regardez ${Content}, capture )}

En fait, il peut être utilisé sans équilibrer du tout: (?<A>).(.(?<Content-A>).)capture les deux premiers caractères, même s'ils sont séparés par des groupes.
(un lookahead est plus couramment utilisé ici mais il n'est pas toujours mis à l'échelle: il peut dupliquer votre logique.)

(?<A-B>)est une fonctionnalité forte - il vous donne un contrôle exact sur vos captures. Gardez cela à l'esprit lorsque vous essayez de tirer le meilleur parti de votre modèle.