Cuantificadores codiciosos versus reacios vs. posesivos

Encontré este excelente tutorial sobre expresiones regulares y aunque intuitivamente entiendo lo que hacen los cuantificadores "codiciosos", "reacios" y "posesivos", parece que hay un serio vacío en mi comprensión.

Específicamente, en el siguiente ejemplo:

Enter your regex: .*foo  // greedy quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Enter your regex: .*?foo  // reluctant quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.

Enter your regex: .*+foo // possessive quantifier
Enter input string to search: xfooxxxxxxfoo
No match found.

La explicación menciona comer toda la cadena de entrada, cartas sido consumidos , coincidencias de dar marcha atrás , la aparición más a la derecha de "foo" ha sido regurgitado , etc.

Desafortunadamente, a pesar de las bonitas metáforas, todavía no entiendo qué come quién ... ¿Conoces otro tutorial que explique (concisamente) cómo funcionan los motores de expresiones regulares?

Alternativamente, si alguien puede explicar en una frase algo diferente el siguiente párrafo, eso sería muy apreciado:

El primer ejemplo usa el cuantificador codicioso. * Para encontrar "cualquier cosa", cero o más veces, seguido de las letras "f" "o" "o". Debido a que el cuantificador es codicioso, la porción. * De la expresión primero se come toda la cadena de entrada. En este punto, la expresión general no puede tener éxito, porque las últimas tres letras ("f" "o" "o") ya han sido consumidas (¿ por quién? ). Entonces, el marcador retrocede lentamente (¿ de derecha a izquierda? ) Una letra a la vez hasta que se regurgita la aparición más a la derecha de "foo" ( ¿qué significa esto? ), Momento en el que la coincidencia tiene éxito y la búsqueda termina.

Sin embargo, el segundo ejemplo es reacio, por lo que comienza consumiendo (¿ por quién? ) "Nada". Debido a que "foo" no aparece al comienzo de la cadena, se ve obligado a tragar (¿ quién traga?) La primera letra (una "x"), que desencadena la primera coincidencia en 0 y 4. Nuestro arnés de prueba continúa el proceso hasta que la cadena de entrada se agote. Encuentra otro partido a las 4 y 13.

El tercer ejemplo no puede encontrar una coincidencia porque el cuantificador es posesivo. En este caso, toda la cadena de entrada es consumida por. * +, ( ¿Cómo? ) Sin dejar nada para satisfacer el "foo" al final de la expresión. Use un cuantificador posesivo para situaciones en las que desea aprovechar todo sin retroceder ( ¿qué significa retroceder? ); superará al cuantificador codicioso equivalente en los casos en que la coincidencia no se encuentre de inmediato.

Lo intentaré.

Un cuantificador codicioso primero coincide tanto como sea posible. Entonces, .*coincide con toda la cadena. Luego, el emparejador intenta hacer coincidir lo fsiguiente, pero no quedan caracteres. Por lo tanto, "retrocede", haciendo que el cuantificador codicioso coincida con un carácter menos (dejando la "o" al final de la cadena sin igualar). Eso todavía no coincide fcon la expresión regular, por lo que retrocede un paso más, haciendo que el cuantificador codicioso vuelva a coincidir con un carácter menos (dejando el "oo" al final de la cadena sin igualar). Eso todavía no coincide con el fen la expresión regular, por lo que retrocede un paso más (dejando el "foo" al final de la cadena sin igual). Ahora, el emparejador finalmente coincide con el fen la expresión regular,ootambién son compatibles ¡Éxito!

Un cuantificador renuente o "no codicioso" primero coincide lo menos posible. Por lo tanto .*, no coincide con nada al principio, dejando toda la cadena sin igual. Luego, el emparejador intenta hacer coincidir lo fsiguiente, pero la parte no coincidente de la cadena comienza con "x", por lo que no funciona. Entonces el emparejador retrocede, haciendo que el cuantificador no codicioso coincida con un personaje más (ahora coincide con la "x", dejando "fooxxxxxxfoo" sin igual). Luego intenta hacer coincidir el f, que tiene éxito, y el oy el siguiente oen la coincidencia de expresiones regulares también. ¡Éxito!

