regular - regex repeat pattern
Codiciosos contra reacios contra cuantificadores posesivos (7)
Aquí está mi opinión sobre las posiciones de celda e índice (vea el diagrama aquí para distinguir una celda de un índice).
Codicioso: haga coincidir tanto como sea posible con el cuantificador codicioso y la expresión regular completa. Si no hay coincidencia, retrocede en el cuantificador codicioso.
Cadena de entrada: xfooxxxxxxfoo
Regex:. * Foo
El 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 ''Pasar'' o ''Error'' 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 - FALLO
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 - FAIL
Partido fallido
Etapa 4:
(i). * = xfooxxxxxx - PASS (Retroceso en el cuantificador codicioso ''. *'')
(ii) foo = foo - PASS
Informe MATCH
Resultado: 1 partido (es)
Encontré el texto "xfooxxxxxxfoo" comenzando en el índice 0 y terminando en el índice 13.
Renuente: haga coincidir lo menos posible con el cuantificador renuente y haga coincidir toda la expresión regular. si no hay coincidencia, agregue caracteres al cuantificador reacio.
Cadena de entrada: xfooxxxxxxfoo
Regex:. *? Foo
El regex anterior tiene dos partes:
(yo) ''.*?'' y
(ii) ''foo''
Paso 1:
. *? = '''' (en blanco) - PASAR (Hacer coincidir lo menos posible con el cuantificador renuente ''. *?''. 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 - PASAR (Agregar caracteres al cuantificador renuente ''. *?''. La celda 0 que tiene ''x'' es una coincidencia.)
foo = foo - PASS
Informe MATCH
Paso 3:
. *? = '''' (en blanco) - PASAR (Hacer coincidir 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
Etapa 4:
. *? = x - PASAR (Agregar caracteres al cuantificador reacio ''. *?''. Celda 4.)
foo = xxx - FAIL (Célula 5,6,7 - índice entre 5 y 8)
Partido fallido
Paso 5:
. *? = xx - PASAR (Agregar caracteres al cuantificador renuente ''. *?''. Celda 4 a 5.)
foo = xxx - FAIL (Celda 6,7,8 - índice entre 6 y 9)
Partido fallido
Paso 6:
. *? = xxx - PASAR (Agregar caracteres al cuantificador renuente ''. *?''. Celda 4 a 6.)
foo = xxx - FAIL (celda 7,8,9 - índice entre 7 y 10)
Partido fallido
Paso 7:
. *? = xxxx - PASAR (Agregar caracteres al cuantificador reacio ''. *?''. Celda 4 a 7.)
foo = xxf - FALLO (Célula 8,9,10 - es decir, índice entre 8 y 11)
Partido fallido
Paso 8:
. *? = xxxxx - PASAR (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 - PASAR (Agregar caracteres al cuantificador renuente ''. *?''. Celda 4 a 9.)
foo = foo - PASS (celda 10,11,12 - es decir, índice entre 10 y 13)
Informe MATCH
Paso 10:
. *? = '''' (en blanco) - PASAR (Haga coincidir lo menos posible con el cuantificador renuente ''. *?''. El índice 13 está en blanco.)
foo = No queda ningún carácter para coincidir - FALLO (no hay nada después del índice 13 para coincidir)
Partido fallido
Resultado: 2 match (es)
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 - PASAR (Hacer coincidir tanto como sea posible con el cuantificador posesivo ''. *'')
foo = No queda ningún carácter para hacer coincidir - FALLO (No hay ninguna coincidencia después del índice 13)
Partido fallido
Nota: Backtracking no está permitido.
Resultado: 0 match (es)
Encontré este excelente tutorial sobre expresiones regulares y si bien intuitivamente entiendo lo que hacen los cuantificadores "codiciosos", "reacios" y "posesivos", parece haber 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 cancelado el emparejamiento, se ha regurgitado la aparición más a la derecha de "foo", etc.
Desafortunadamente, a pesar de las bonitas metáforas, todavía no entiendo lo que come quién ... ¿Conoces otro tutorial que explique (de manera concisa) 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 utiliza 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 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? ). Por lo tanto, el emparejador retrocede lentamente ( de derecha a izquierda ) una letra a la vez hasta que la aparición más a la derecha de "foo" haya sido regurgitada ( ¿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 por consumir primero (¿ por quién? ) "Nada". Debido a que "foo" no aparece al principio de la cadena, se ve obligada a tragar (¿ quién traga?) La primera letra (una "x"), que activa 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 los 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. Use un cuantificador posesivo para situaciones en las que desea aprovechar todo sin tener que retroceder ( ¿qué significa retroceder? ); superará al cuantificador codicioso equivalente en los casos en que la coincidencia no se encuentre inmediatamente.
Codicioso: "coincide con la secuencia de caracteres más larga posible"
Renuente: "coincide con la secuencia de caracteres más corta posible"
Posesivo: esto es un poco extraño, ya que NO (en contraste con los codiciosos y reacios) intenta encontrar una coincidencia para toda la expresión regular.
Por cierto: ninguna implementación de emparejador de patrones de expresiones regulares utilizará nunca 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!
No he escuchado los términos exactos ''regurgitar'' o ''retroceder'' antes; la frase que reemplazaría esto es "retroceso", pero ''regurgitar'' parece una frase tan buena como cualquiera para "el contenido que había sido aceptado tentativamente antes de retroceder lo tiró de nuevo".
Lo importante a tener en cuenta acerca de la mayoría de los motores de expresiones regulares es que están dando marcha atrás : aceptarán tentativamente una coincidencia parcial parcial, mientras intentan hacer coincidir todo el contenido de la expresión regular. Si la expresión regular no se puede hacer coincidir completamente en el primer intento, entonces el motor de expresiones regulares retrocederá en una de sus coincidencias. Intentará emparejar * , + ? , alternancia, o {n,m} repetición diferente, e intente de nuevo. (Y sí, este proceso puede llevar mucho tiempo).
El primer ejemplo utiliza 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 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 ya fueron consumidas por la parte inicial .* la regla. Sin embargo, el siguiente elemento en la expresión regular, f , no tiene nada más en la cadena de entrada. El motor será forzado a dar marcha atrás en su coincidencia inicial .* , Y tratar de hacer coincidir todos los caracteres pero el último. (Puede ser inteligente y dar marcha atrás a todos menos a los tres últimos, porque tiene tres términos literales, pero no conozco los detalles de la implementación en este nivel).
Por lo tanto, el emparejador retrocede lentamente ( de derecha a izquierda ) una letra a la vez hasta que la aparición más a la derecha de "foo" haya sido regurgitada ( ¿qué significa esto? ), En la que
Esto significa que el foo había sido tentativamente incluido al emparejar .* . Debido a que el intento falló, el motor de expresiones regulares intenta aceptar un carácter menos en .* . Si hubiera habido una coincidencia exitosa antes de .* En este ejemplo, entonces el motor probablemente intentaría acortar la coincidencia .* (De derecha a izquierda, como se señaló, porque es un calificativo codicioso), y si no fue capaz de hacer coincidir todas las entradas, por lo que podría verse obligado a volver a evaluar lo que había coincidido antes de .* en mi ejemplo hipotético.
punto el partido tiene éxito y la búsqueda termina.
El segundo ejemplo, sin embargo, es reacio, por lo que comienza por consumir 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 obliga a tragar (¿ quién traga?) el
Nuevamente, el .?* Consume el primer carácter, después de retroceder en el fallo 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 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 los 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 totalidad no encuentre una coincidencia. Debido a que la forma posesiva no realiza el retroceso, 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 retroceder sobre las posibles coincidencias si una entrada no coincide. (Si tuviera que escribir todo el código coincidente a mano, esto sería similar a no utilizar nunca putc(3) para "empujar" 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 de expresiones regulares son mucho mejores que un solo carácter de retroceso, pueden rebobinar todo el respaldo a cero e intentarlo de nuevo. :)
Pero más que los posibles incrementos de velocidad, esto también puede permitirle escribir expresiones regulares que coincidan exactamente con lo que necesita para coincidir. Estoy teniendo problemas para dar un ejemplo fácil :) pero escribir una expresión regular utilizando cuantificadores posesivos y codiciosos puede dar diferentes coincidencias, y una u otra puede ser más apropiada.
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 tener que retroceder ( ¿qué significa retroceder? ); superará
"Retroceder" en este contexto significa "retroceder": eliminar una coincidencia parcial provisional 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.
Voy a darle una oportunidad.
Un cuantificador codicioso primero coincide tanto como sea posible. Así que el .* Coincide con toda la cadena. Luego, el emparejador intenta coincidir con la f siguiente, pero no quedan caracteres. Así que "retrocede", haciendo que el codificador codicioso coincida con una cosa menos (dejando la "o" al final de la cadena sin emparejar). Eso todavía no coincide con la f en la expresión regular, así que "retrocede" un paso más, haciendo que el codificador codicioso coincida con una cosa menos otra vez (dejando el "oo" al final de la cadena sin emparejar). Eso aún 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 emparejar). Ahora, el emparejador finalmente coincide con la f en la expresión regular, y la o y la siguiente o también coinciden. ¡Éxito!
Un cuantificador reacio o "no codicioso" primero hace coincidir lo menos posible. Así que el .* coincide con nada al principio, dejando la cadena entera sin igual. Luego, el emparejador intenta coincidir con la f siguiente, pero la parte no coincidente 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 "fooxxxxxxxo" sin emparejar). Luego trata de hacer coincidir la f , que tiene éxito, y la o y la siguiente o en la expresión regular también coinciden. ¡Éxito!
En su ejemplo, luego comienza el proceso nuevamente con la parte restante no coincidente de la cadena, siguiendo el mismo proceso.
Un cuantificador posesivo es como el cuantificador codicioso, pero no retrocede. Así que comienza con .* Coincidiendo con toda la cadena, sin dejar nada inigualable. 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í.
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 tiene los detalles adecuados, y sigo volviendo a ella. Quizás quieras revisarlo.
Si desea un nivel más alto (una explicación menos detallada), para expresiones regulares simples como la que está viendo, un motor de expresiones regulares funciona por retroceso. Esencialmente, 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 pruebe cada opción posible.
Este proceso se usa recursivamente: 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, reacios y posesivos entra cuando el motor toma sus decisiones de con qué parte de la cadena tratar de emparejar, 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 toda la cadena (o al menos, todo lo que no ha sido igualado por partes anteriores de la expresión regular) y verifica 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 recorta 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. Por lo tanto, un cuantificador codicioso comprueba las posibles coincidencias en orden, de mayor a menor.
Un cuantificador reacio le dice al motor que comience con la pieza más corta posible de la cuerda. Si coincide, el motor puede continuar; si no, agrega un carácter a la sección de la cadena que se está verificando e intenta eso, y así sucesivamente hasta que encuentre una coincidencia o la cadena completa se haya agotado. Por lo tanto, un cuantificador reacio verifica las 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 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á viendo y no hace más intentos.
Esta es la razón por la que la coincidencia del cuantificador posesivo falla en su ejemplo: el .*+ comprueba con la cadena completa, que coincide, pero luego el motor busca 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, daría marcha atrás y trataría de hacer que .* Solo coincida con el carácter del último al último, luego del tercer al último carácter, y luego del cuarto al último carácter, que tiene éxito porque solo entonces hay un foo izquierda después de que .* haya "comido" la parte anterior de la cadena.
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 carácter al final se pone en cuarentena y la verificación se realiza de nuevo.
Cuando la secuencia activa solo satisface las condiciones iniciales del patrón de expresiones regulares, 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 utilizarán cuando el proceso comience nuevamente 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 como sea posible.
La cuantificación renuente es casi lo mismo que 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 tan poco de la secuencia original se incluye en una coincidencia como sea posible.
La Cuantificación Posesiva no tiene una cuarentena e incluye todo en una secuencia activa fija.