Cuantificadores codiciosos versus reacios versus posesivos

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

En concreto, 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 comió toda la cadena de entrada, que se consumieron letras , que el matcher retrocedió , que se regurgitó la aparición más a la derecha de "foo" , etc.

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

Alternativamente, si alguien puede explicar en una redacción 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 parte. * 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 comparador 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 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 principio de la cadena, se ve obligado a tragar (¿ quién traga?) La primera letra (una "x"), lo que activa 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 otra coincidencia en 4 y 13.

El tercer ejemplo no encuentra una coincidencia porque el cuantificador es posesivo. En este caso, la cadena de entrada completa es consumida por. * +, ( ¿Cómo? ) Sin dejar nada para satisfacer el "foo" al final de la expresión. Utilice un cuantificador posesivo para situaciones en las que desee apoderarse de todo algo sin siquiera 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 comparador intenta hacer coincidir lo fsiguiente, pero no quedan caracteres. Así que "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 con el fde 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 emparejar). Eso todavía no coincide con el fde la expresión regular, por lo que retrocede un paso más (dejando el "foo" al final de la cadena sin igualar). Ahora, el emparejador finalmente coincide con el fen la expresión regular, y el oy el siguiente otambién coinciden. ¡Éxito!

Un cuantificador reacio o "no codicioso" primero coincide lo menos posible. Entonces .*, no coincide con nada al principio, dejando toda la cadena sin emparejar. Luego, el comparador intenta hacer coincidir lo fsiguiente, pero la parte no coincidente de la cadena comienza con "x", por lo que no funciona. Así que el comparador retrocede, haciendo que el cuantificador no codicioso coincida con un carácter 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, luego comienza el proceso de nuevo con la parte no coincidente restante de la cadena, "xxxxxxfoo", siguiendo el mismo proceso.

Un cuantificador posesivo es como el cuantificador codicioso, pero no retrocede. Entonces comienza haciendo .*coincidir toda la cadena, sin dejar nada sin igual. Entonces no queda nada para que coincida con el fen la expresión regular. Dado que el cuantificador posesivo no retrocede, la coincidencia falla allí.

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

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

Lo importante a tener en cuenta acerca 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 puede coincidir completamente en el primer intento, el motor de expresiones regulares 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 parte. * 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 de la expresión regular, fno le queda nada en la cadena de entrada. El motor se verá obligado a retroceder en su .*coincidencia inicial e intentará hacer coincidir todos los caracteres menos el último. (Puede ser inteligente y retroceder a todos menos los últimos tres, porque tiene tres términos literales, pero no conozco los detalles de implementación en este nivel).

Entonces, el comparador 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 el cual

Esto significa que la foohabían tentativamente sido incluido cuando la concordancia .*. Debido a que ese intento falló, el motor de expresiones regulares intenta aceptar un carácter menos en .*. Si hubiera habido una persona compatible antes de la .*de este ejemplo, entonces el motor probablemente se trate de acortar el .*partido (de derecha a izquierda, como usted ha señalado, porque es un partido de clasificación codiciosos), y si era incapaz de 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.

punto, la coincidencia tiene éxito y la búsqueda finaliza.

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

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

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

Una vez más, .?*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 .*?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 otra coincidencia en 4 y 13.

El tercer ejemplo no encuentra 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 posibles coincidencias 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 uno podría escribir en un primer intento. Excepto que los motores de expresiones regulares son mucho mejor que un solo carácter de retroceso, pueden rebobinar todo el regreso a cero e intentarlo 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 vs codiciosos puede darte diferentes coincidencias, y una u otra puede ser más apropiada.

sin dejar nada para satisfacer el "foo" al final de la expresión. Utilice un cuantificador posesivo para situaciones en las que desee apoderarse de todo algo sin siquiera retroceder ( ¿qué significa retroceder? ); superará

En este contexto, "retroceder" significa "retroceder": desechar 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 inmediatamente.

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 detalladamente detallada, y sigo volviendo a ella. Quizás quieras revisarlo.

Si desea un nivel superior (explicación menos detallada), para expresiones regulares simples como la que está viendo, un motor de expresiones regulares funciona retrocediendo. Esencialmente, elige ("come") una sección de la cadena e intenta hacer coincidir la expresión regular con esa sección. Si coincide, genial. De lo contrario, 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 haya probado 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 parte individualmente.