En su ejemplo, comienza el proceso nuevamente con la parte restante no coincidente de la cadena, "xxxxxxfoo", siguiendo el mismo proceso.

Un cuantificador posesivo es como el cuantificador codicioso, pero no da marcha atrás. Por lo tanto, comienza haciendo .*coincidir toda la cadena, sin dejar nada sin igualar. Entonces no queda nada para que coincida con el fen la expresión regular. Como el cuantificador posesivo no retrocede, la coincidencia falla allí.

Es solo el resultado de mi práctica visualizar la escena.

No he escuchado los términos exactos 'regurgitar' o 'retroceder' antes; la frase que reemplazaría a estos es "retroceder", pero "regurgitar" parece una frase tan buena como cualquier otra para "el contenido que se había aceptado provisionalmente antes de retroceder".

Lo importante a tener en cuenta sobre la mayoría de los motores de expresiones regulares es que están retrocediendo : aceptarán tentativamente una coincidencia parcial potencial, mientras intentan hacer coincidir todo el contenido de la expresión regular. Si la expresión regular no puede coincidir completamente en el primer intento, entonces el motor de expresión regular retrocederá en una de sus coincidencias. Se tratará a juego *, +, ?, alternancia o {n,m}repetición diferente, y vuelve a intentarlo. (Y sí, este proceso puede llevar mucho tiempo).

El primer ejemplo usa el cuantificador codicioso. * Para encontrar "cualquier cosa", cero o más veces, seguido de las letras "f" "o" "o". Debido a que el cuantificador es codicioso, la porción. * De la expresión primero se come toda la cadena de entrada. En este punto, la expresión general no puede tener éxito, porque las últimas tres letras ("f" "o" "o") ya han sido consumidas (¿ por quién? ).

Las últimas tres letras, f, o, y oya estaban consumidos por la primera .*parte de la regla. Sin embargo, al siguiente elemento en la expresión regular, fno le queda nada en la cadena de entrada. El motor se verá obligado a retroceder en su .*partida inicial e intentar hacer coincidir el personaje menos el último. (Puede ser inteligente y retroceder a todos menos los últimos tres, porque tiene tres términos literales, pero no estoy al tanto de los detalles de implementación en este nivel).

Entonces, el emparejador retrocede lentamente (¿ de derecha a izquierda? ) Una letra a la vez hasta que se regurgita la aparición más a la derecha de "foo" ( ¿qué significa esto? ), En qué

Esto significa que se foohabía incluido tentativamente al hacer coincidir .*. Debido a que ese intento falló, el motor de expresiones regulares intenta aceptar un personaje menos .*. Si hubo una coincidencia exitosa antes de la .*de este ejemplo, entonces el motor probablemente trataría de acortar la .*coincidencia (de derecha a izquierda, como señaló, porque es un calificador codicioso), y si no pudo igualar la totalidad de los insumos, entonces podría ser obligado a volver a evaluar lo que había emparejado antes de la .*en mi ejemplo hipotético.

señalar que la coincidencia tiene éxito y la búsqueda finaliza.

Sin embargo, el segundo ejemplo es reacio, por lo que comienza consumiendo primero (¿ por quién? ) "Nada". Porque "foo"

La nada inicial es consumida por .?*, lo que consumirá la menor cantidad posible de cualquier cosa que permita que el resto de la expresión regular coincida.

no aparece al comienzo de la cadena, se ve obligado a tragar (¿ quién traga?)

Nuevamente, .?*consume el primer carácter, después de retroceder en la falla inicial para hacer coincidir la expresión regular completa con la coincidencia más corta posible. (En este caso, el motor regex está extendiendo el partido .*?de izquierda a derecha, porque .*?es reacio).

primera letra (una "x"), que activa la primera coincidencia en 0 y 4. Nuestro arnés de prueba continúa el proceso hasta que se agota la cadena de entrada. Encuentra otro partido a las 4 y 13.

El tercer ejemplo no puede encontrar una coincidencia porque el cuantificador es posesivo. En este caso, toda la cadena de entrada es consumida por. * +, ( ¿Cómo? )

A .*+consumirá tanto como sea posible y no retrocederá para encontrar nuevas coincidencias cuando la expresión regular en su conjunto no pueda encontrar una coincidencia. Debido a la forma posesiva no realiza la marcha atrás, es probable que no vea con muchos usos .*+, sino más bien con las clases de caracteres o restricciones similares: account: [[:digit:]]*+ phone: [[:digit:]]*+.

Esto puede acelerar drásticamente la coincidencia de expresiones regulares, porque le está diciendo al motor de expresiones regulares que nunca debe retroceder sobre coincidencias potenciales si una entrada no coincide. (Si tuviera que escribir todo el código coincidente a mano, esto sería similar a no usar nunca putc(3)para 'retroceder' un carácter de entrada. Sería muy similar al código ingenuo que se podría escribir en un primer intento. Excepto que los motores regex son mucho mejor que un solo carácter de retroceso, pueden rebobinar todo el retroceso a cero e intentar de nuevo. :)

Pero más que posibles aceleraciones, esto también puede permitirle escribir expresiones regulares que coincidan exactamente con lo que necesita. Tengo problemas para encontrar un ejemplo fácil :) pero escribir una expresión regular usando cuantificadores posesivos frente a codiciosos puede darte diferentes coincidencias, y uno u otro puede ser más apropiado.

sin dejar nada para satisfacer al "tonto" al final de la expresión. Use un cuantificador posesivo para situaciones en las que desea aprovechar todo sin retroceder ( ¿qué significa retroceder? ); superará

"Retroceder" en este contexto significa "retroceder": descartar una coincidencia parcial tentativa para intentar otra coincidencia parcial, que puede o no tener éxito.

el cuantificador codicioso equivalente en los casos en que la coincidencia no se encuentra de inmediato.

http://swtch.com/~rsc/regexp/regexp1.html

No estoy seguro de que esa sea la mejor explicación en Internet, pero está razonablemente bien escrita y adecuadamente detallada, y sigo volviendo a ella. Quizás quieras revisarlo.

Si desea un nivel más alto (explicación menos detallada), para expresiones regulares simples como la que está viendo, un motor de expresión regular funciona al retroceder. Básicamente, elige ("come") una sección de la cadena e intenta hacer coincidir la expresión regular con esa sección. Si coincide, genial. Si no, el motor altera su elección de la sección de la cadena e intenta hacer coincidir la expresión regular contra esa sección, y así sucesivamente, hasta que se pruebe todas las opciones posibles.

Este proceso se usa de forma recursiva: en su intento de hacer coincidir una cadena con una expresión regular dada, el motor dividirá la expresión regular en partes y aplicará el algoritmo a cada pieza individualmente.

La diferencia entre los cuantificadores codiciosos, renuentes y posesivos entra cuando el motor está haciendo la elección de con qué parte de la cadena tratar de hacer coincidir, y cómo modificar esa elección si no funciona la primera vez. Las reglas son las siguientes:

• Un cuantificador codicioso le dice al motor que comience con toda la cadena (o al menos, todo lo que no ha sido igualado por partes anteriores de la expresión regular) y verifique si coincide con la expresión regular. Si es así, genial; el motor puede continuar con el resto de la expresión regular. Si no, lo intenta nuevamente, pero recorta un carácter (el último) de la sección de la cadena que se va a verificar. Si eso no funciona, recorta a otro personaje, etc. Por lo tanto, un cuantificador codicioso verifica posibles coincidencias en orden de mayor a menor.

• Un cuantificador renuente le dice al motor que comience con la pieza más corta posible de la cadena. Si coincide, el motor puede continuar; de lo contrario, agrega un carácter a la sección de la cadena que se verifica y lo intenta, y así sucesivamente hasta que encuentre una coincidencia o se haya agotado toda la cadena. Por lo tanto, un cuantificador reacio verifica posibles coincidencias en orden de menor a mayor.

