Cuál es la diferencia entre .*? y. * expresiones regulares?

142

Estoy tratando de dividir una cadena en dos partes usando regex. La cadena tiene el siguiente formato:

text to extract<number>

He estado usando (.*?)<y <(.*?)>que funcionan bien, pero después de leer un poco en regex, comencé a preguntarme por qué necesito ?las expresiones. Solo lo hice así después de encontrarlos a través de este sitio, así que no estoy exactamente seguro de cuál es la diferencia.

Doug
fuente

Respuestas:

172

Es la diferencia entre cuantificadores codiciosos y no codiciosos.

Considere la entrada 101000000000100.

Utilizando 1.*1, *es codicioso - que coincidirá con todo el camino hasta el final, y luego dar marcha atrás hasta que pueda coincidir 1, dejándole con 1010000000001.
.*?No es codicioso. *no coincidirá con nada, pero luego intentará hacer coincidir caracteres adicionales hasta que coincida 1, finalmente coincidirá 101.

Todos los cuantificadores tienen un modo no expansivo: .*?, .+?, .{2,6}?, e incluso .??.

En su caso, un patrón similar podría ser <([^>]*)>: emparejar cualquier cosa menos un signo mayor que (estrictamente hablando, coincide con cero o más caracteres que no sean >intermedios <y >).

Ver la hoja de trucos del cuantificador .

Kobi
fuente
Ah, genial, me gusta el último de cualquier cosa menos el signo>.
Doug
1
¿Puedes explicar o mostrar un ejemplo de cómo el codicioso ?difiere del no codicioso ???
AdrianHHH
44
Por supuesto. Para la cadena "abc", la expresión regular /\w\w?\w/coincidiría con la cadena completa "abc", porque ?es codiciosa. /\w\w??\w/es vago, solo coincidirá "ab". Solo retrocederá y coincidirá "abc"si falla más tarde.
Kobi
184

En codicioso vs no codicioso

La repetición en regex por defecto es codiciosa : intentan igualar tantas repeticiones como sea posible, y cuando esto no funciona y tienen que retroceder, intentan igualar una repetición menos a la vez, hasta que coincida con todo el patrón. encontró. Como resultado, cuando finalmente ocurre una coincidencia, una repetición codiciosa coincidiría con tantas repeticiones como sea posible.

El ?cuantificador como repetición cambia este comportamiento a no codicioso , también llamado reacio ( en, por ejemplo, Java ) (y a veces "perezoso"). En contraste, esta repetición primero intentará igualar la menor cantidad posible de repeticiones, y cuando esto no funciona y tienen que retroceder, comienzan a emparejar un reptil más a la vez. Como resultado, cuando finalmente ocurre una coincidencia, una repetición reacia coincidiría con la menor cantidad posible de repeticiones.

Referencias


Ejemplo 1: de la A a la Z

Comparemos estos dos patrones: A.*Zy A.*?Z.

Dada la siguiente entrada:

eeeAiiZuuuuAoooZeeee

Los patrones producen las siguientes coincidencias:

Primero centrémonos en lo que A.*Zhace. Cuando coincide con el primero A, el .*, siendo codicioso, primero intenta igualar tantos .como sea posible.

eeeAiiZuuuuAoooZeeee
   \_______________/
    A.* matched, Z can't match

Como Zno coincide, el motor retrocede, y .*luego debe coincidir con uno menos .:

eeeAiiZuuuuAoooZeeee
   \______________/
    A.* matched, Z still can't match

Esto sucede algunas veces más, hasta que finalmente llegamos a esto:

eeeAiiZuuuuAoooZeeee
   \__________/
    A.* matched, Z can now match

Ahora Zpuede coincidir, por lo que el patrón general coincide:

eeeAiiZuuuuAoooZeeee
   \___________/
    A.*Z matched

Por el contrario, la repetición reacia en los A.*?Zprimeros partidos lo menos .posible, y luego tomar más .según sea necesario. Esto explica por qué encuentra dos coincidencias en la entrada.

Aquí hay una representación visual de lo que coincidieron los dos patrones:

eeeAiiZuuuuAoooZeeee
   \__/r   \___/r      r = reluctant
    \____g____/        g = greedy

Ejemplo: una alternativa

En muchas aplicaciones, las dos coincidencias en la entrada anterior es lo que se desea, por lo tanto, .*?se utiliza un reacio en lugar del codicioso .*para evitar la coincidencia excesiva. Sin embargo, para este patrón en particular, existe una alternativa mejor, utilizando la clase de caracteres negados.

El patrón A[^Z]*Ztambién encuentra las mismas dos coincidencias que el A.*?Zpatrón para la entrada anterior ( como se ve en ideone.com ). [^Z]es lo que se llama una clase de caracteres negados : coincide con cualquier cosa menos Z.

La principal diferencia entre los dos patrones está en el rendimiento: al ser más estricta, la clase de caracteres negados solo puede coincidir en un sentido para una entrada determinada. No importa si usa un modificador codicioso o reacio para este patrón. De hecho, en algunos sabores, puedes hacerlo aún mejor y usar lo que se llama cuantificador posesivo, que no retrocede en absoluto.

Referencias


Ejemplo 2: de A a ZZ

Este ejemplo debería ser ilustrativo: muestra cómo los patrones de clase de caracteres codiciosos, renuentes y negados coinciden de manera diferente dada la misma entrada.

eeAiiZooAuuZZeeeZZfff

Estas son las coincidencias para la entrada anterior:

Aquí hay una representación visual de lo que coincidieron:

         ___n
        /   \              n = negated character class
eeAiiZooAuuZZeeeZZfff      r = reluctant
  \_________/r   /         g = greedy
   \____________/g

Temas relacionados

Estos son enlaces a preguntas y respuestas en stackoverflow que cubren algunos temas que pueden ser de interés.

Una repetición codiciosa puede superar a otra

poligenelubricantes
fuente
1
Quise decir rubular.com, no ideone.com. Para otros: no revisen esta publicación por mí, lo haré yo mismo en la próxima revisión, junto con otros ejemplos. Siéntase libre de dar comentarios, sugerencias, etc. en los comentarios para que yo también pueda incorporarlos.
Polygenelubricants
2
Ver también: stackoverflow.com/questions/3145023/…
polygenelubricants
44
Esta respuesta se ha agregado a las Preguntas frecuentes sobre la expresión regular de desbordamiento de pila , en "Cuantificadores> Más sobre las diferencias ..."
aliteralmind
¡Esta respuesta realmente merece ser la respuesta elegida! Muchas gracias por tu explicación detallada.
masky007
Agregué la etiqueta no codiciosa . Por qué, porque la pregunta lo necesitaba, pero también porque atraerá a más usuarios a esta gran respuesta. En otras palabras, si da una respuesta excelente y la respuesta usa una etiqueta que no está en la pregunta, agregue la etiqueta porque el OP no sabía que la etiqueta era reveladora.
Guy Coder
21

Digamos que tienes:

<a></a>

<(.*)>coincidiría a></adonde <(.*?)>coincidiría a. Este último se detiene después del primer partido de >. Comprueba una o 0 coincidencias de .*seguido por la siguiente expresión.

La primera expresión <(.*)>no se detiene cuando coincide con la primera >. Continuará hasta el último partido de >.

Simón
fuente
Esto es más fácil de entender que la explicación anterior.
Prometeo