La diferencia entre cuantificadores codiciosos, reacios y posesivos entra cuando el motor está eligiendo 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 la cadena completa (o al menos, toda ella que no haya sido igualada 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 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, recorta otro carácter, etc. Entonces, un cuantificador codicioso verifica las posibles coincidencias en orden de la más larga a la más corta.

• Un cuantificador reacio le dice al motor que arranque con el trozo más corto 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 intenta, y así sucesivamente hasta que encuentra una coincidencia o se ha agotado toda la cadena. Entonces, un cuantificador reacio verifica las 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 intento: le dice al motor que arranque verificando toda la cadena. La diferencia es que si no funciona, el cuantificador posesivo informa que la coincidencia falló en ese mismo 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 que la coincidencia del cuantificador posesivo falla en su ejemplo: .*+se verifica con la cadena completa, que coincide, pero luego el motor busca caracteres adicionales foodespués de eso, pero por supuesto no los encuentra, porque usted Ya estás al final de la cadena. Si fuera un cuantificador codicioso, retrocedería e intentaría hacer la .*única coincidencia hasta el penúltimo carácter, luego hasta el tercero hasta el último carácter, luego hasta el cuarto hasta el último carácter, que tiene éxito porque solo entonces es hay una fooizquierda después de que se .*haya "comido" la parte anterior de la cuerda.

Aquí está mi opinión sobre el uso de posiciones de celda e índice (consulte el diagrama aquí para distinguir una celda de un índice).

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

Cadena de entrada: xfooxxxxxxfoo
Regex:. * Foo

La expresión regular 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 de 'Aprobado' o 'No aprobado' 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 para coincidir después del índice 13 - FAIL
Match falló.

Paso 2:
(i). * = Xfooxxxxxxfo - PASS (Retroceso en el cuantificador codicioso '. *')
(Ii) foo = o - FAIL Falló la
coincidencia.

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

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

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

Reacio: haga coincidir lo menos posible con 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:
(i) '. *?' y
(ii) 'foo'

Paso 1:.
*? = '' (en blanco) - APROBADO (Coincide lo menos posible con el 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 (Agregue caracteres al cuantificador reacio '. *?'. La celda 0 que tiene 'x' es una coincidencia.)
foo = foo - PASS
Report MATCH

Paso 3:.
*? = '' (en blanco) - APROBADO (Coincide lo menos posible con el 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.

Paso 4:.
*? = x - APROBADO (Agregar caracteres al cuantificador reacio '. *?'. Celda 4.)
foo = xxx - FALLO (Celda 5,6,7 - es decir, índice entre 5 y 8)
Error de coincidencia.

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)
Error de coincidencia.

Paso 6:.
*? = xxx - APROBADO (Agregar caracteres al cuantificador reacio '. *?'. Celdas 4 a 6.)
foo = xxx - FALLO (Celda 7,8,9 - es decir, índice entre 7 y 10)
Error de coincidencia.

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) La
coincidencia falló.

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) Error de
coincidencia.

Paso 9:.
*? = xxxxxx - PASS (Agregar caracteres al cuantificador reacio '. *?'. Celdas 4 a 9.)
foo = foo - PASS (Celdas 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 fallido.

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: haga coincidir tanto como sea posible con el cuantificador posesivo y haga 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 - APROBADO (Coincidir tanto como sea posible con el cuantificador posesivo '. *')
Foo = No queda ningún carácter por coincidir - FALLO (Nada que coincidir después del índice 13)
Fallo en la coincidencia.

Nota: No se permite retroceder.

Resultado: 0 partido (s)

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

Reacio: "hacer coincidir la secuencia de caracteres más corta posible"

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

Por cierto: ninguna implementación de comparador de patrones de expresiones regulares utilizará el retroceso. Todos los comparadores de patrones de la vida real son extremadamente rápidos, ¡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 se vuelve a realizar la comprobación.

Cuando la secuencia activa solo satisface las condiciones principales del patrón de expresiones regulares, se intenta validar las condiciones restantes frente a la cuarentena. Si esta validación tiene éxito, los caracteres coincidentes en la cuarentena se validan y los caracteres residuales no coincidentes permanecen sin validar y se utilizarán cuando el proceso comience de nuevo en la siguiente 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.

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

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