• Un cuantificador posesivo es como un cuantificador codicioso en el primer intento: le dice al motor que comience comprobando toda la cadena. La diferencia es que si no funciona, el cuantificador posesivo informa que la coincidencia falló en ese momento. El motor no cambia la sección de la cadena que se está mirando, y no hace más intentos.

Esta es la razón por la cual la coincidencia del cuantificador posesivo falla en su ejemplo: .*+se compara con la cadena completa, que coincide, pero luego el motor continúa buscando caracteres adicionales foodespués de eso, pero por supuesto no los encuentra, porque usted Ya estás al final de la cadena. Si se tratara de un cuantificador codicioso, retrocedería e intentaría hacer la .*única coincidencia hasta el penúltimo personaje, luego hasta el penúltimo carácter, luego hasta el penúltimo carácter, lo cual tiene éxito porque solo entonces es hay una fooizquierda después de que el .*ha "comido" la parte anterior de la cadena.

Aquí está mi opinión usando las posiciones de Celda e Índice (Vea el diagrama aquí para distinguir una Celda de un Índice).

Codicioso: coincide tanto como sea posible con el cuantificador codicioso y la expresión regular completa. Si no hay coincidencia, retroceda en el cuantificador codicioso.

Cadena de entrada: xfooxxxxxxfoo
Regex:. * Foo

El Regex anterior tiene dos partes:
(i) '. *' Y
(ii) 'foo'

Cada uno de los pasos a continuación analizará las dos partes. Los comentarios adicionales para una coincidencia con 'Pasar' o 'Fallar' se explican entre llaves.

Paso 1:
(i). * = Xfooxxxxxxfoo - PASS ('. *' Es un cuantificador codicioso y utilizará toda la cadena de entrada)
(ii) foo = No queda ningún carácter que coincida después del índice 13 - Falló la
coincidencia FAIL .

Paso 2:
(i). * = Xfooxxxxxxfo - PASS (Retroceso en el cuantificador codicioso '. *')
(Ii) foo = o - FAIL
Match fallido.

Paso 3:
(i). * = Xfooxxxxxxf - PASS (Retroceso en el cuantificador codicioso '. *')
(Ii) foo = oo - FAIL
Match falló.

Paso 4:
(i). * = Xfooxxxxxx - PASS (Retroceso en el cuantificador codicioso '. *')
(Ii) foo = foo - PASS
Report Match

Resultado: 1 coincidencia (es)
Encontré el texto "xfooxxxxxxfoo" comenzando en el índice 0 y terminando en el índice 13.

Reacio: haga coincidir lo menos posible con el cuantificador de reacios y haga coincidir la expresión regular completa. Si no hay coincidencia, agregue caracteres al cuantificador renuente.

Cadena de entrada: xfooxxxxxxfoo
Regex:. *? Foo

La expresión regular anterior tiene dos partes:
(i) '. *?' y
(ii) 'foo'

Paso 1:.
*? = '' (en blanco) - PASAR (Hacer coincidir lo menos posible con el cuantificador reacio '. *?'. El índice 0 que tiene '' es una coincidencia.)
foo = xfo - FALLO (Celda 0,1,2 - es decir, índice entre 0 y 3)
Partido fallido.

Paso 2:.
*? = X - PASS (Agrega personajes para el cuantificador reacios celular 0 tener 'x' es un partido '*.?'..)
Foo foo = - PASS
DEL PARTIDO

Paso 3:.
*? = '' (en blanco) - PASAR (Coincidir lo menos posible con el cuantificador reacio '. *?'. El índice 4 que tiene '' es una coincidencia.)
foo = xxx - FALLO (Celda 4,5,6 - es decir, índice entre 4 y 7)
Partido fallido.

Paso 4:.
*? = x - PASAR (Agregar caracteres al cuantificador renuente '. *?'. Celda 4.)
foo = xxx - FALLO (Celda 5,6,7 - es decir, índice entre 5 y 8)
Falló la coincidencia.

