Los cuantificadores greedy, reluctant y possessive en expresiones regulares

Escrito por el .
java planeta-codigo programacion
Enlace permanente Comentarios

En el mundo de las expresiones regulares hay tres tipos de cuantificadores que varían el comportamiento según el número caracteres que toman para encontrar ocurrencias. Son greedy o avaricioso, reluctant o reacio y possessive o posesivo. Cada cuantificador tiene una expresión en una expresión regular. La opción más habitual es el cuantificador greedy, añadiendo una ? se convierte en reluctant y añadiendo un + se convierte en possessive.

Greedy  Reluctant  Possessive  Significado
X?      X??        X?+         X, uno o ninguno
X*      X*?        X*+         X, cero o mas
X+      X+?        X++         X, uno o más
X{n}    X{n}?      X{n}+       X, exactamente n veces
X{n,}   X{n,}?     X{n,}+      X, al menos n veces
X{n,m}  X{n,m}?    X{n,m}+     X, al menos n veces pero no mas de m

Aparentemente cada uno de los cuantificadores realiza lo mismo, sin embargo, hay diferencias en su comportamiento al hacer emparejamientos entre los elementos de la expresión regular y la cadena en la que se está aplicando.

  • Greedy o avaricioso: este cuantificador intenta obtener el emparejamiento más largo que pueda, tantos caracteres como pueda, si el emparejamiento no es válido elimina un caracter de la cadena que se está comprobando y lo intenta de nuevo.
  • Reluctant, reacio o vago: funciona al contrario que el cuantificador greedy, intentando inicialmente ningún caracter, tan pocos caracteres como pueda, si el emparejamiento no es válido añade un caracter de la cadena que se está comprobando y lo intenta de nuevo.
  • Possessive o posesivo: funciona igual que greedy salvo que si el emparejamiento no es válido no elimina un caracter de la cadena que se está comprobando y finaliza la comprobación.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package io.github.picodotdev.blogbitix.javaregexquantifiers;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    public static void main(String[] args) {
		String[] tests = new String[] {
			"Greedy",     "xfooxxxxxxfoo", ".*foo",
			"Reluctant",  "xfooxxxxxxfoo", ".*?foo",
			"Possessive", "xfooxxxxxxfoo", ".*+foo",
			"Greedy",     "xfooxxxxxxfoo", ".{2,5}",
			"Reluctant",  "xfooxxxxxxfoo", ".{2,5}?",
			"Possessive", "xfooxxxxxxfoo", ".{2,5}+"
		};

		for (int i = 0; i < tests.length; i += 3) {
			String quantifier = tests[i];
			String string = tests[i + 1];
			String regex = tests[i + 2];

		    System.out.printf("%s, %s, %s%n", quantifier, string, regex);

		    {
		        Pattern pattern = Pattern.compile(regex);
		        Matcher matcher = pattern.matcher(string);
		        while (matcher.find()) {
		            System.out.printf("I found the text \"%s\" starting at index %d and ending at index %d.%n", matcher.group(), matcher.start(), matcher.end());
		        }
		    }

		    System.out.println();
		}
    }
}
Main.java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Greedy, xfooxxxxxxfoo, .*foo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Reluctant, xfooxxxxxxfoo, .*?foo
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.

Possessive, xfooxxxxxxfoo, .*+foo

Greedy, xfooxxxxxxfoo, .{2,5}
I found the text "xfoox" starting at index 0 and ending at index 5.
I found the text "xxxxx" starting at index 5 and ending at index 10.
I found the text "foo" starting at index 10 and ending at index 13.

Reluctant, xfooxxxxxxfoo, .{2,5}?
I found the text "xf" starting at index 0 and ending at index 2.
I found the text "oo" starting at index 2 and ending at index 4.
I found the text "xx" starting at index 4 and ending at index 6.
I found the text "xx" starting at index 6 and ending at index 8.
I found the text "xx" starting at index 8 and ending at index 10.
I found the text "fo" starting at index 10 and ending at index 12.

Possessive, xfooxxxxxxfoo, .{2,5}+
I found the text "xfoox" starting at index 0 and ending at index 5.
I found the text "xxxxx" starting at index 5 and ending at index 10.
I found the text "foo" starting at index 10 and ending at index 13.
System.out

En el primer ejemplo del cuantificador greedy se usa .* para encontrar cualquier cosa, cero o más veces, seguido de las letras f o o. Dado que el cuantificador de la expresión la expresión .* es avaricioso primero consume toda la cadena. En este punto, no hay coincidencia dado que las tres últimas letras (f o o) han sido consumidas. De modo que se busca con una letra menos sucesivamente hasta que la la ocurrencia más a la derecha de foo ha sido regurgitada, en este punto hay coincidencia y la búsqueda finaliza.

En el segundo ejemplo, sin embargo, el cuantificador es reacio o vago de modo que empieza consumiendo nada. Dado que foo no aparece en el inicio de la cadena es forzado a tomar la primera letra x con la que se encuentra la primera coincidencia entre 0 y 4. Se siguen encontrando coincidencias hasta que la cadena de entrada ha sido consumida. Encuentra otra coincidencia en 4 y 13.

En el tercer caso se se hayan coincidencias ya que el cuantificador es posesivo. En este caso, la cadena completa es consumida por .*+ dejando nada que satisfaga el patrón foo al final de la expresión. Dado que no vuelve hacia atrás tiene mejor rendimiento que el cuantificador greedy en los casos que se quiera encontrar una coincidencia completa en algo.

Terminal

El código fuente completo del ejemplo puedes descargarlo del repositorio de ejemplos de Blog Bitix alojado en GitHub y probarlo en tu equipo ejecutando siguiente comando:
./gradlew run


Comparte el artículo: