Codiciosos contra reacios versus cuantificadores posesivos

Encontré este excelente tutorial sobre expresiones regulares y, aunque entiendo intuitivamente lo que hacen los cuantificadores “codiciosos”, “reacios” y “posesivos”, parece que hay un agujero serio 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 que se ha comido toda la cadena de entrada, se han consumido las letras, se ha retrocedido el matcher, se ha regurgitado la ocurrencia más a la derecha de “foo”, etc.

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

Alternativamente, si alguien puede explicar en fraseología algo diferente el siguiente párrafo, 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 se han consumido (¿ por quién? ). Entonces, el emparejador retrocede lentamente (¿ de derecha a izquierda? ) Una letra a la vez hasta que la ocurrencia más a la derecha de “foo” ha sido regurgitada ( ¿qué significa esto? ), Momento en el que el partido tiene éxito y la búsqueda finaliza.

El segundo ejemplo, sin embargo, es reacio, por lo que comienza consumiendo primero (¿ 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 se agote la cadena de entrada. Encuentra otro partido en 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? ) Y no deja nada para satisfacer al “foo” al final de la expresión. Use un cuantificador posesivo para situaciones en las que desee aprovechar todo sin detenerse ( ¿qué significa retroceder? ); superará al cuantificador codicioso equivalente en los casos en que la coincidencia no se encuentre de manera inmediata.

Lo intentaré.

Un cuantificador codicioso primero coincide tanto como sea posible. Entonces el .* Coincide con la cadena completa. Entonces el emparejador intenta hacer coincidir los siguientes, pero no quedan caracteres. Así que “retrocede”, haciendo que el cuantificador codicioso coincida con una cosa menos (dejando la “o” al final de la cadena sin igual). Eso todavía no coincide con la f en la expresión regular, por lo que “da marcha atrás” un paso más, haciendo que el cuantificador codicioso coincida con una cosa menos otra vez (dejando el “oo” al final de la secuencia sin igual). Eso todavía no coincide con la f en 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 f en la expresión regular, y el o y el siguiente o se corresponden. ¡Éxito!

Un cuantificador reacio o “no codicioso” primero coincide lo menos posible. Entonces el .* coincide con nada al principio, dejando la secuencia completa sin igual. Luego, el emparejador intenta hacer coincidir el f siguiente, pero la parte incomparable de la cadena comienza con “x”, por lo que no funciona. Así que el emparejador retrocede, haciendo que el cuantificador no codicioso coincida con una cosa más (ahora coincide con la “x”, dejando “fooxxxxxxfoo” sin igual). Luego intenta hacer coincidir la f , que tiene éxito, y la o y la siguiente o en la expresión regular también. ¡Éxito!

En su ejemplo, luego comienza el proceso otra vez con la porción restante no igualada de la cadena, siguiendo el mismo proceso.

Un cuantificador posesivo es como el cuantificador codicioso, pero no retrocede. Por lo tanto, comienza con .* Haciendo coincidir toda la cadena, sin dejar nada sin igual. Entonces no queda nada para que coincida con la f en la expresión regular. Como el cuantificador posesivo no retrocede, la coincidencia falla allí.

Es solo mi salida de práctica para visualizar la escena-

Imagen visual

No escuché los términos exactos ‘regurgitar’ o ‘retroceder’ antes; la frase que reemplazaría estos es “retroceder”, pero “regurgitar” parece una frase tan buena como cualquiera para “el contenido que se había aceptado tentativamente antes de retroceder y tirarlo de nuevo”.

Lo importante para darse cuenta de 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 se puede emparejar por completo en el primer bash, el motor regex retrocederá en una de sus coincidencias. Intentará hacer coincidir * , + ? , alternancia o {n,m} repetición de manera diferente, y vuelva 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 se han consumido (¿ por quién? ).

