java regex capturing-group lookaround nested-reference

¿Cómo podemos unir ^ nb ^ n con Java regex?



capturing-group lookaround (3)

Como se menciona en la pregunta: con el grupo de equilibrio de .NET, los patrones del tipo a n b n c n d n ... z n se pueden combinar fácilmente como

^ (?<A>a)+ (?<B-A>b)+ (?(A)(?!)) (?<C-B>c)+ (?(B)(?!)) ... (?<Z-Y>z)+ (?(Y)(?!)) $

Por ejemplo: http://www.ideone.com/usuOE

Editar:

También hay un patrón PCRE para el lenguaje generalizado con patrón recursivo, pero se necesita una búsqueda anticipada. No creo que esto sea una traducción directa de lo anterior.

^ (?=(a(?-1)?b)) a+ (?=(b(?-1)?c)) b+ ... (?=(x(?-1)?y)) x+ (y(?-1)?z) $

Por ejemplo: http://www.ideone.com/9gUwF

Esta es la segunda parte de una serie de artículos educativos de expresiones regulares. Muestra cómo lookaheads y referencias anidadas se pueden utilizar para que coincida con el lenguaje no regular a n b n . Las referencias anidadas se introducen por primera vez en: ¿cómo esta expresión regex encuentra números triangulares?

Uno de los idiomas no regulares arquetípicos es:

L = { a n b n : n > 0 }

Este es el lenguaje de todas las cadenas no vacías consistentes en un número de a seguidas por un número igual de b ''s. Los ejemplos de cadenas en este lenguaje son ab , aabb , aaabbb .

Este lenguaje puede mostrarse como no regular por el lema de bombeo . De hecho, es un lenguaje arquetípico sin contexto , que puede ser generado por la gramática libre de contexto S → aSb | ab S → aSb | ab .

No obstante, las implementaciones de expresiones regulares modernas reconocen claramente más que solo los lenguajes regulares. Es decir, no son "regulares" según la definición formal de la teoría del lenguaje. PCRE y Perl admiten expresiones regulares recursivas, y .NET admite la definición de grupos de equilibrio. Incluso características menos "sofisticadas", por ejemplo, la comparación de retroreferencia, significa que la expresión regular no es regular.

¿Pero qué tan poderosas son estas características "básicas"? ¿Podemos reconocer L con Java regex, por ejemplo? ¿Podemos quizás combinar vistas alternativas y referencias anidadas y tener un patrón que funcione con, por ejemplo, String.matches para que coincida con cadenas como ab , aabb , aaabbb , etc.?

Referencias

Preguntas relacionadas

Dado que no se mencionó que PCRE apoye patrones recursivos, me gustaría señalar el ejemplo más simple y eficiente de PCRE que describe el lenguaje en cuestión:

/^(a(?1)?b)$/

La respuesta es, no hace falta decir, ¡SÍ! Sin duda, puede escribir un patrón de expresiones regulares de Java para que coincida con a n b n . Utiliza un lookahead positivo para la aserción y una referencia anidada para "contar".

En lugar de dar el patrón de inmediato, esta respuesta guiará a los lectores a través del proceso de derivación. Se dan varios consejos a medida que la solución se construye lentamente. En este aspecto, es de esperar que esta respuesta contenga mucho más que solo otro patrón de expresiones regulares limpio. Es de esperar que los lectores también aprendan a "pensar en expresiones regulares" y cómo combinar varias construcciones de manera armónica para que puedan derivar más patrones por sí mismos en el futuro.

El lenguaje utilizado para desarrollar la solución será PHP por su concisión. La prueba final una vez que se finalice el patrón se realizará en Java.

Paso 1: busque la afirmación

Comencemos con un problema más simple: queremos hacer coincidir a+ al comienzo de una cadena, pero solo si es seguido inmediatamente por b+ . Podemos usar ^ para anchor nuestra coincidencia, y como solo queremos hacer coincidir el a+ sin el b+ , podemos usar la aserción de Lookarounds anticipada (?=…) .

