Regular Expressions
Man liebt sie oder man hasst sie, aber vermeiden kann man sie in einem Programmiererleben kaum: Regular Expressions. Ich mag sie, ich lasse dafür jedes Sudoku liegen. Hier ein paar Beispiele aus meinem Fundus:
- Suchmaske mit Wildcards
- Quantifiers: Greedy, Lazy, Possessive
- JavaScript Regex Tester
- Buchempfehlung: Jeffrey Friedl, Mastering Regular Expressions
Beispiel: Suchmaske mit Wildcards
Die ursprüngliche Aufgabenstellung lautet: In einem HTML Form wird vom Benutzer ein Suchstring für einen Namen in ein Textfeld eingegeben. Auf dem Server wird dieser Text als Parameter an ein SQL Select Statement ' ... WHERE name LIKE ?' übergeben. Der String soll dazu in '%' eingeschlossen werden. Vom Benutzer mitgegebene Wildcards '*' und '?' sollen durch '%' ersetzt werden. Mehrfache Wildcards hintereinander sind zu entfernen.
Und hier eine funktionierende Lösung:
private static final String A1 = "^\\s*[*?%]+"; private static final String A2 = "^\\s*(?![*?%]|\\s)"; private static final String E1 = "[*?%]+\\s*$"; private static final String E2 = "(?<![*?%]|\\s)\\s*$"; private static final String MID = "[*?%]+"; private static final String REGEX = A1 + '|' + A2 + '|' + E1 + '|' + E2 + '|' + MID; public static String parse ( final String source ) { final String result = source.replaceAll( REGEX, "%" ); return result; }
Zugegeben, der Ausdruck ist nicht auf den ersten Blick zu erfassen. Zunächst einmal besteht er aus fünf mit '|' verbundenen einzelnen Ausdrücken, die zunächst erklärt werden sollen:
Ausdruck A1
Von allen durch Java bedingten Dekorationen befreit, lautet der Ausdruck A1:
^\s*[*?%]+
Der Ausdruck A1 passt für Zeichenfolgen, die:
- am Anfang der Zeichenfolge stehen,
- mit 0 oder mehr Leerzeichen beginnen,
- wenigstens einmal das Zeichen '*', '?' oder '%' enthalten.
Die gesamte zu A1 passende Zeichenfolge wird ersetzt. Beispiele:
- "*abc" wird zu "%abc"
- " ?abc" wird zu "%abc"
- " *?abc" wird zu "%abc"
Ausdruck A2
Der Ausdruck A2 lautet:
^\s*(?![*?%]|\s)
Der Ausdruck A2 passt für Zeichenfolgen, die:
- am Anfang der Zeichenfolge stehen,
- mit 0 oder mehr Leerzeichen beginnen,
- die nicht von '*', '?', '%' oder einem Leerzeichen gefolgt werden.
Der Ausdruck arbeitet mit negative lookahead: (?![*?%]&\s).
Die gesamte zu A2 passende Zeichenfolge bis zum Beginn des lookahead wird ersetzt,
also alle Leerzeichen am Anfang der Zeichenfolge. Beispiele:
- "abc" wird zu "%abc"
- " abc" wird zu "%abc"
Ausdruck E1
Der Ausdruck E1 lautet:
[*?%]+\s*$
Der Ausdruck E1 passt für Zeichenfolgen, die:
- am Ende der Zeichenfolge stehen,
- mit 0 oder mehr Leerzeichen enden,
- vor denen ein- oder mehrmals eines der Zeichen '*', '?', oder '%' steht.
Die gesamte zu E1 passende Zeichenfolge wird ersetzt. Beispiele:
- "abc*" wird zu "abc%"
- "abc? " wird zu "abc%"
- "abc?* " wird zu "abc%"
Ausdruck E2
Der Ausdruck E2 lautet:
(?<![*?%]|\s)\s*$
Der Ausdruck E2 passt für Zeichenfolgen, die:
- am Ende der Zeichenfolge stehen,
- mit 0 oder mehr Leerzeichen enden,
- denen weder '*', '?', '%' noch ein Leerzeichen vorangehen.
Der Ausdruck arbeitet mit neagtive lookbehind: (?<![*?%]|\s).
Die gesamte zu E2 passende Zeichenfolge ab dem Ende des lookbehind wird ersetzt,
also alle Leerzeichen am Ende der Zeichenfolge. Beispiele:
- "abc" wird zu "abc%"
- "abc " wird zu "abc%"
Ausdruck MID
Der Ausdruck MID lautet:
[*?%]+
Der Ausdruck MID passt für Zeichenfolgen, die:
- an beliebiger Stelle in der Zeichenfolge stehen, und
- aus einer beliebigen Folge von '*', '?', '%' bestehen.
Die gesamte zu MID passende Zeichenfolge wird ersetzt. Beispiele:
- "a*b" wird zu "a%b"
- "a?*b" wird zu "a%b"
Ausdruck REGEX
Der gesamte Ausdruck REGEX verbindet die Teilausdrücke mit dem
logischen 'Oder' |. Das Stichwort hierfür ist Alternation.
Die Auswertung von Alternativen erfolgt bei den verschiedenen Regex Engines
unterschiedlich. Java benutzt eine NFA (Nondeterministic Finite Automaton) Engine,
die eine Ordered Alternation ausführt. Die Ausdrücke werden von links nach
rechts evaluiert und die Suche bei der ersten passenden Alternative abgebrochen.
A1|A2|E1|E|MID
Bei der Verarbeitung in String.replaceAll() spielt also die Reihenfolge der Teilausdrücke eine Rolle: Der erste passende Ausruck wird ersetzt. Sind die mit 'Oder' verbundenen Teilausdrücke nicht disjunkt, wird der erste passende Ausdruck ersetzt, was zu unerwarteten Effekten führen kann. Im Beispiel ist der Ausdruck MID nicht disjunkt zu den vorangehenden Ausdrücken A1 und E1 und sollte daher am Ende stehen. Einen passenden disjunkten Ausdruck für MID suche ich noch.
Natürlich gibt es auch andere Lösungen, aber die hier hat mir einfach Spaß gemacht.
Quantifiers: Greedy, Lazy, Possessive
Es gibt drei Kategorien von Quantifiers. Friedl bezeichnet sie als greedy, lazy und possessive, die API Dokumentation zu java.lang.regex.Pattern als greedy, reluctant und possessive. Sie unterscheiden sich durch das Vorgehen der Regex Engine beim Bearbeiten des Suchmusters. Java benutzt eine NFA (Nondeterministic Finite Automaton) Engine.
Greedy Quantifiers ( ?, *, +, X{n,m} ) innerhalb eines Patterns beanspruchen im Suchstring zunächst immer die längstmögliche passende Zeichenfolge. Bei der Untersuchung der folgenden Pattern-Elemente geben sie von hinten her Zeichen auf, um dem Rest des Patterns einen Match zu ermöglichen.
Lazy Quantifiers ( ??, *?, +?, X{n,m}? )werden zunächst übersprungen. Erst wenn das folgende Pattern nicht passt, wird von links nach rechts der lazy Quantifier einbezogen.
Possessive Quantifiers ( ?+, *+, ++, X{n,m}+ )suchen zunächst die kürzeste passende Zeichenfolge. Wenn daran anschließend der Rest des Patterns nicht passt, wird nochmals zum possessive Quantifier zurückgekehrt. Ein possessive Quantifier gibt einmal gefundene Substrings niemals auf.
Als grobe Regel merke ich mir:
- lazy Quantifiers finden den kürzesten passenden Substring,
- greedy Quantifiers finden den längsten, geben aber nötigenfalls Teile wieder her,
- possessive Quantifier finden den längsten und geben den Fund nicht mehr her.
JavaScript Regex Tester
Hier ist ein kleines Formular zum Testen von Regular Expressions mit JavaScript. Das Formular arbeitet nur dann korrekt, wenn im Browser JavaScript erlaubt ist.
Buchempfehlung
Als Referenz für Regular Expressions begleitet mich seit Jahren das Eulen-Buch aus der O'Reilly Serie:
