Erweiterte reguläre Ausdrücke in Perl und anderen Skriptsprachen, PCRE
[Seminarthemen WS07/08] [Übersicht]
Perl Compatible Regular Expressions (PCRE)
PCRE ist eine Bibliothek zur Auswertung von Regulären Ausdrücken. Die Entwickler von Perl gelten, was reguläre Ausdrücke angeht, als Vorreiter. Neue reguläre Ausdrücke werden häufig zuerst bei Perl entwickelt und dann von anderen Skriptsprachen oder in der PCRE übernommen. Die von Perl entliehenen Ausdrücke entsprechen in etwa dem Stand von Perl 5.0. In PCRE befinden sich auch ein paar zusätzliche reguläre Ausdrücke, die erst später in Perl aufgenommen wurden. Dennoch gibt es einige Unterschiede, da Perl zwischenzeitlich stark erweitert wurde.
Ursprünglich wurde PCRE für den Mailserver Exim entwickelt. PCRE ist auch in vielen Skriptsprachen und Programmiersprachen wie z.B. Ruby, Python, PHP und weiteren verfügbar.
[top]
Modus-Modifikatoren
Innerhalb von regulären Ausruck hat man die Möglichkeit einige Regex-Modi zu aktivieren/steuern. Mit "(?i)" schaltet man den Modi für das Ignorieren von Groß- und Kleinschreibung ein. Dieser Modus gilt so lange bis er mit (?-i) beendet wird.
Durch den folgenden Ausdruck
Platt(?i)fisch(?-i)Gräte
werden Strings wie "PlattfischGräte", "PlattFISCHGräte", "PlattFiScHGräte",... erkannt. "fisch" kann beliebig groß und klein geschrieben werden. Der Modus "Ignorieren von Groß- und Kleinschreibung" gilt nicht für "Platt" und "Gräte". Diese müssen in exakt dieser Schreibweise vorkommen.
Befindet sich (?i) innerhalb eines Klammerausdrucks, wird der Modus in den meisten Implementationen spätestens durch die schließende Klammer des Unterausdrucks beendet.
Unterstützt wird dieses Konstrukt von Perl und den meisten Sprachen, die PCRE nutzen. In Python gilt der eingeschaltete Modus für den ganzen Regex, lässt sich im Regex nicht wieder ausschalten. Auch andere Skriptsprachen verhalten sich bei diesem Konstrukt teilweise unterschiedlich.
Im folgenden ein paar Beispiele:
(?i) #Aktiviert "Groß-Kleinschreibung ignorieren"
(?-i) #Deaktiviert "Groß-Kleinschreibung ignorieren"
(?ix-m) #Aktiviert "Groß-Kleinschreibung ignorieren" und "Freie Form"
#und Deaktiviert Mehrzeilenmodus
Die folgenden Modi stehen in den meisten Systemen zur Verfügung:
| i | Groß- und Kleinschreibung ignorieren |
| x | "Freie Form" |
| s | "Punkt passt auf Alles" |
| m | Mehrzeilenmodus |
[top]
Nicht-einfangende Klammern
Die nicht-einfangenden Klammern "(?:...)" dienen zur Gruppierung. Dabei wird zwar gruppiert, aber der vom Unterausdruck erkannte Text, nicht abgespeichert. Sie sind somit in keiner Variablen $1, $2,... enthalten. Genutzt werden können diese nicht-einfangenden Klammern zur Gruppenbildung für Alternationen und Quantoren. Ihr Einsatz kann auch bei großen regulären Ausdrücken die Lesbarkeit erhöhen. Die Regex sind zu dem effizienter, bei Verwendung von nicht-einfangenden Klammern statt normalen Klammern. Da keine Abspeicherung erfolgt, wird Speicher und Rechenzeit eingespart.
Hilfreich können Nicht-einfangende Klammern neben Effezienzverbesserung auch bei größeren zusammengesetzten regulären Ausdrücken sein.
In einem einfachen Beispiel erklärt:
$var = qr/(\D+)/i;
m/(\d+)$var(\d+)/
Erzielt der reguläre Ausdruck einen Treffer, steht in $1 und $2 je eine Zahl. Enthält die Variable $var auch eine einfangende Klammer, wie in diesem Beispiel, ist in $2 die Zahl enthalten, die vom Unterausdruck der Variable eingefangen wurde.
In der Variable $3 ist dann die eigentlich gesuchte Zahl enthalten. Mit Hilfe von nicht-einfangenden Klammern, lässt sich das gewünschte Ergebnis erreichen.
$var = qr/(?:\D+)/i;
m/(\d+)$var(\d+)/
[top]
Benannte Unterausdrücke
In Python und den .NET-Sprachen gibt es die Möglichkeit Unterausdrücken in einfangenden Klammern Namen zu geben. Dies kann unter anderem dies Lesbarkeit von regulären Ausdrücken erhöhen. In Perl gibt es diese Möglichkeit nicht.
Verwendung von benannten Unterausdrücken in Python
(?P<NAME>...) #Syntax im regulären Ausdruck
(?=NAME) #Nutzung als Rückwärtsreferenz in Regulärem Ausdruck
RegexObj.group("NAME") #Zugriff im Programm
Verwendung von benannten Unterausdrücken in .NET-Sprachen
(?<NAME>...) #Syntax im regulären Ausdruck
\k<NAME> #Nutzung als Rückwärtsreferenz in Regulärem Ausdruck
RegexObj.Groups["NAME"] #Zugriff im Programm
[top]
Not greedy/Nicht gierige Quantoren
Normale Quantoren sind von "Natur" aus gierig. Zu Erinnerung, normale Quantoren sind "?" "*" "+" "{min,max}". Wenn sich ein Quantor auf einen Unterausdruck wie z.B. "[A-Z]" in "[A-Z]*" bezieht, gibt es eine minimale und eine maximal Anzahl von Treffern. Bei "*" ist minimal "0" und maxmimal "beliebig häufig". Gierig heißt, dass normale Quantoren versuchen immer die größtmögliche Zeichenkette zu auszuwählen.
Beispiel:
Der folgende reguläre Ausdruck
a.*b
erkennt im String "ababab" den kompletten String "ababab".
Durch ein zusätzliches Fragezeichen hinter dem Sternchen
a.*?b
erreicht man, dass der kleinste mögliche String "ab" erkannt wird.
Durch das zusätzliche "?" hinter dem Quantor, lassen sich natürlich auch die anderen Quantoren zu not-greedy ändern, "*?" "+?" "??" "{min,max}?".
[top]
Rekursive Muster
Es besteht die Möglichkeit Rekursive Muster zu schreiben, jedoch ist an dieser Stelle die Syntax in Perl und PCRE etwas unterschiedlich. Rekursion wird in Perl über die Möglichkeit gebildet, Perlcode während der Laufzeit auszuwerten. In PCRE gibt es die Möglichkeit ein zusätzliches Metazeichen zu nutzen.
Rekursion in Perl:
Der im Muster enthaltene Perlcode, kann den regulären Ausdruck auch selbst enthalten. Die Variable "$re" enthält den regulären Ausdruck selbst.
Dies wird im folgenden Beispiel für das rekursive Muster genutzt:
$re = qr{ ( a | (?p{$re}) )* }x;
Rekursion in PCRE:
In PCRE ist die Syntax "(?R)", wenn der ganze reguläre Ausdruck eingesetzt werden soll, oder "(?" + Nummer eines Klammernausdrucks + ")".
Das obige Beispiel würde in PCRE so aussehen:
(a | (?R) )*
Eine Alternative in PCRE ist benannte Unterausdrücke zu verwenden.
[top]
Kommentare
Mit dem Konstrukt
(?#...)
kann man in Regex Kommentare hinzufügen
Eine Alternative an dieser Stelle wäre der Modus "Freie Form", bei dem auch Kommentare zulässig sind.
[top]
Bevor wir zu "Atomaren Klammern" kommen, erkläre ich an dieser Stelle, wie reguläre Ausdrücke intern verarbeitet werden und was "Backtracking" bedeutet.
"Vorgehensweise von NFA Maschinen" und "Backtracking" (hier klicken)
Atomare Klammern
Passt der Unterausdruck von atomaren Klammern, lässt dieses Konstrukt den gefundenen Text nicht mehr los. Bei normalen Klammern können Quantoren Zeichen wieder abgeben, damit der ganze reguläre Ausdruck passt. Der von atomaren Klammern eingefangene Text ist aber wie ein Atom unteilbar. Es ist kein Backtracking mehr möglich. Die gespeicherten Zustände werden nach dem schließenden Unterausdruck, gelöscht.
Die Syntax für Atomare Klammern:
(?>...)
Beispiel:
Im folgenden Beispiel wird nach beliebigen Zeichen, gefolgt von einem Ausrufezeichen, gesucht.
(.*)! #regulärer Ausdruck mit normalen Klammern
(?>.*)! #regulärer Ausdruck mit atomaren Klammern
Im ersten regulären Ausdruck "(.*)!" werden normale Klammern verwendet. Im zweiten regulären Ausdruck "(?>.*)!" werden atomare Klammern verwendet. Wendet man nun den ersten regulären Ausdruck auf den String "Hey!" an, passt dieser. Wendet man jedoch den zweiten regulären Ausdruck auf den String an, findet dieser nichts. Beide Unterausdrücke(Klammern) finden "Hallo!". Der erste jedoch gibt das "!" wieder zurück, damit der ganze reguläre Ausdruck passt, der zweite reguläre Ausdruck behält "!" und somit passt der ganze reguläre Ausdruck nicht. Im zweiten regulären Ausdruck werden intern die Zustände, die fürs Backtracking verwendet werden, nachdem die Maschine am Ende der atomaren Klammerung angekommen ist, gelöscht. Dadurch kann die Maschine nicht wieder zu Punkten in der atomaren Klammer zurückkehren. Der von der atomaren Klammer gefundene Text ist nun eine unveränderliche Einheit im gesamten regulären Ausdruck.
Es werden nur die Zustände gelöscht, die durch die atomare Gruppe hinzukamen. Mögliche Zustände vor der atomaren Klammer bleiben bestehn.
Schnellere Fehlschläge mit atomaren Gruppen
Wenn der reguläre Ausdruck
^\w+:
z.B. auf "Emailadresse" angewendet wird, ist erkennbar, dass dieser reguläre Ausdruck nicht passen wird, denn am Ende von "Emailadresse" steht kein Doppelpunkt.
Bis die Maschine das jedoch feststellt ist schon viel Rechenzeit verbraucht worden.
Zunächst wird das "\w+" den ganzen String durchqueren. Dabei wird bei jedem Buchstaben ein Zustand gespeichert, bis auf bei dem ersten Zeichen, da es durch den Quantor "+" obligatorisch ist. Am Ende angekommen setzt die Maschine mit dem nächsten Element des regulären Ausdrucks fort, in diesem Beispiel dem Doppelpunkt. Nun nimmt sich die Maschine den letzten Buchstaben "e" und stellt fest, dass der Doppelpunkt nicht passt. Springt also einen weiteren Zustand zurück. Dies geschieht so lange, bis er bei der letzten Rücksprungmöglichkeit, dem "m", angekommen ist und erst hier feststellt, dass der reguläre Ausdruck nicht passt.
Um den Regex effizienter zu machen, kann man mit Hilfe von atomaren Gruppen dafür sorgen, dass die Maschine kein Backtracking macht und so der reguläre Ausdruck schon viel früher fehlschlägt.
In diesem Beispiel:
^(?>\w+):
Wünschenswert wäre eine automatische Optimierung durch die Maschine, die erkennt, dass hinter dem Quantor noch etwas folgt, was vielleicht nie erkannt wird. Bisher wird dies aber von keiner Implementation unterstützt.
[top]
Possessive Quantoren
Possessive Quantoren gibt es bisher nur in "java.util.regex". Possessive Quantoren haben hinter dem normalen Ausdruck noch ein "+", also "*+", "++", "?+", "{min,max}+".
Wie auch die normalen Quantoren versuchen possessive Quantoren möglichst viele Zeichen zu erkennen, aber anders als die normalen Quantoren, geben possessive Quantoren keine Zeichen wieder her. Wie festzustellen ist, lässt sich dieses Verhalten auch durch atomare Klammern erzeugen. So ist das Resultat von ".++" dasselbe wie in "(?>.+)". Durch possessive Quantoren können reguläre Ausdrücke effizienter werden. Denn im Gegensatz zu atomaren Gruppen, werden Zustände nicht gespeichert. Bei atomaren Gruppen, würden diese hingegen am Ende gelöscht.
[top]
Lookahead und Lookbehind / Lookaround
Das Lookahead- und das Lookbehind-Konstrukt werden zusammen auch als Lookarround-Konstrukt bezeichnet. Mit diesen Konstrukten lässt sich String auf ein Unterausdruck prüfen. Die Besonderheit von Lookarounds ist, dass kein Text verbraucht wird. Es wird nur eine Position gefunden. Der Text kann somit noch andersweitig im regulären Ausdruck verwendet werden. Verwendung können Lookarounds z.B. auch im if-Teil von bedingten regulären Ausdrucken finden.
Mit Lookahead wird der Suchstring in Leserichtung(rechts) nach einem Unterausdruck abgesucht. Bei Lookbehind läuft das genau anders herum, da wird in die entgegen gesetzte Richtung(links) gesucht. Es gibt auch negierte Lookarounds bei denen der Unterausdruck nicht vorkommen darf.
Es gibt die folgenden 4 Typen von Lookaround:
| Typ | Konstrukt | Erfolgreich, wenn der geklammerte Unterausdruck... |
|---|
| Positives Lookbehind | (?<=...) | auf der linken Seite gefunden wird. |
| Negatives Lookbehind | (?<!...) | auf der linken Seite nicht gefunden wird. |
| Positives Lookahead | (?=...) | auf der rechten Seite gefunden wird. |
| Negatives Lookahead | (?!...) | auf der rechten Seite nicht gefunden wird. |
Beispiel:
Der reguläre Ausdruck
(?=PeterPan)Peter
erkennt nur dann "Peter", wenn "Peter" Teil von "PeterPan" ist. Das Lookahead passt auf die Position von "PeterPan" und der eigentliche Ausdruck passt auf den Teil "Peter" von "PeterPan". "Peter" alleine im String würde vom regulären Ausdruck nicht erkannt werden.
Weiteres Beispiel:
Wenn wir ein Leerzeichen zwischen "PeterPan" mit Hilfe von regulären Ausdrücken setzen wollen, können wir dies mit einem Lookahead und Lookbehind machen. Es wird kein Text eingefangen sondern nur die Position, die wir dann durch ein Leerzeichen ersetzen.
s/(?<=\bPeter)(?=Pan\b)/ /g
Der Lookbehind-Unterausdruck passt auf "Peter", die gefunde Position ist die hinter "Peter". An dieser Stelle findet der Lookahead-Unterausdruck dann "Pan". Die gefundene Position wird dann durch ein Leerzeichen ersetzt.
[top]
Bedingte reguläre Audrücke
Die Syntax für das if-then-else Kontrukt:
(? if then| else)
Mit diesem Konstrukt können innerhalb einer Regex if-then-else Bedingungen formuliert werden. Der if-Teil ist eine Bedingung, der then- und else-Teil sind normale Unterausdrücke. Dieses Konstrukt funktioniert wie eine normale if-then-else Bedingung. Ist der if-Teil wahr, wird der then-Teil verwendet, ansonsten der else-Teil. Der else-Teil kann auch weggelassen werden. Das dazugehörige Zeichen "|" muss dann auch weggelassen werden.
Worauf im if-Teil gerpüft werden kann, hängt vom Regex-Dialekt ab. In den meisten Implementationen kann man auf vorher eingefangenen Text prüfen oder aber auf einen Lokkaround-Kontrukt. Mit einer Zahl im if-Teil kann auf das Vorhandensein eines Treffers in einem Klammerausdruck vor der if-Bedingung geprüft werden.
Beispiel:
Ein gutes Beispiel ist ein <IMG>-Tag, dass auch eingeschlossen von einem <A>-Tag sein kann.
( <A\s+[^>]+ \s* )?
<IMG\s+[^>]+>
(?(1)\s*</A>) #wenn <A>-Tag vorhanden dann auch schließen
Im Beispiel wird der durch den ersten Klammerausdruck eingefangene Text auf Vorhandensein geprüft. Das ist in diesem Fall das öffnende <A>-Tag. Wenn das der Fall ist, muss das schließende <A>-Tag auch vorhanden sein. Einen else-Teil gibt es in diesem Beispiel nicht.
[top]
Alternative zu PCRE in Ruby / Oniguruma
Für Ruby ab Version 1.9 ist neben PCRE die RegExp Engine "Oniguruma" verfügbar.
Diese Engine befindet sich noch in der Entwicklung. Sie soll die meisten regulären Ausdrücke unterstüzten,
die auch in PCRE verfügbar sind, aber performanter sein.
[top]