Aquí está nuestro patrón con un arnés de prueba simple:

function testAll($r, $tests) { foreach ($tests as $test) { $isMatch = preg_match($r, $test, $groups); $groupsJoined = join(''|'', $groups); print("$test $isMatch $groupsJoined/n"); } } $tests = array(''aaa'', ''aaab'', ''aaaxb'', ''xaaab'', ''b'', ''abbb''); $r1 = ''/^a+(?=b+)/''; # └────┘ # lookahead testAll($r1, $tests);

La salida es ( como se ve en ideone.com ):

aaa 0 aaab 1 aaa aaaxb 0 xaaab 0 b 0 abbb 1 a

Este es exactamente el resultado que queremos: coincidimos con a+ , solo si está al principio de la cadena, y solo si es seguido inmediatamente por b+ .

Lección : puede usar patrones en las alternativas para hacer afirmaciones.

Paso 2: Capturar de forma anticipada (y modo de espacio libre)

Ahora digamos que aunque no queremos que b+ sea ​​parte de la coincidencia, queremos capturarlo de todos modos en el grupo 1. Además, como anticipamos tener un patrón más complicado, usemos el modificador x para free-spacing para que podamos hacer que nuestra expresión regular sea más legible.

Sobre la base de nuestro fragmento de PHP anterior, ahora tenemos el siguiente patrón:

$r2 = ''/ ^ a+ (?= (b+) ) /x''; # │ └──┘ │ # │ 1 │ # └────────┘ # lookahead testAll($r2, $tests);

La salida es ahora ( como se ve en ideone.com ):

aaa 0 aaab 1 aaa|b aaaxb 0 xaaab 0 b 0 abbb 1 a|bbb

Tenga en cuenta que, por ejemplo, aaa|b es el resultado de join lo que cada grupo capturó con ''|'' . En este caso, el grupo 0 (es decir, lo que coincide con el patrón) capturó aaa , y el grupo 1 capturó b .

Lección : Puedes capturar dentro de un vistazo. Puede usar espaciado libre para mejorar la legibilidad.

Paso 3: Refactorizar la búsqueda anticipada en el "ciclo"

Antes de que podamos presentar nuestro mecanismo de conteo, debemos hacer una modificación en nuestro patrón. Actualmente, la búsqueda anticipada está fuera del "bucle" de + repetición. Esto está bien hasta ahora porque solo queríamos afirmar que hay un b+ sigue nuestro a+ , pero lo que realmente queremos hacer con el tiempo es afirmar que para cada a que coincidamos dentro del "bucle", hay un b correspondiente al mismo. .

No nos preocupemos por el mecanismo de conteo por ahora y simplemente hagamos la refactorización de la siguiente manera:

  • Primero refactorice a+ a (?: a )+ (tenga en cuenta que (?:…) es un grupo que no captura)
  • A continuación, mueva la búsqueda hacia adelante dentro de este grupo no captor
    • Tenga en cuenta que ahora debemos "omitir" a* antes de que podamos "ver" el b+ , por lo tanto, modifique el patrón en consecuencia

Entonces ahora tenemos lo siguiente:

$r3 = ''/ ^ (?: a (?= a* (b+) ) )+ /x''; # │ │ └──┘ │ │ # │ │ 1 │ │ # │ └───────────┘ │ # │ lookahead │ # └───────────────────┘ # non-capturing group

El resultado es el mismo que antes ( como se ve en ideone.com ), por lo que no hay ningún cambio en ese sentido. Lo importante es que ahora estamos haciendo la aserción en cada iteración del + "bucle". Con nuestro patrón actual, esto no es necesario, pero a continuación haremos que el grupo 1 "cuente" para nosotros utilizando la autorreferencia.

Lección : Puedes capturar dentro de un grupo que no captura. Las miradas se pueden repetir.

Paso 4: este es el paso donde comenzamos a contar

