Quantificatori Regex Java: Greedy, Reluctant, Possessive

Un quantificatore specifica quante volte l'elemento che lo precede può ripetersi. * significa "zero o più volte", + significa "una o più volte", ? significa "zero o una volta", e {n,m} indica un intervallo preciso. Questi concetti sono comuni a tutti i dialetti regex. Ciò che crea confusione in Java è che ogni quantificatore esiste in tre modalità — greedy, reluctant e possessive — ed è la modalità, non il conteggio, a determinare come il motore regex di java.util.regex scorre l'input.

Questa pagina tratta i quattro quantificatori di base, le tre modalità di corrispondenza, il motivo per cui i pattern greedy eccedono nella corrispondenza e come i quantificatori possessive proteggono dal backtracking catastrofico. Si presuppone che tu sappia già come compilare un Pattern ed eseguire un Matcher; in caso contrario, inizia con Pattern e Matcher. Per i metacaratteri da ripetere, consulta le classi di caratteri, e per catturare il testo ripetuto, consulta i gruppi.

I quattro quantificatori di base

Applica un quantificatore a un singolo carattere, a una classe di caratteri o a un gruppo, e controlla la ripetizione dell'elemento immediatamente alla sua sinistra:

Quantificatore	Ripete l'elemento precedente	Esempio	Corrisponde a
`*`	zero o più volte	`ab*c`	`ac`, `abc`, `abbbc`
`+`	una o più volte	`ab+c`	`abc`, `abbc` (non `ac`)
`?`	zero o una volta	`colou?r`	`color`, `colour`
`{n}`	esattamente `n` volte	`\d{4}`	un anno a 4 cifre
`{n,}`	`n` o più volte	`\d{2,}`	due o più cifre
`{n,m}`	tra `n` e `m` volte	`\d{3,5}`	da 3 a 5 cifre

Pattern.matches("ab*c", "abbbc");   // true  — three b's
Pattern.matches("ab+c", "ac");      // false — '+' needs at least one b
Pattern.matches("colou?r", "color");// true  — the 'u' is optional
Pattern.matches("\\d{3,5}", "1234");// true  — four digits is within 3..5

Il greedy è il comportamento predefinito

Un quantificatore senza suffisso è greedy: consuma quanta più input possibile, poi retrocede — restituendo un carattere alla volta — finché il resto del pattern riesce a corrispondere. Ecco perché un ingenuo <.+> su HTML assorbe molto più di un singolo tag:

String html = "<b>one</b>";
Matcher m = Pattern.compile("<.+>").matcher(html);
m.find();
m.group(); // "<b>one</b>"  — '.+' ate everything, then backed up to the last '>'

Il motore ha prima acquisito l'intera stringa, non ha trovato il > finale, e ha retrocesso finché un > non si è allineato — fermandosi sull'ultimo.

Reluctant: aggiungi `?` per prendere il meno possibile

Aggiungendo un ? a qualsiasi quantificatore (*?, +?, ??, {n,m}?), esso diventa reluctant (detto anche lazy): corrisponde al minor numero di ripetizioni prima di espandersi solo se necessario. Questo è ciò che di solito si vuole quando si analizzano token delimitati:

String html = "<b>one</b>";
Matcher m = Pattern.compile("<.+?>").matcher(html);
m.find();
m.group(); // "<b>"  — stopped at the first '>'

Stesso pattern, un carattere in più, comportamento opposto: il greedy <.+> restituisce l'intera stringa, mentre il reluctant <.+?> restituisce solo il primo tag.

Possessive: aggiungi `+` e non cedere mai

Aggiungendo un + (*+, ++, ?+, {n,m}+), il quantificatore diventa possessive: acquisisce il più possibile come un greedy, ma si rifiuta di retrocedere. Se il resto del pattern fallisce, l'intera corrispondenza fallisce — non c'è modo di tornare indietro per recuperarla.

// Possessive '.++' eats the final '>' too and won't return it, so no '>' is left
Pattern.compile("<.++>").matcher("<b>one</b>").find(); // false

Perché rinunciare a tale flessibilità? Velocità e sicurezza. Poiché un quantificatore possessive non riconsidere mai, non può cadere nel backtracking catastrofico — l'esplosione esponenziale che blocca un thread su pattern come (a+)+b alimentato da una lunga sequenza di a senza b. Il possessive a++b risponde "nessuna corrispondenza" quasi istantaneamente.

Modalità	Sintassi	Strategia	Retrocede?
Greedy	`X*`	prende il massimo, poi cede se necessario	sì
Reluctant	`X*?`	prende il minimo, poi aggiunge se necessario	sì
Possessive	`X*+`	prende il massimo e lo mantiene	no

Un esempio pratico: tutte e tre le modalità a confronto

Questo programma esegue lo stesso input attraverso quantificatori greedy, reluctant e possessive, poi esercita l'intervallo {n,m} e un quantificatore di gruppo. Tutto qui è puro java.util.regex del JDK.

