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

99

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 n b n . 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 = { an bn: 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

Preguntas vinculadas

poligenelubricantes
fuente
4
Esta serie se inició con el permiso de algunos miembros de la comunidad ( meta.stackexchange.com/questions/62695/… ). Si la recepción es buena, planeo continuar cubriendo otras características más avanzadas y más básicas de expresiones regulares.
polygenelubricants
Parte 3: stackoverflow.com/questions/3664881/…
polygenelubricants
Vaya, nunca supe que las expresiones regulares de Java no se limitarán a las expresiones regulares. Supongo que eso explica por qué siempre pensé que no se implementarían por completo. Lo que quiero decir es que no hay operadores de complemento, diferencia o producto integrados en Java Regexs, pero eso tiene sentido ya que no están restringidos a los lenguajes regulares.
Lan
Esta pregunta se ha agregado a las Preguntas frecuentes sobre expresiones regulares de desbordamiento de pila , en "Advanced Regex-Fu".
aliteralmind

Respuestas:

139

La respuesta es, no hace falta decirlo, ¡SÍ! Seguramente puede escribir un patrón de expresiones regulares de Java para que coincida con a n b n . 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 n
  • 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 n b n .

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 5000 b 5000 . 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 n b 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 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 n b n c n !!

Entonces, hemos visto cómo hacer coincidir a n b n, que no es regular, pero aún no tiene contexto, pero ¿podemos también hacer coincidir a n b n c n , 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 $

poligenelubricantes
fuente
Sin duda, puede haber errores / errores tipográficos en esta respuesta larga, así que deje los comentarios como comentarios para que pueda revisarlos por mi cuenta.
polygenelubricants
Gran trabajo. Me tomará un tiempo leerlo, pero la última línea es básicamente imposible de leer; es una fuente tan pequeña. ------ Oh espera. ¿Es eso un feature? .... No estoy seguro si es una buena idea. Sé cuál es el último símbolo, pero no se puede leer (aparte de copiarlo y pegarlo).
Peter Ajtai
6
@Peter: Resalta el texto pequeño y copia y pega en otra cosa. Es difícil de leer a propósito: es un spoiler, la solución al acertijo adicional.
polygenelubricants
8
+1: Fantástica explicación, estos "artículos avanzados" son ideas brillantes.
Callum Rogers
1
@LarsH PHP preg_match()es un ejemplo de PCRE . Las expresiones regulares de Java parecen estar basadas en una versión anterior de las expresiones regulares de Perl . Lo que significa que las expresiones regulares de PHP son más poderosas que la versión en Java. A partir del 02/21/2013 , pcre.txt afirma que se corresponde aproximadamente con Perl 5.12 . Mientras que Perl está actualmente en 5.16, con 5.18 algunos meses de descanso. (En realidad, no se ha agregado mucho a las expresiones regulares en ese momento)
Brad Gilbert
20

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)$/
Jaytea
fuente
+1 wow, no sabía que PCRE admite patrones recursivos (¡todavía estoy aprendiendo! ¡Todos los días!). He revisado el artículo para incluir esta información. Sin a^n b^n c^nembargo, no creo que el patrón recursivo pueda coincidir .
polygenelubricants
Cabe señalar que esta opción es más simple, pero no tan buena como la respuesta publicada: la recursividad se desborda en cadenas largas.
Kobi
@Kobi Esto depende de tu definición de "bueno". Por ejemplo, la solución recursiva es alrededor de un orden de magnitud más rápida que la otra ( codepad.viper-7.com/CWgy7c ). Y es mucho más fácil de entender. La solución recursiva es prácticamente la transformación directa de la gramática en una expresión regular (en realidad, podría simplemente escribirla en la forma gramatizada, funcionaría).
NikiC
1
@polygeniclubricants, puede hacer coincidir ese patrón con dos patrones recursivos, uno para consumir as y bs sin capturar (y verifica que haya la misma cantidad con recursión), seguido de una expresión regular de captura que consume con avidez todas las a, y luego aplica el recursivo patrón a consumir y verificar que haya el mismo número de bsy cs. La expresión regular es: /^(?=(a(?-1)?b)c)a+(b(?-1)?c)$/x. Crédito a: nikic.github.io/2012/06/15/…
Josh Reback
11

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

Kennytm
fuente
1
@poly: Gracias :). En realidad, no estoy familiarizado con los patrones .NET, pero para este tipo de patrones resulta muy fácil equilibrar grupos, por lo que complementaré esta respuesta.
kennytm
¿Puedes hacer esto con un patrón recursivo? Porque si no puede, es un giro interesante que el grupo de equilibrio puede hacer cosas que el patrón recursivo no puede. (Y sí, agradezco mucho el suplemento).
poligenelubricantes
por cierto, la razón por la que omití la solución .NET fue porque tengo planes para "¿Cómo podemos combinar a^n b^ncon .NET regex?" artículo en el futuro, pero eres más que bienvenido a escribirlo si quieres. No estoy haciendo estos artículos solo para mí; Quiero animar a otros a que también lo hagan para tener un buen contenido en el sitio.
poligenelubricantes
Actualice si encuentra una manera de hacerlo con patrones recursivos. Jugué con grupos de equilibrio para capturar palabras cuyas longitudes hacen una serie de Fibonacci y no pude hacer que funcionara. Puede ser posible usar la función de mirar alrededor, similar a lo que he hecho.
Kobi
1
Solo me gustaría señalar que la versión PCRE de este patrón es un poco defectuosa, ya que coincide si el siguiente fragmento de caracteres es más largo que el anterior. Ver aquí: regex101.com/r/sdlRTm/1 es necesario agregar (?!b), (?!c)etc. después de que los grupos de captura, así: regex101.com/r/sdlRTm/2
jaytea