Esto es lo que vamos a hacer: reescribiremos el grupo 1 de modo que:

  • Al final de la primera iteración de + , cuando se combina la primera a , debe capturar b
  • Al final de la segunda iteración, cuando se combina otra a , debe capturar bb
  • Al final de la tercera iteración, debería capturar bbb
  • ...
  • Al final de la enésima iteración, el grupo 1 debe capturar b n
  • Si no hay suficiente b para capturar en el grupo 1, entonces la afirmación simplemente falla

Entonces el grupo 1, que ahora es (b+) , tendrá que ser reescrito a algo así como (/1 b) . Es decir, tratamos de "agregar" a b a qué grupo 1 capturó en la iteración anterior.

Aquí hay un pequeño problema en el sentido de que a este patrón le falta el "caso base", es decir, el caso en el que puede coincidir sin la autorreferencia. Se requiere un caso base porque el grupo 1 comienza "sin inicializar"; aún no ha capturado nada (ni siquiera una cadena vacía), por lo que un intento de autorreferencia siempre fallará.

Hay muchas formas de evitar esto, pero por ahora, hagamos que la coincidencia de autorreferencia sea optional , es decir, /1? . Esto puede o no funcionar perfectamente, pero veamos lo que hace, y si hay algún problema, entonces cruzaremos ese puente cuando lleguemos a él. Además, agregaremos algunos casos de prueba más mientras estamos en ello.

$tests = array( ''aaa'', ''aaab'', ''aaaxb'', ''xaaab'', ''b'', ''abbb'', ''aabb'', ''aaabbbbb'', ''aaaaabbb'' ); $r4 = ''/ ^ (?: a (?= a* (/1? b) ) )+ /x''; # │ │ └─────┘ | │ # │ │ 1 | │ # │ └──────────────┘ │ # │ lookahead │ # └──────────────────────┘ # non-capturing group

La salida es ahora ( como se ve en ideone.com ):

aaa 0 aaab 1 aaa|b # (*gasp!*) aaaxb 0 xaaab 0 b 0 abbb 1 a|b # yes! aabb 1 aa|bb # YES!! aaabbbbb 1 aaa|bbb # YESS!!! aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....

A-ha! ¡Parece que estamos realmente cerca de la solución ahora! ¡Logramos que el grupo 1 "cuente" usando la autorreferencia! Pero espera ... ¡algo está mal con el segundo y último caso de prueba! ¡No hay suficientes b s, y de alguna manera contaba mal! Examinaremos por qué sucedió esto en el próximo paso.

Lección : Una forma de "inicializar" un grupo autorreferencial es hacer que la coincidencia de autorreferencia sea opcional.

Paso 4½: entender qué salió mal

El problema es que, dado que hicimos la coincidencia de referencia automática opcional, el "contador" puede "restablecerse" de nuevo a 0 cuando no hay suficientes b . Examinemos de cerca lo que sucede en cada iteración de nuestro patrón con aaaaabbb como entrada.

a a a a a b b b ↑ # Initial state: Group 1 is "uninitialized". _ a a a a a b b b ↑ # 1st iteration: Group 1 couldn''t match /1 since it was "uninitialized", # so it matched and captured just b ___ a a a a a b b b ↑ # 2nd iteration: Group 1 matched /1b and captured bb _____ a a a a a b b b ↑ # 3rd iteration: Group 1 matched /1b and captured bbb _ a a a a a b b b ↑ # 4th iteration: Group 1 could still match /1, but not /1b, # (!!!) so it matched and captured just b ___ a a a a a b b b ↑ # 5th iteration: Group 1 matched /1b and captured bb # # No more a, + "loop" terminates

A-ha! En nuestra cuarta iteración, todavía podíamos coincidir con /1 , ¡pero no podíamos coincidir con /1b ! ¿Ya que permitimos que la coincidencia de autorreferencia sea opcional con /1? , el motor retrocede y tomó la opción de "no, gracias", lo que nos permite unir y capturar solo b .