Las últimas tres letras, f , o , y o ya fueron consumidas por la porción inicial .* de la regla. Sin embargo, el siguiente elemento en la expresión regular, f , no tiene nada en la cadena de entrada. El motor se verá forzado a dar marcha atrás en su coincidencia inicial .* , E intente hacer coincidir el carácter de todos menos el último. (Podría ser inteligente y dar marcha atrás a todos-pero-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 la ocurrencia más a la derecha de “foo” ha sido regurgitada ( ¿qué significa esto? ), A lo que

Esto significa que el foo ha sido incluido tentativamente al hacer coincidir .* . Como ese bash falló, el motor de expresiones regulares intenta aceptar un carácter menos .* . Si hubiera habido una coincidencia exitosa antes del .* En este ejemplo, entonces el motor probablemente trataría de acortar el fósforo .* (De derecha a izquierda, como usted señaló, porque es un calificador codicioso), y si no pudo hacer coincidir todas las entradas, entonces podría verse obligado a volver a evaluar lo que había coincidido antes de .* en mi ejemplo hipotético.

señale que el partido tiene éxito y la búsqueda termina.

El segundo ejemplo, sin embargo, es reacio, por lo que comienza consumiendo primero (¿ por quién? ) “Nada”. Porque “foo”

La inicial nada es consumida por .?* , Que consumirá la cantidad más corta posible de cualquier cosa que permita que el rest de la expresión regular coincida.

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

De nuevo, el .?* Consume el primer carácter, después de retroceder en la falla inicial para hacer coincidir toda la expresión regular con la coincidencia más corta posible. (En este caso, el motor de expresiones regulares está extendiendo la coincidencia para .*? De izquierda a derecha, porque .*? Es reacio).

primera letra (una “x”), que desencadena 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 en 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 que la forma posesiva no realiza retrocesos, probablemente no verá muchos usos con .*+ , Sino con 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 dar marcha atrás sobre posibles coincidencias si una entrada no coincide. (Si tuviera que escribir todo el código coincidente a mano, sería similar a nunca usar putc(3) para “rechazar” un carácter de entrada. Sería muy similar al código ingenuo que se podría escribir en un primer bash. Excepto que los motores regex son mucho mejores que un solo carácter de push-back, pueden retroceder a cero e intentar nuevamente :).

Pero más que las posibles aceleraciones, esto también te permite escribir expresiones regulares que coincidan exactamente con lo que necesitas unir. Tengo problemas para encontrar un ejemplo fácil 🙂 pero escribir una expresión regular usando cuantificadores posesivos vs codiciosos puede darte diferentes coincidencias, y una u otra pueden ser más apropiadas.

no queda nada para satisfacer al “foo” al final de la expresión. Use un cuantificador posesivo para situaciones en las que desee aprovechar todo sin detenerse ( ¿qué significa retroceder? ); superará

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

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

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

No estoy seguro de que 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 superior (explicación menos detallada), para las expresiones regulares simples como la que está viendo, un motor de expresiones regulares funciona retrocediendo. 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 con esa sección, y así sucesivamente, hasta que se intente con todas las opciones posibles.

Este proceso se usa de forma recursiva: en su bash por 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 hace su elección de qué parte de la cadena tratará de coincidir, y cómo modificar esa opción si no funciona la primera vez. Las reglas son las siguientes:

  • Un cuantificador codicioso le dice al motor que comience con la cadena completa (o al menos, toda ella que no haya sido igualada por partes previas de la expresión regular) y verifique si coincide con la expresión regular. Si es así, genial; el motor puede continuar con el rest de la expresión regular. De lo contrario, intenta de nuevo, pero recortando un carácter (el último) de la sección de la cadena que se va a verificar. Si eso no funciona, elimina a otro personaje, etc. Por lo tanto, un cuantificador codicioso verifica posibles coincidencias en orden de más largo a más corto.

  • Un cuantificador reacio le dice al motor que comience con la parte más corta posible de la cuerda. Si coincide, el motor puede continuar; de lo contrario, agrega un carácter a la sección de la cadena que se está verificando y lo prueba, y así sucesivamente hasta que encuentra una coincidencia o toda la cadena se ha agotado. Por lo tanto, un cuantificador reacio verifica posibles coincidencias en orden de la más corta a la más larga.

  • Un cuantificador posesivo es como un cuantificador codicioso en el primer bash: le dice al motor que comience por verificar 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 bashs.

Esta es la razón por la cual la coincidencia del cuantificador posesivo falla en su ejemplo: el .*+ Se compara con la cadena completa, que coincide, pero luego el motor continúa buscando caracteres adicionales foo después de eso, pero por supuesto no encuentra ellos, porque ya estás al final de la cadena. Si fuera un cuantificador codicioso, retrocedería y trataría de hacer que el .* solo con el penúltimo carácter, luego hasta el penúltimo carácter, y luego hasta el penúltimo carácter, que tiene éxito porque solo luego queda un foo después de que .* haya “comido” la parte anterior de la cadena.

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

Codicioso: empareja 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

La Regex anterior tiene dos partes:
(yo y
(ii) ‘foo’

Cada uno de los pasos a continuación analizará las dos partes. Los comentarios adicionales para una coincidencia con ‘Pase’ o ‘Fallo’ se explican entre corchetes.

Paso 1:
(i). * = xfooxxxxxxfoo – PASS (‘. *’ es un cuantificador codicioso y usará toda la cadena de entrada)
(ii) foo = No queda ningún carácter que coincida después del índice 13 – FALLA
Partido fallido

Paso 2:
(i). * = xfooxxxxxxfo – PASS (retroceso en el cuantificador codicioso ‘. *’)
(ii) foo = o – FAIL
Partido fallido

Paso 3:
(i). * = xfooxxxxxxf – PASS (retroceso en el cuantificador codicioso ‘. *’)
(ii) foo = oo – FALLO
Partido fallido

Etapa 4:
(i). * = xfooxxxxxx – PASS (retroceso en el cuantificador codicioso ‘. *’)
(ii) foo = foo – PASS
Informe MATCH

Resultado: 1 partido (s)
Encontré el texto “xfooxxxxxxfoo” comenzando en el índice 0 y terminando en el índice 13.

Renuente: haga coincidir lo menos posible el cuantificador reacio y haga coincidir toda la expresión regular. si no hay coincidencia, agregue caracteres al cuantificador reacio.

Cadena de entrada: xfooxxxxxxfoo
Regex:. *? Foo

La expresión regular anterior tiene dos partes:
(yo) ‘.*?’ y
(ii) ‘foo’

Paso 1:
. *? = ” (en blanco) – PASS (unir lo menos posible al cuantificador reacio ‘. *?’. El índice 0 que tiene ” es una coincidencia).
foo = xfo – FAIL (celda 0,1,2 – es decir, índice entre 0 y 3)
Partido fallido

Paso 2:
. *? = x – PASS (Agregar caracteres al cuantificador reacio ‘. *?’. La celda 0 que tiene ‘x’ es una coincidencia).
foo = foo – PASS
Informe MATCH

Paso 3:
. *? = ” (en blanco) – PASS (unir lo menos posible al cuantificador reacio ‘. *?’. El índice 4 que tiene ” es una coincidencia).
foo = xxx – FAIL (celda 4,5,6 – es decir, índice entre 4 y 7)
Partido fallido

Etapa 4:
. *? = x – PASS (Agregar caracteres al cuantificador reacio ‘. *?’. Celda 4.)
foo = xxx – FAIL (celda 5,6,7 – es decir, índice entre 5 y 8)
Partido fallido

Paso 5:
. *? = xx – PASS (Agregar caracteres al cuantificador reacio ‘. *?’. Celda 4 a 5.)
foo = xxx – FAIL (celda 6,7,8 – es decir, índice entre 6 y 9)
Partido fallido

Paso 6:
. *? = xxx – PASS (Agregar caracteres al cuantificador reacio ‘. *?’. Celda 4 a 6.)
foo = xxx – FAIL (celda 7,8,9 – es decir, índice entre 7 y 10)
Partido fallido

Paso 7:
. *? = xxxx – PASS (Agregar caracteres al cuantificador reacio ‘. *?’. Celda 4 a 7.)
foo = xxf – FAIL (celda 8,9,10 – es decir, índice entre 8 y 11)
Partido fallido

Paso 8:
. *? = xxxxx – PASS (Agregar caracteres al cuantificador reacio ‘. *?’. Celda 4 a 8.)
foo = xfo – FAIL (celda 9,10,11 – es decir, índice entre 9 y 12)
Partido fallido

Paso 9:
. *? = xxxxxx – PASS (Agregar 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:
. *? = ” (en blanco) – PASS (unir lo menos posible al cuantificador reacio ‘. *?’. El índice 13 está en blanco).
foo = No queda ningún carácter para que coincida – FAIL (No hay nada después del índice 13 para que coincida)
Partido fallido

Resultado: 2 partido (s)
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: combina tanto como sea posible con el cuantificador posesivo y haz coincidir toda la expresión regular. NO retroceda.

Cadena de entrada: xfooxxxxxxfoo
Regex:. * + Foo

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

Paso 1:
. * + = xfooxxxxxxfoo – PASS (coincida tanto como sea posible con el cuantificador posesivo ‘. *’)
foo = No queda ningún caracter para que coincida – FAIL (Nada que coincida después del índice 13)
Partido fallido

Nota: Retroceder no está permitido.

Resultado: 0 partido (s)

Codicioso: “unir la secuencia de caracteres más larga posible”

Reacio: “unir la secuencia de caracteres más corta posible”

Posesivo: Esto es un poco extraño, ya que NO (a diferencia de codicioso y reacio) intenta encontrar una coincidencia para toda la expresión regular.

Por cierto: ninguna implementación de matcher de patrones regex usará backtracking alguna vez. Todas las combinaciones de patrones de la vida real son extremadamente rápidas, ¡casi independientes de la complejidad de la expresión regular!

La cuantificació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 satisface solo las principales condiciones del patrón de expresión regular, se intenta validar las condiciones restantes con respecto a la cuarentena. Si esta validación es exitosa, los caracteres coincidentes en la cuarentena se validan y los caracteres residuales no coincidentes permanecen sin validar y se usarán cuando el proceso comience de nuevo en la siguiente iteración.

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

La cuantificación reacia es casi igual a la calificación codiciosa, excepto que el flujo de caracteres es el opuesto, es decir, comienzan en la cuarentena y fluyen hacia la secuencia activa . El comportamiento resultante es que se incluye tan poca secuencia original en un partido como sea posible.

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