¿Qué son los grupos de equilibrio de expresiones regulares?

Estaba leyendo una pregunta sobre cómo obtener datos entre llaves dobles ( esta pregunta ), y luego alguien mencionó los grupos de equilibrio. Todavía no estoy muy seguro de qué son y cómo usarlos.

Leí la Definición de grupo de equilibrio , pero la explicación es difícil de seguir y todavía estoy bastante confundido con las preguntas que mencioné.

¿Alguien podría simplemente explicar qué son los grupos de equilibrio y cómo son útiles?

Hasta donde yo sé, los grupos de equilibrio son exclusivos del sabor de expresiones regulares de .NET.

Aparte: Grupos repetidos

Primero, debe saber que .NET es (nuevamente, hasta donde yo sé) el único sabor de expresiones regulares que le permite acceder a múltiples capturas de un solo grupo de captura (no en referencias inversas sino después de que se haya completado la coincidencia).

Para ilustrar esto con un ejemplo, considere el patrón

(.)+

y la cuerda "abcd".

en todos los demás tipos de expresiones regulares, el grupo de captura 1simplemente arrojará un resultado: d(tenga en cuenta que, por supuesto, la coincidencia completa será la abcdesperada). Esto se debe a que cada nuevo uso del grupo de captura sobrescribe la captura anterior.

.NET, por otro lado, los recuerda a todos. Y lo hace en una pila. Después de hacer coincidir la expresión regular anterior como

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

encontrarás eso

m.Groups[1].Captures

Es un CaptureCollectioncuyos elementos corresponden a las cuatro capturas

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

donde el número es el índice en el CaptureCollection. Básicamente, cada vez que se usa el grupo nuevamente, se inserta una nueva captura en la pila.

Se vuelve más interesante si usamos grupos de captura con nombre. Debido a que .NET permite el uso repetido del mismo nombre, podríamos escribir una expresión regular como

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

para capturar dos palabras en el mismo grupo. Nuevamente, cada vez que se encuentra un grupo con un nombre determinado, se inserta una captura en su pila. Entonces, aplicando esta expresión regular a la entrada "foo bar"e inspeccionando

m.Groups["word"].Captures

encontramos dos capturas

0: "foo"
1: "bar"

Esto nos permite incluso colocar cosas en una sola pila desde diferentes partes de la expresión. Pero aún así, esta es solo la característica de .NET de poder rastrear múltiples capturas que se enumeran en esto CaptureCollection. Pero dije, esta colección es una pila . Entonces, ¿podemos sacar cosas de él?

Ingrese: Grupos de equilibrio

Resulta que podemos. Si usamos un grupo como (?<-word>...), entonces la última captura se extrae de la pila wordsi la subexpresión ...coincide. Entonces, si cambiamos nuestra expresión anterior a

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

Luego, el segundo grupo mostrará la captura del primer grupo y al final recibiremos un vacío CaptureCollection. Por supuesto, este ejemplo es bastante inútil.

Pero hay un detalle más en la sintaxis negativa: si la pila ya está vacía, el grupo falla (independientemente de su subpatrón). Podemos aprovechar este comportamiento para contar los niveles de anidación, y aquí es de donde proviene el grupo de equilibrio de nombres (y donde se vuelve interesante). Digamos que queremos hacer coincidir cadenas que están correctamente entre paréntesis. Empujamos cada paréntesis de apertura en la pila y sacamos una captura para cada paréntesis de cierre. Si encontramos un paréntesis de cierre de más, intentará abrir una pila vacía y provocará que el patrón falle:

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

Entonces tenemos tres alternativas en una repetición. La primera alternativa consume todo lo que no sea un paréntesis. La segunda alternativa coincide con los (s mientras los empuja hacia la pila. La tercera alternativa coincide con )s mientras extrae elementos de la pila (¡si es posible!).