Sin embargo, tenga en cuenta que, salvo en la primera iteración, siempre podría coincidir con la referencia automática /1 . Esto es obvio, por supuesto, ya que es lo que acabamos de capturar en nuestra iteración anterior, y en nuestra configuración siempre podemos hacer coincidir de nuevo (por ejemplo, si bbb última vez, estamos seguros de que todavía habrá bbb , pero hay puede o no ser bbbb esta vez).

Lección : Cuidado con retroceder. El motor regex hará tanto retroceso como lo permita hasta que el patrón dado coincida. Esto puede afectar el rendimiento (es decir, retroceso catastrófico ) y / o la corrección.

Paso 5: ¡Autoposesión al rescate!

El "arreglo" ahora debería ser obvio: combine la repetición opcional con el cuantificador possessive . Es decir, ¿en lugar de simplemente ? , utilice ?+ lugar (recuerde que una repetición que se cuantifica como posesiva no se retrasa, incluso si dicha "cooperación" puede dar como resultado una coincidencia del patrón general).

En términos muy informales, ¿esto es qué ?+ ? y ?? dice:

?+

  • (opcional) "No tiene que estar allí"
    • (posesivo) "pero si está allí, debes tomarlo y no soltarlo".

?

  • (opcional) "No tiene que estar allí"
    • (codicioso) "pero si es así puedes tomarlo por ahora"
      • (retrocediendo) "¡pero se te puede pedir que lo dejes ir más tarde!"

??

  • (opcional) "No tiene que estar allí"
    • (reacio) "e incluso si es usted no tiene que tomarlo todavía"
      • (retrocediendo) "¡pero se te puede pedir que lo tomes luego!"

En nuestra configuración, /1 no estará allí la primera vez, pero siempre estará allí en cualquier momento después de eso, y siempre queremos coincidir con eso. Por lo tanto, /1?+ Lograría exactamente lo que queremos.

$r5 = ''/ ^ (?: a (?= a* (/1?+ b) ) )+ /x''; # │ │ └──────┘ │ │ # │ │ 1 │ │ # │ └───────────────┘ │ # │ lookahead │ # └───────────────────────┘ # non-capturing group

Ahora la salida es ( como se ve en ideone.com ):

aaa 0 aaab 1 a|b # Yay! Fixed! aaaxb 0 xaaab 0 b 0 abbb 1 a|b aabb 1 aa|bb aaabbbbb 1 aaa|bbb aaaaabbb 1 aaa|bbb # Hurrahh!!!

Voilà !!! ¡¡¡Problema resuelto!!! ¡Ahora estamos contando correctamente, exactamente como queremos!

Lección : aprende la diferencia entre la repetición codiciosa, renuente y posesiva. Opcional-posesivo puede ser una combinación poderosa.

Paso 6: toques finales

Entonces, lo que tenemos ahora es un patrón que coincide repetidamente con, y para cada a que se combinó, hay una b correspondiente capturada en el grupo 1. La + termina cuando no hay más a , o si la afirmación falla porque no hay a t correspondiente b para a .

Para finalizar el trabajo, simplemente necesitamos agregar a nuestro patrón /1 $ . Esto ahora es una referencia a lo que el grupo 1 hizo coincidir, seguido por el ancla de final de línea. El ancla asegura que no hay ningún b adicional en la cuerda; en otras palabras, que de hecho tenemos a n b n .

Aquí está el patrón finalizado, con casos de prueba adicionales, incluido uno de 10.000 caracteres de longitud:

$tests = array( ''aaa'', ''aaab'', ''aaaxb'', ''xaaab'', ''b'', ''abbb'', ''aabb'', ''aaabbbbb'', ''aaaaabbb'', '''', ''ab'', ''abb'', ''aab'', ''aaaabb'', ''aaabbb'', ''bbbaaa'', ''ababab'', ''abc'', str_repeat(''a'', 5000).str_repeat(''b'', 5000) ); $r6 = ''/ ^ (?: a (?= a* (/1?+ b) ) )+ /1 $ /x''; # │ │ └──────┘ │ │ # │ │ 1 │ │ # │ └───────────────┘ │ # │ lookahead │ # └───────────────────────┘ # non-capturing group

Encuentra 4 coincidencias: ab , aabb , aaabbb y a 5000 b 5000 . Solo se necesitan 0.06 segundos para ejecutar en ideone.com .

Paso 7: la prueba de Java

Entonces, el patrón funciona en PHP, pero el objetivo final es escribir un patrón que funcione en Java.

public static void main(String[] args) { String aNbN = "(?x) (?: a (?= a* (//1?+ b)) )+ //1"; String[] tests = { "", // false "ab", // true "abb", // false "aab", // false "aabb", // true "abab", // false "abc", // false repeat(''a'', 5000) + repeat(''b'', 4999), // false repeat(''a'', 5000) + repeat(''b'', 5000), // true repeat(''a'', 5000) + repeat(''b'', 5001), // false }; for (String test : tests) { System.out.printf("[%s]%n %s%n%n", test, test.matches(aNbN)); } } static String repeat(char ch, int n) { return new String(new char[n]).replace(''/0'', ch); }

El patrón funciona como se espera ( como se ve en ideone.com ).

Y ahora llegamos a la conclusión ...

Es necesario decir que el a* en el futuro, y de hecho el "lazo principal + ", ambos permiten retroceder. Se alienta a los lectores a confirmar por qué esto no es un problema en términos de corrección, y por qué al mismo tiempo hacer ambos posesivos también funcionaría (aunque tal vez mezclar un cuantificador posesivo obligatorio y no obligatorio en el mismo patrón puede llevar a percepciones erróneas).

También se debe decir que si bien es claro que hay un patrón de expresiones regulares que coincidirá con n n n , esta no siempre es la "mejor" solución en la práctica. Una solución mucho mejor es simplemente hacer coincidir ^(a+)(b+)$ , y luego comparar la longitud de las cadenas capturadas por los grupos 1 y 2 en el lenguaje de programación de alojamiento.

En PHP, puede parecerse a esto ( como se ve en ideone.com ):

function is_anbn($s) { return (preg_match(''/^(a+)(b+)$/'', $s, $groups)) && (strlen($groups[1]) == strlen($groups[2])); }

El propósito de este artículo NO es convencer a los lectores de que Regex puede hacer casi cualquier cosa; es evidente que no puede, e incluso para las cosas que puede hacer, al menos una delegación parcial al idioma de alojamiento debe considerarse si conduce a una solución más simple.

Como se menciona en la parte superior, aunque este artículo está necesariamente etiquetado [regex] para , es quizás más que eso. Aunque ciertamente es valioso aprender acerca de afirmaciones, referencias anidadas, cuantificadores posesivos, etc., tal vez la lección más importante aquí sea el proceso creativo mediante el cual uno puede tratar de resolver problemas, la determinación y el arduo trabajo que a menudo requiere cuando está sujeto a varias limitaciones, la composición sistemática de varias partes para construir una solución de trabajo, etc.

Material de bonificación! ¡Patrón recursivo de PCRE!

Dado que trajimos PHP, debe decirse que PCRE admite patrones recursivos y subrutinas. Por lo tanto, siguiendo el patrón funciona para preg_match ( como se ve en ideone.com ):

$rRecursive = ''/ ^ (a (?1)? b) $ /x'';

Actualmente, la expresión regular de Java no es compatible con el patrón recursivo.

¡Aún más material extra! ¡Coincidiendo con n b n c n !!

Entonces, hemos visto cómo hacer coincidir un n b n que no es regular, pero sigue sin tener un contexto, pero ¿podemos también combinar un n b n c n , que ni siquiera está libre de contexto?

La respuesta es, por supuesto, ¡SÍ! Se alienta a los lectores a que intenten resolverlo por sí mismos, pero la solución se proporciona a continuación (con implementación en Java en ideone.com ).

^ (?: a (?= a* (/1?+ b) b* (/2?+ c) ) )+ /1 /2 $