¿Cómo podemos hacer coincidir un ^ nb ^ n con Java regex?

_{Esta es la segunda parte de una serie de artículos educativos sobre expresiones regulares. Muestra cómo se pueden usar búsquedas anticipadas y referencias anidadas para hacer coincidir el idioma no regular a ⁿ b ⁿ . Las referencias anidadas se introducen por primera vez en: ¿Cómo encuentra esta expresión regular números triangulares?}

Uno de los lenguajes arquetípicos no regulares es:

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

Este es el idioma de todas las cadenas no vacías que constan de un número de aseguido de un número igual de b. Ejemplos de cadenas en esta lengua son ab, aabb, aaabbb.

El lema de bombeo puede demostrar que este lenguaje no es regular . De hecho, es un lenguaje arquetípico libre de contexto , que puede ser generado por la gramática libre de contexto S → aSb | ab .

No obstante, las implementaciones de expresiones regulares de hoy en día reconocen claramente más que solo lenguajes regulares. Es decir, no son "regulares" según la definición de la teoría formal del lenguaje. PCRE y Perl admiten expresiones regulares recursivas y .NET admite la definición de grupos de equilibrio. Incluso las características menos "elegantes", por ejemplo, la coincidencia de referencias inversas, significan que la expresión regular no es regular.

Pero, ¿qué tan poderosas son estas características "básicas"? ¿Podemos reconocer Lcon Java regex, por ejemplo? Podemos quizá combinar lookarounds y referencias anidadas y tienen un patrón que funciona con por ejemplo, String.matchespara que coincida con cadenas como ab, aabb, aaabbb, etc?

Referencias

• perlfaq6: ¿Puedo usar expresiones regulares de Perl para hacer coincidir texto balanceado?
• MSDN - Elementos del lenguaje de expresión regular - Definiciones de grupos de equilibrio
• pcre.org - página de manual de PCRE
• regular-expressions.info - Lookarounds y Agrupación y referencias hacia atrás
• java.util.regex.Pattern

Preguntas vinculadas

• ¿Afecta la búsqueda a qué idiomas pueden coincidir con expresiones regulares?
• .NET Regex Balancing Groups vs PCRE Recursive Patterns

La respuesta es, no hace falta decirlo, ¡SÍ! Seguramente puede escribir un patrón de expresiones regulares de Java para que coincida con a ⁿ b ⁿ . Utiliza una búsqueda anticipada positiva para la aserción y una referencia anidada para "contar".

En lugar de dar el patrón inmediatamente, esta respuesta guiará a los lectores a través del proceso de derivarlo. Se dan varias sugerencias a medida que la solución se construye lentamente. En este aspecto, es de esperar que esta respuesta contenga mucho más que otro patrón de expresiones regulares ordenado. Es de esperar que los lectores también aprendan cómo "pensar en expresiones regulares", y cómo unir armoniosamente varios constructos, 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 finalizado el patrón se realizará en Java.

Paso 1: anticipación para la afirmación

Comencemos con un problema más simple: queremos hacer coincidir a+al principio de una cadena, pero solo si le sigue inmediatamente b+. Podemos usar ^para anclar nuestra coincidencia, y dado que solo queremos hacer coincidir a+sin el b+, podemos usar la aserción de búsqueda 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);

El resultado es ( como se ve en ideone.com ):

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

Esta es exactamente la salida que queremos: hacemos coincidir a+, solo si está al principio de la cadena, y solo si es seguida inmediatamente por b+.

Lección : Puede usar patrones en las revisiones para hacer afirmaciones.

Paso 2: captura en una vista anticipada (y en modo de espaciado libre)

Ahora digamos que aunque no queremos b+que forme parte de la coincidencia, queremos capturarlo de todos modos en el grupo 1. Además, como anticipamos que tendremos un patrón más complicado, usemos el xmodificador para el espacio libre para que podamos puede hacer que nuestra expresión regular sea más legible.