_{Nota: Solo para aclarar, ¡solo estamos verificando que no haya paréntesis que no coincidan! Esto significa que no hay cadena que contiene paréntesis en absoluto será partido, porque todavía son sintácticamente válido (en alguna sintaxis donde tiene sus paréntesis, a partido). Si desea asegurarse de que haya al menos un par de paréntesis, simplemente agregue una búsqueda anticipada (?=.*[(])justo después de ^.}

Sin embargo, este patrón no es perfecto (o del todo correcto).

Final: Patrones condicionales

Hay una trampa más: esto no asegura que la pila esté vacía al final de la cadena (por (foo(bar)lo tanto , sería válida). .NET (y muchos otros sabores) tienen una construcción más que nos ayuda aquí: patrones condicionales. La sintaxis general es

(?(condition)truePattern|falsePattern)

donde falsePatternes opcional: si se omite, el caso falso siempre coincidirá. La condición puede ser un patrón o el nombre de un grupo de captura. Me centraré en el último caso aquí. Si es el nombre de un grupo de captura, entonces truePatternse usa si y solo si la pila de captura para ese grupo en particular no está vacía. Es decir, un patrón condicional como (?(name)yes|no)dice "si nameha coincidido y capturado algo (que todavía está en la pila), use el patrón de lo yescontrario use el patrón no".

Entonces, al final de nuestro patrón anterior, podríamos agregar algo como lo (?(Open)failPattern)que hace que todo el patrón falle, si la Openpila no está vacía. Lo más simple para hacer que el patrón falle incondicionalmente es (?!)(una mirada hacia adelante negativa vacía). Entonces tenemos nuestro patrón final:

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

Tenga en cuenta que esta sintaxis condicional no tiene nada que ver per se con el equilibrio de grupos, pero es necesario aprovechar todo su poder.

A partir de aquí, el cielo es el límite. Son posibles muchos usos muy sofisticados y hay algunas trampas cuando se usan en combinación con otras características de .NET-Regex como mirar atrás de longitud variable ( que tuve que aprender por las malas ). Sin embargo, la pregunta principal es siempre: ¿su código aún se puede mantener al usar estas funciones? Debe documentarlo muy bien y asegurarse de que todos los que trabajen en él también conozcan estas características. De lo contrario, podría estar mejor, simplemente caminando la cadena de forma manual carácter por carácter y contando los niveles de anidación en un número entero.

Anexo: ¿Qué pasa con la (?<A-B>...)sintaxis?

Los créditos para esta parte van a Kobi (consulte su respuesta a continuación para obtener más detalles).

Ahora, con todo lo anterior, podemos validar que una cadena esté correctamente entre paréntesis. Pero sería mucho más útil si pudiéramos obtener capturas (anidadas) para todos los contenidos de esos paréntesis. Por supuesto, podríamos recordar abrir y cerrar paréntesis en una pila de captura separada que no se vacía, y luego hacer una extracción de subcadenas en función de sus posiciones en un paso separado.

Pero .NET proporciona una característica más de conveniencia aquí: si usamos (?<A-B>subPattern), no solo se extrae una captura de la pila B, sino que también todo lo que se encuentra entre esa captura emergente de By este grupo actual se envía a la pila A. Entonces, si usamos un grupo como este para el paréntesis de cierre, mientras sacamos los niveles de anidación de nuestra pila, también podemos empujar el contenido del par a otra pila:

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

_{Kobi proporcionó esta demostración en vivo en su respuesta}

Entonces, tomando todas estas cosas juntas, podemos:

• Recuerda arbitrariamente muchas capturas
• Validar estructuras anidadas
• Captura cada nivel de anidación

Todo en una sola expresión regular. Si eso no es emocionante ...;)

Algunos recursos que encontré útiles cuando los conocí por primera vez:

• http://blog.stevenlevithan.com/archives/balancing-groups
• MSDN sobre grupos de equilibrio
• MSDN en patrones condicionales
• http://kobikobi.wordpress.com/tag/balancing-group/ (ligeramente académico, pero tiene algunas aplicaciones interesantes)

Solo una pequeña adición a la excelente respuesta de M. Buettner:

¿Qué pasa con la (?<A-B>)sintaxis?

(?<A-B>x)es sutilmente diferente de (?<-A>(?<B>x)). Dan como resultado el mismo flujo de control ^* , pero capturan de manera diferente.
Por ejemplo, veamos un patrón para aparatos ortopédicos equilibrados:

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

Al final de la partida tenemos una cadena equilibrada, pero eso es todo lo que tenemos, no sabemos dónde están las llaves porque la Bpila está vacía. El arduo trabajo que hizo el motor por nosotros se ha ido.
_{( ejemplo en Regex Storm )}

(?<A-B>x)es la solución a ese problema. ¿Cómo? Que no captura xen $A: captura el contenido entre la captura previa de By la posición actual.

Usémoslo en nuestro patrón:

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

Esto se capturaría en $Contentlas cuerdas entre los tirantes (y sus posiciones), para cada par a lo largo del camino.
Para la cadena {1 2 {3} {4 5 {6}} 7}que habría cuatro capturas: 3, 6, 4 5 {6}, y 1 2 {3} {4 5 {6}} 7- mucho mejor que nada o } } } }.
_{( ejemplo: haga clic en la tablepestaña y mire ${Content}, capturas )}

De hecho, se puede utilizar sin equilibrar en absoluto: (?<A>).(.(?<Content-A>).)captura los dos primeros personajes, aunque estén separados por grupos.
(una búsqueda anticipada se usa más comúnmente aquí, pero no siempre se escala: puede duplicar su lógica).

(?<A-B>)es una característica sólida: le brinda un control exacto sobre sus capturas. Tenga esto en cuenta cuando intente sacar más provecho de su patrón.