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

Question

De los 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 lo mismo ... así que, ¿cuál es la diferencia?

Realmente agradecería algunos ejemplos.

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

Answer 1

Un operador ambicioso siempre trata de "agarrar" la mayor cantidad de información posible, mientras que un cuantificador reacio hará coincidir la menor cantidad de información posible y aún así 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 2

Un cuantificador codicioso coincidirá tanto como sea posible y aún así obtener una coincidencia Un cuantificador reacio coincidirá con la menor cantidad posible.

por ejemplo, dada la cadena

abcdef

el calificador codiciosos

ab [az] * [az] se correspondería con abcdef

el calificador reacios

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

Answer 3

decir que tiene una expresión regular "a\w*b", y utilizarlo en "abab" juego Greedy coincidirá "abab" (se parece a un a, tanto las ocurrencias de \w como sea posible, y una b) y la coincidencia reacia coincidirá solo "ab" (como \w como sea posible)

Answer 4

De this link, donde el autor del tutorial reconoce s el espíritu de su pregunta:

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

Ellos van a juntar ejemplos y ofrecer la explicación:

cuantificadores codiciosos se consideran "codiciosos", porque obligan a la matcher para leer en, o comer, la cadena completa de entrada antes de intentar la primera coincidencia .Si el primer partido intento (toda la cadena de entrada) falla, el matcher retrocede el cadena de entrada por un personaje y trata otra vez, repitiendo el proceso hasta que se encuentra una coincidencia o no hay más quedan caracteres para respaldar apagado de. Dependiendo del cuantificador utilizado en la expresión, lo último que intentará contra es 1 o 0 caracteres.

Los cuantificadores renuentes, sin embargo, tomar el camino contrario: Comienzan al principio de la cadena de entrada, luego comer de mala gana un carácter a la vez buscando una coincidencia. La última cosa que intentan es la cadena de entrada completa.

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

Por último, los cuantificadores posesivos siempre comen toda la cadena de entrada, tratando una vez (y sólo una vez) para un partido . A diferencia de los cuantificadores codiciosos, los cuantificadores posesivos nunca retroceden, incluso si hacerlo permitiera que la coincidencia global se completara.

Answer 5

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) mientras permite 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 "avaricia": De forma predeterminada, cuando un subconjunto cuantificado no permite que el resto del patrón general coincida, Perl retrocederá. Sin embargo, este comportamiento es a veces indeseable. Por lo tanto, Perl también proporciona la forma de cuantificador "posesivo".

 
    *+  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 coinciden, como el a++ se engullir todos los a 's en la cadena y no dejar ninguna para la parte restante del patrón. Esta característica puede ser extremadamente útil para dar pistas sobre dónde no debe retroceder. Por ejemplo, el típico problema "emparejar una secuencia de comillas dobles" puede realizarse de la manera más eficiente cuando se escribe como:

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

porque sabemos que si la cita final no coincide, retroceder no ayudará. Consulte la subexpresión independiente (?>...) para obtener más detalles; Los cuantificadores posesivos son solo azúcar sintáctico para esa construcción. Por ejemplo, el ejemplo anterior también se puede escribir de la siguiente manera:

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