java - sheet - ¿Cuál es la diferencia entre los cuantificadores de expresión regular `Greedy` y` Reluctant`?

java util regex

Question

Desde el Pattern javadocs:

Greedy quantifiers: X? X, once or not at all X* X, zero or more times X+ X, one or more times X{n} X, exactly n times X{n,} X, at least n times X{n,m} X, at least n but not more than m times Reluctant quantifiers: X?? X, once or not at all X*? X, zero or more times X+? X, one or more times X{n}? X, exactly n times X{n,}? X, at least n times X{n,m}? X, at least n but not more than m times

La descripción de lo que hacen es la misma ... entonces, ¿cuál es la diferencia?

Realmente agradecería algunos ejemplos.

Estoy codificando en Java, pero escucho que este concepto es el mismo para la mayoría de las implementaciones de expresiones regulares modernas.

Answer 1

Desde este enlace , donde el autor del tutorial reconoce el espíritu de su pregunta:

A primera vista puede parecer que los cuantificadores X ?, X ?? y X? + hacen exactamente lo mismo, ya que todos prometen coincidir con "X, una vez o no". Existen diferencias de implementación sutiles que se explicarán cerca del final de esta sección.

Continúan reuniendo ejemplos y ofrecen la explicación:

Los cuantificadores codiciosos se consideran "codiciosos" porque obligan al emparejador a leer o comer toda la cadena de entrada antes de intentar la primera coincidencia. Si el primer intento de coincidencia (la cadena de entrada completa) falla, el emparejador retrocede la cadena de entrada con un carácter y lo intenta de nuevo, repitiendo el proceso hasta que se encuentre una coincidencia o ya no haya más caracteres para retroceder. Dependiendo del cuantificador usado en la expresión, lo último que intentará hacer coincidir es 1 o 0 caracteres.

Sin embargo, los cuantificadores renuentes adoptan el enfoque opuesto: comienzan al principio de la cadena de entrada y luego comen a regañadientes un personaje a la vez en busca de una coincidencia. Lo último que intentan es toda la cadena de entrada.

Y para crédito adicional, la explicación posesiva:

Finalmente, los cuantificadores posesivos siempre se comen toda la cadena de entrada, intentando una vez (y solo una vez) una coincidencia. A diferencia de los cuantificadores codiciosos, los cuantificadores posesivos nunca retroceden, incluso si hacerlo permitiría que el emparejamiento general tuviera éxito.

Answer 2

Hay documentación sobre cómo Perl maneja estos cuantificadores perldoc perlre .

De forma predeterminada, un subpatrón cuantificado es "codicioso", es decir, coincidirá tantas veces como sea posible (dada una ubicación de inicio particular) y al mismo tiempo permitirá que el resto del patrón coincida. Si desea que coincida con el número mínimo de veces posible, siga el cuantificador con un " ? ". Tenga en cuenta que los significados no cambian, solo la "codicia":

*? Match 0 or more times, not greedily +? Match 1 or more times, not greedily ?? Match 0 or 1 time, not greedily {n}? Match exactly n times, not greedily {n,}? Match at least n times, not greedily {n,m}? Match at least n but not more than m times, not greedily De forma predeterminada, cuando un subpatrón cuantificado no permite que el resto del patrón global coincida, Perl retrocederá. Sin embargo, este comportamiento es a veces indeseable. Por lo tanto, Perl también proporciona la forma cuantificadora "posesiva".

*+ Match 0 or more times and give nothing back ++ Match 1 or more times and give nothing back ?+ Match 0 or 1 time and give nothing back {n}+ Match exactly n times and give nothing back (redundant) {n,}+ Match at least n times and give nothing back {n,m}+ Match at least n but not more than m times and give nothing back Por ejemplo,

''aaaa'' =~ /a++a/ nunca coincidirá, ya que a++ se tragará todas las a ''s de la cadena y no dejará ninguna para la parte restante del patrón. Esta característica puede ser extremadamente útil para dar sugerencias a Perl sobre dónde no debe retroceder. Por ejemplo, el problema típico de "coincidir con una cadena entre comillas dobles" se puede realizar de manera más eficiente cuando se escribe como:

/"(?:[^"//]++|//.)*+"/ ya que sabemos que si la cita final no coincide, el seguimiento no ayudará. Vea la subexpresión independiente (?>...) para más detalles; Los cuantificadores posesivos son solo azúcar sintáctica para esa construcción. Por ejemplo, el ejemplo anterior también podría escribirse como sigue:

/"(?>(?:(?>[^"//]+)|//.)*)"/

Answer 3

Un cuantificador codicioso coincidirá tanto como sea posible y seguirá obteniendo una coincidencia Un cuantificador reacio coincidirá con la menor cantidad posible.

por ejemplo, dada la cadena

a B C D e F

el calificativo codicioso

ab [az] * [az] coincidiría con abcdef

el calificante reacio

ab [az] *? [az] coincidiría con abc

Answer 4

Un operador ambicioso siempre trata de "agarrar" la mayor cantidad de entrada posible, mientras que un cuantificador reacio coincidirá con la menor cantidad de entrada posible y creará una coincidencia.

Ejemplo:

"The red fox jumped over the red fence"
/(.*)red/ => /1 = "The red fox jumped over the "
/(.*?)red/ => /1 = "The "

"aaa"
/a?a*/ => /1 = "a", /2 = "aa"
/a??a*/ => /1 = "", /2 = "aaa"

"Mr. Doe, John"
/^(?:Mrs?.)?.*/b(.*)$/ => /1 = "John"
/^(?:Mrs?.)?.*?/b(.*)$/ => /1 = "Doe, John"

Answer 5

diga que tiene una expresión regular "a/w*b" , y "abab" en "abab" coincidencia codiciosa coincidirá con "abab" (busca una a , tantas apariciones de /w como sea posible y una b ) y una coincidencia renuente coincidirá solo con "ab" (tan poco como sea posible)