Java Regex-Quantifizierer

Ein Quantifizierer gibt an, wie oft das vorangehende Element wiederholt werden darf. * bedeutet „null oder mehr", + bedeutet „ein oder mehr", ? bedeutet „null oder eins", und {n,m} legt einen genauen Bereich fest. Das ist in jedem Regex-Dialekt gleich. Was in Java häufig zu Verwirrung führt, ist, dass jeder Quantifizierer in drei Modi vorkommt — greedy (gierig), reluctant (zögerlich) und possessive (besitzergreifend) — und der Modus, nicht die Anzahl, bestimmt, wie die Regex-Engine in java.util.regex die Eingabe durchläuft.

Diese Seite behandelt die vier grundlegenden Quantifizierer, die drei Übereinstimmungsmodi, warum Greedy-Muster zu viel verbrauchen und wie possessive Quantifizierer vor katastrophalem Backtracking schützen. Es wird vorausgesetzt, dass Sie bereits wissen, wie man ein Pattern kompiliert und einen Matcher ausführt; falls nicht, beginnen Sie mit Pattern und Matcher. Für die Metazeichen, die Sie wiederholen werden, siehe Zeichenklassen, und um den wiederholten Text zu erfassen, siehe Gruppen.

Die vier grundlegenden Quantifizierer

Hängen Sie einen Quantifizierer an ein einzelnes Zeichen, eine Zeichenklasse oder eine Gruppe, und er steuert die Wiederholung dessen, was sich unmittelbar links davon befindet:

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

Greedy ist der Standard

Ein einfacher Quantifizierer ist greedy: Er verbraucht so viel Eingabe wie möglich und macht dann Backtracking — gibt Zeichen einzeln zurück — bis der Rest des Musters übereinstimmen kann. Deshalb verschluckt ein naives <.+> gegen HTML weit mehr als ein einzelnes 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 '>'

Die Engine griff zunächst nach dem gesamten String, fand kein abschließendes > und ging rückwärts, bis ein > passte — und landete dabei beim allerletzten.

Reluctant: ? hinzufügen, um so wenig wie möglich zu nehmen

Hängen Sie ein ? an einen Quantifizierer (*?, +?, ??, {n,m}?) an, wird er reluctant (auch lazy genannt): Er trifft zunächst auf die wenigsten Wiederholungen zu und erweitert sich nur, wenn es notwendig ist. Das ist in der Regel das, was Sie beim Scannen von abgegrenzten Tokens möchten:

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

Gleiches Muster, ein zusätzliches Zeichen, entgegengesetztes Verhalten: Greedy <.+> gibt den gesamten String zurück, während reluctant <.+?> nur das erste Tag zurückgibt.

Possessive: + hinzufügen und nie zurückgeben

Hängen Sie ein + an (*+, ++, ?+, {n,m}+) wird der Quantifizierer possessive: Er greift wie ein greedy-Quantifizierer so viel wie möglich, verweigert aber das Backtracking. Wenn das restliche Muster dann fehlschlägt, schlägt die gesamte Übereinstimmung fehl — es gibt kein Rückwärtsgehen, um sie zu retten.

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

Warum diese Flexibilität aufgeben? Geschwindigkeit und Sicherheit. Da ein possessiver Quantifizierer nie neu bewertet, kann er nicht in katastrophales Backtracking geraten — den exponentiellen Aufwand, der einen Thread bei Mustern wie (a+)+b mit einer langen Folge von a ohne b einfriert. Possessives a++b antwortet nahezu sofort mit „keine Übereinstimmung".

Ein Arbeitsbeispiel: alle drei Modi nebeneinander

Dieses Programm führt dieselbe Eingabe durch greedy, reluctant und possessive Quantifizierer, übt dann den {n,m}-Bereich und einen Gruppen-Quantifizierer. Alles hier ist reines java.util.regex aus dem JDK.

Was aus dem Lauf zu entnehmen ist:

• Greedy <.+> gab <b>one</b><i>two</i> aus — den gesamten String. Es verbrauchte alles und machte dann Backtracking bis zum letzten >, was genau erklärt, warum greedy Muster über Trennzeichen hinaus zu viel verbrauchen.
• Reluctant <.+?> gab <b> aus derselben Eingabe aus. Das einzelne ? kippte die Strategie von „meiste" zu „wenigste" und hielt beim ersten > an — die Lösung für Tag-für-Tag-Scanning.
• Possessive <.++> gab matches=false aus. Es verschluckte das letzte > und weigerte sich, es zurückzugeben, sodass das abschließende > im Muster nichts zum Abgleichen hatte und der gesamte Versuch fehlschlug — der Preis dafür, nie Backtracking zu betreiben.
• \d{3,5} lehnte 12 ab (no match, zu wenige Ziffern), akzeptierte 123 und 12345 vollständig, und bei 1234567 wurde nur 12345 (Länge 5) gefunden — die Obergrenze 5 begrenzte es, obwohl mehr Ziffern verfügbar waren.
• Das Gruppenmuster (\w+\s*){2,3} stimmte mit alpha beta gamma überein — drei Wörter, das Maximum — und bewies, dass der Quantifizierer auf die gesamte eingeklammerte Gruppe angewendet wurde, und a++b gab bei einer langen Folge von a ohne b sofort false zurück, was zeigt, wie possessive Quantifizierer katastrophales Backtracking umgehen.

Welchen Modus soll ich verwenden?

• Greifen Sie zu reluctant (*?, +?), wenn Sie Inhalte zwischen Trennzeichen abgleichen — Anführungszeichen, Tags, Klammern, begrenzte Blöcke. Es hält beim ersten abschließenden Trennzeichen statt beim letzten an, was fast immer das ist, was Sie meinen.
• Bleiben Sie bei greedy (dem Standard), wenn Sie tatsächlich die längstmögliche Übereinstimmung möchten, oder wenn es sowieso nur eine mögliche Übereinstimmung gibt und das zusätzliche ?/+ nur Rauschen wäre.
• Verwenden Sie possessive (*+, ++) als Leistungs- und Sicherheitswerkzeug bei Eingaben, die Sie nicht kontrollieren. Da es nie Backtracking betreibt, kann es kein katastrophales Backtracking auslösen, aber es schlägt auch bei Übereinstimmungen fehl, die ein greedy Quantifizierer noch gerettet hätte — wenden Sie es also nur dort an, wo Sie wissen, dass Backtracking unnötig ist.

Ein häufiger Praxisfall: Ein Regex, der bei kleinen Eingaben funktioniert, aber bei großen hängt, ist in der Regel ein greedy Quantifizierer innerhalb einer Gruppe, wie (\w+)+. Den inneren Quantifizierer possessive zu machen ((\w++)+ oder das Muster umzustrukturieren) beseitigt den exponentiellen Aufwand.

Übungsaufgaben