Paso 5:.
*? = xx - PASAR (Agregar caracteres al cuantificador reacio '. *?'. Celdas 4 a 5.)
foo = xxx - FALLO (Celda 6,7,8 - es decir, índice entre 6 y 9) La
coincidencia falló.

Paso 6:.
*? = xxx - PASAR (Agregar caracteres al cuantificador renuente '. *?'. Celdas 4 a 6.)
foo = xxx - FALLO (Celda 7,8,9 - es decir, índice entre 7 y 10) La
coincidencia falló.

Paso 7:.
*? = xxxx - PASAR (Agregar caracteres al cuantificador renuente '. *?'. Celda 4 a 7.)
foo = xxf - FALLO (Celda 8,9,10 - es decir, índice entre 8 y 11)
Falló la coincidencia.

Paso 8:.
*? = xxxxx - PASAR (Agregar caracteres al cuantificador renuente '. *?'. Celda 4 a 8.)
foo = xfo - FALLO (Celda 9,10,11 - es decir, índice entre 9 y 12) La
coincidencia falló.

Paso 9:.
*? = xxxxxx - PASS (Agregue caracteres al cuantificador reacio '. *?'. Celda 4 a 9.)
foo = foo - PASS (Celda 10,11,12 - es decir, índice entre 10 y 13)
Informe MATCH

Paso 10:.
*? = '' (Blanco) - PASS (Partido lo menos posible a la cuantificador renuente '*' Índice 13 está en blanco.?..)
Foo = n carácter a la izquierda para que coincida - FAIL (No hay nada después de índice 13 para que coincida)
Partido ha fallado.

Resultado: 2 coincidencias
Encontré el texto "xfoo" comenzando en el índice 0 y terminando en el índice 4.
Encontré el texto "xxxxxxfoo" comenzando en el índice 4 y terminando en el índice 13.

Posesivo: unir lo más posible al cuantificador posesivo y unir la expresión regular completa. NO retroceda.

Cadena de entrada: xfooxxxxxxfoo
Regex:. * + Foo

La expresión regular anterior tiene dos partes: '. * +' Y 'foo'.

Paso 1:.
* + = Xfooxxxxxxfoo - PASAR (Coincidir tanto como sea posible con el cuantificador posesivo '. *')
Foo = No queda ningún carácter para que coincida - FALLO (Nada que coincida después del índice 13)
Falló la coincidencia.

Nota: el retroceso no está permitido.

Resultado: 0 partido (s)

Codicioso: "coincide con la secuencia de personajes más larga posible"

Reacio: "coincide con la secuencia de caracteres más corta posible"

Posesivo: Esto es un poco extraño ya que NO (en contraste con la avaricia y la renuencia) intenta encontrar una coincidencia para toda la expresión regular.

Por cierto: ninguna implementación de igualador de patrones de expresiones regulares utilizará el retroceso. Todos los patrones de coincidencia de la vida real son extremadamente rápidos, ¡casi independientes de la complejidad de la expresión regular!

La codificación codiciosa implica la coincidencia de patrones utilizando todos los caracteres no validados restantes de una cadena durante una iteración. Los caracteres no validados comienzan en la secuencia activa . Cada vez que no se produce una coincidencia, el personaje al final se pone en cuarentena y la verificación se realiza nuevamente.

Cuando la secuencia activa solo satisface las condiciones principales del patrón regex, se intenta validar las condiciones restantes contra la cuarentena. Si esta validación es exitosa, los caracteres coincidentes en la cuarentena se validan y los caracteres no coincidentes residuales permanecen sin validar y se usarán cuando el proceso comience nuevamente en la próxima iteración.

El flujo de caracteres es de la secuencia activa a la cuarentena. El comportamiento resultante es que la mayor parte de la secuencia original se incluye en una coincidencia como sea posible.

La cuantificación reacia es casi lo mismo que la calificación codiciosa, excepto que el flujo de caracteres es lo contrario, es decir, comienzan en la cuarentena y fluyen hacia la secuencia activa . El comportamiento resultante es que se incluye lo menos posible de la secuencia original en una coincidencia.

La cuantificación posesiva no tiene cuarentena e incluye todo en una secuencia activa fija .