java— editable, runs on the server

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

public class QuantifiersDemo {
 public static void main(String[] args) {
 String html = "onetwo";

// 1. Greedy: <.+> grabs as much as it can, then backtracks to find a '>'
 Matcher greedy = Pattern.compile("<.+>").matcher(html);
 greedy.find();
 System.out.println("greedy <.+> : " + greedy.group());

// 2. Reluctant: <.+?> takes as little as possible, then expands only if forced
 Matcher lazy = Pattern.compile("<.+?>").matcher(html);
 lazy.find();
 System.out.println("reluctant <.+?> : " + lazy.group());

// 3. Possessive: <.++> never gives characters back, so it cannot find a '>'
 Matcher poss = Pattern.compile("<.++>").matcher(html);
 System.out.println("possessive <.++> : matches=" + poss.find());

// 4. The {n,m} family controls exact repetition counts
    Pattern code = Pattern.compile("\\d{3,5}");
    for (String s : new String[]{"12", "123", "12345", "1234567"}) {
      Matcher m = code.matcher(s);
      if (m.find()) {
        System.out.println("\\d{3,5} on " + s + " -> matched '" + m.group()
            + "' (len " + m.group().length() + ")");
      } else {
        System.out.println("\\d{3,5} on " + s + " -> no match");
      }
    }

// 5. A quantifier after a group repeats the whole group
    Matcher words = Pattern.compile("(\\w+\\s*){2,3}").matcher("alpha beta gamma delta");
    words.find();
    System.out.println("(\\w+\\s*){2,3} : '" + words.group().trim() + "'");

// 6. Possessive quantifiers reject without backtracking, dodging blow-ups
    String tricky = "aaaaaaaaaaaaaaaaaaaa!";
    boolean ok = Pattern.compile("a++b").matcher(tricky).find();
    System.out.println("a++b on a...! : " + ok + " (failed fast, no backtracking)");
  }
}

Cosa ricavare dall'esecuzione:

Il greedy <.+> ha stampato onetwo — l'intera stringa. Ha consumato tutto, poi ha retrocesso fino all'ultimo >, motivo per cui i pattern greedy eccedono nella corrispondenza tra delimitatori.
Il reluctant <.+?> ha stampato  dallo stesso identico input. Il singolo ? ha invertito la strategia da "massimo" a "minimo", fermandosi al primo > — la soluzione per analizzare un tag alla volta.
Il possessive <.++> ha stampato matches=false. Ha inghiottito il > finale e si è rifiutato di restituirlo, così il > finale nel pattern non aveva nulla da corrispondere e l'intero tentativo è fallito — il prezzo del non retrocedere mai.
\d{3,5} ha rifiutato 12 (no match, cifre insufficienti), ha accettato 123 e 12345 integralmente, e su 1234567 ha corrisposto solo a 12345 (len 5) — il limite superiore 5 lo ha bloccato anche se erano disponibili altre cifre.
Il pattern di gruppo (\w+\s*){2,3} ha corrisposto a alpha beta gamma — tre parole, il massimo — dimostrando che il quantificatore si applicava all'intero gruppo tra parentesi, e a++b ha restituito false quasi istantaneamente su una lunga sequenza di a senza b, mostrando come i quantificatori possessive evitino il backtracking catastrofico.

Quale modalità dovrei usare?

Scegli il reluctant (*?, +?) quando fai la corrispondenza di contenuti tra delimitatori — virgolette, tag, parentesi, blocchi delimitati. Si ferma al primo delimitatore di chiusura invece dell'ultimo, il che è quasi sempre quello che si intende.
Mantieni il greedy (predefinito) quando vuoi genuinamente la corrispondenza più lunga possibile, o quando esiste una sola corrispondenza possibile e il ?/+ extra sarebbe solo rumore.
Usa il possessive (*+, ++) come strumento di prestazione e sicurezza su input non controllato. Poiché non retrocede mai, non può innescare il backtracking catastrofico, ma farà anche fallire corrispondenze che un quantificatore greedy avrebbe recuperato — quindi applicalo solo dove sai che il backtracking è inutile.

Un comune rimedio nel mondo reale: un'espressione regolare che funziona su input piccoli ma si blocca su input grandi è di solito un quantificatore greedy all'interno di un gruppo, come (\w+)+. Rendere il quantificatore interno possessive ((\w++)+ o ristrutturare il pattern) elimina l'esplosione esponenziale.

Esercitati

Pratica

Sull'input 'one', cosa corrisponde il pattern Java '<.+?>' (un quantificatore reluctant) alla prima chiamata a find()?

'' — il reluctant '+?' prende il minor numero di caratteri possibile e si ferma al primo '>''one' — l'intera stringa, perché '.' corrisponde a qualsiasi carattereNiente, perché il quantificatore possessive si rifiuta di retrocedere'' — il motore scorre da destra e restituisce l'ultimo tag