Sobre la base de nuestro fragmento de código 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|bes el resultado de join-ing con lo que capturó cada grupo '|'. En este caso, el grupo 0 (es decir, lo que coincide con el patrón) capturó aaay el grupo 1 capturó b.

Lección : puede capturar dentro de un vistazo. Puede utilizar espacios libres para mejorar la legibilidad.

Paso 3: Refactorización de la anticipación en el "bucle"

Antes de que podamos introducir nuestro mecanismo de conteo, necesitamos hacer una modificación a 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+seguimiento nuestro a+, pero lo que realmente queremos hacer al final es afirmar que para cada uno aque coincidamos dentro del "bucle", hay un correspondiente bque lo acompaña.

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

• Primera refactorización a+a (?: a )+(tenga en cuenta que (?:…)es un grupo que no captura)
• Luego, mueva la búsqueda hacia adelante dentro de este grupo que no captura
  • Tenga en cuenta que ahora debemos "omitir" a*antes de que podamos "ver" el b+, así que modifique el patrón en consecuencia

Entonces ahora tenemos lo siguiente:

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

La salida es la misma que antes ( como se ve en ideone.com ), por lo que no hay cambios en ese sentido. Lo importante es que ahora estamos haciendo la afirmació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 usando la autorreferencia.

Lección : puede capturar dentro de un grupo que no captura. Se pueden repetir las miradas.

Paso 4: Este es el paso donde comenzamos a contar.

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

• Al final de la primera iteración de +, cuando ase empareja la primera , debería capturarb
• Al final de la segunda iteración, cuando ase empareja otra , debería capturarbb
• Al final de la tercera iteración, debería capturar bbb
• ...
• Al final de la n -ésima iteración, el grupo 1 debería capturar b ⁿ
• Si no hay suficientes bpara capturar en el grupo 1, la afirmación simplemente falla

Entonces, el grupo 1, que es ahora (b+), tendrá que reescribirse a algo como (\1 b). Es decir, intentamos "agregar" ba lo que el grupo 1 capturó en la iteración anterior.

Aquí hay un pequeño problema, ya 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 opcional , es decir \1?. Esto puede o no funcionar perfectamente, pero veamos qué hace, y si hay algún problema, cruzaremos ese puente cuando lleguemos a él. Además, agregaremos algunos casos de prueba más mientras estamos en eso.

$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....

¡Ajá! ¡Parece que ahora estamos muy cerca de la solución! ¡Logramos que el grupo 1 "cuente" usando la autorreferencia! Pero espere ... ¡algo anda mal con el segundo y último caso de prueba! No hay suficientes bmensajes de correo electrónico, ¡y de alguna manera contó mal! Examinaremos por qué sucedió esto en el siguiente paso.

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

Paso 4½: Entender qué salió mal

El problema es que, dado que hicimos que la coincidencia de autorreferencia fuera opcional, el "contador" puede "restablecerse" a 0 cuando no hay suficientes b. Examinemos de cerca lo que sucede en cada iteración de nuestro patrón con una aaaaabbbentrada.

 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

¡Ajá! En nuestra cuarta iteración, aún podríamos igualar \1, ¡pero no pudimos igualar \1b! Dado que permitimos que la coincidencia de autorreferencia sea opcional con \1?, el motor retrocede y tomó la opción "no, gracias", que luego nos permite emparejar y capturar solo b!

Sin embargo, tenga en cuenta que, excepto en la primera iteración, siempre puede hacer coincidir solo la autorreferencia \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 igualarlo nuevamente (por ejemplo, si capturamos la bbbúltima vez, tenemos la garantía de que todavía habrá bbb, pero puede haber o puede que no sea bbbbesta vez).

Lección : Cuidado con dar marcha atrás. El motor de expresiones regulares hará todo el retroceso que permita hasta que coincida el patrón dado. Esto puede afectar el rendimiento (es decir, retroceso catastrófico ) y / o corrección.

Paso 5: ¡Posesión al rescate!

La "solución" ahora debería ser obvia: combine la repetición opcional con el cuantificador posesivo . Es decir, en lugar de simplemente ?, use ?+en su lugar (recuerde que una repetición que se cuantifica como posesiva no retrocede, incluso si tal "cooperación" puede resultar en una coincidencia del patrón general).

En términos muy informales, esto es lo que ?+, ?y ??dice:

?+

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

?

• (opcional) "No tiene que estar allí"
  • (codicioso) "pero si lo es, puedes aceptarlo por ahora"
    • (retrocediendo) "¡pero se le puede pedir que lo deje pasar más tarde!"

??

• (opcional) "No tiene que estar allí"
  • (reacio) "e incluso si es así, no tienes que tomarlo todavía",
    • (retrocediendo) "¡pero se le puede pedir que lo tome más tarde!"

En nuestra configuración, \1no estará ahí la primera vez, pero siempre estará ahí en cualquier momento después de eso, y siempre queremos igualarlo entonces. Por \1?+lo tanto, 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 de la manera que queremos!

Lección : Aprenda la diferencia entre repetición codiciosa, reacia 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 arepetidamente, y para cada acoincidencia, hay un correspondiente bcapturado en el grupo 1. El +termina cuando no hay más a, o si la aserción falló porque no hay un correspondiente bpara an a.

Para terminar el trabajo, simplemente necesitamos agregar a nuestro patrón \1 $. Esta es ahora una referencia posterior a lo que coincidió con el grupo 1, seguida del final del ancla de línea. El ancla asegura que no haya ningún extra ben la cuerda; en otras palabras, que de hecho tenemos un ⁿ b ⁿ .

Aquí está el patrón finalizado, con casos de prueba adicionales, incluido uno que tiene 10,000 caracteres de largo:

$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

Se encuentra 4 partidos ab, aabb, aaabbb, y el un ⁵⁰⁰⁰ b ⁵⁰⁰⁰ . Solo se necesitan 0,06 segundos para ejecutarse 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 esperaba ( como se ve en ideone.com ).

Y ahora llegamos a la conclusión ...

Es necesario decir que el a* de la búsqueda hacia delante, y de hecho el "principal +lazo", ambos retroceso permiso. Se anima 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 quizás mezclar cuantificadores posesivos obligatorios y no obligatorios en el mismo patrón puede llevar a percepciones erróneas).

También debe decirse que, si bien está bien, hay un patrón de expresiones regulares que coincidirá con un ⁿ b ⁿ , 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 verse así ( 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 las expresiones regulares pueden hacer casi cualquier cosa; claramente no puede, e incluso para las cosas que puede hacer, se debe considerar al menos una delegación parcial al idioma de alojamiento si conduce a una solución más simple.

Como se mencionó en la parte superior, si bien este artículo está necesariamente etiquetado [regex]como stackoverflow, quizás se trate de más que eso. Si bien ciertamente hay valor en aprender sobre afirmaciones, referencias anidadas, cuantificadores posesivos, etc., quizás la lección más importante aquí es el proceso creativo mediante el cual uno puede intentar resolver problemas, la determinación y el trabajo arduo que a menudo requiere cuando está sujeto a varias restricciones, la composición sistemática de varias partes para construir una solución de trabajo, etc.

¡Material extra! Patrón recursivo PCRE!

Como hicimos aparecer PHP, es necesario decir que PCRE admite patrones recursivos y subrutinas. Por lo tanto, el siguiente 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 admite patrones recursivos.

¡Aún más material extra! Coincidencia de a ⁿ b ⁿ c ⁿ !!

Entonces, hemos visto cómo hacer coincidir a ⁿ b ^n, que no es regular, pero aún no tiene contexto, pero ¿podemos también hacer coincidir a ⁿ b ⁿ c ⁿ , que ni siquiera es libre de contexto?

La respuesta es, por supuesto, ¡SÍ! Se anima a los lectores a intentar resolver esto por su cuenta, 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 $

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

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

Como se menciona en la pregunta, con el grupo de equilibrio de .NET, los patrones del tipo a ⁿ b ⁿ c ⁿ d ⁿ ... z ⁿ 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 esta 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