Regular Expressions / Reguläre Ausdrücke

Autor: Alexander Dilthey | Erstmalig veröffentlicht: 01.02.2005

http://www.aboutwebdesign.de/awd/content/1107290248.shtml

 

Haben Sie schon einmal einen regulären Ausdruck gesehen? Wenn ja, erschien er Ihnen auf den ersten Blick bestimmt sehr unzugänglich. Fast allen Programmierern, die zum ersten Mal mit dieser Technik konfrontiert werden, geht es so. Und es stimmt: manchmal scheint es, als hätten die Erfinder der regulären Ausdrücke gerade die Sonderzeichen zu deren Strukturierung ausgewählt, die das Auge am meisten verwirren.

Trotzdem lohnt es sich, einige Zeit in sie zu investieren. Sie sind eine der vielseitigsten und praktischsten Möglichkeiten, wenn es darum geht, Zeichenketten zu analysieren.

In unserem Tutorial werden wir versuchen, die grundlegenden Ideen der regulären Ausdrücke anhand einiger Beispiele praxisnah zu erklären. Wir verwenden dabei die von Perl unterstützte Syntax. Das sollte aber kein Problem sein, denn inzwischen wurde diese von praktisch allen großen Programmiersprachen und Klassenbibliotheken übernommen. Sie werden unseren Beispiele z.B. auch mit PHP oder Java problemlos verwenden können, von einigen minimalen Änderungen, die eventuell durchzuführen sind, einmal abgesehen.

Nicht ganz so einfach ist es, die Befehle der verschiedenen Sprachen zum Einsatz von regulären Ausdrücken anzuwenden. In unserem Tutorial verwenden wir nur Perl-Code. Dem Einsatz von regulären Ausdrücken mit Java werden wir in Kürze einen separaten Artikel widmen.

 

Das Prinzip hinter regulären Ausdrücken


Was sind diese vielbeschworenen Ausdrücke, reguläre zumal, denn nun eigentlich? Eine ziemlich treffende Antwort lautet: "Ein Werkzeug zur Mustererkennung in Zeichenketten". Mit regulären Ausdrücken können Sie XML-Dateien parsen, eine URL in ihre Einzelbestandteile zerlegen oder den in einer Email-Adresse enthaltenen Benutzernamen herausfiltern.

Ein regulärer Ausdruck an sich ist eine Art Bauplan, der den Aufbau einer Zeichenkette beschreibt. Doch ein Bauplan allein nützt nicht viel - zusätzlich benötigt wird eine Funktion, die überprüft, ob eine gegebene Zeichenkette durch diesen Bauplan beschrieben wird. Diese Funktion wird allgemein als "Automat" bezeichnet und prüft Zeichen für Zeichen der Zeichenkette durch, ob es sich in Übereinstimmung mit dem Bauplan befindet. Wenn das Ergebnis positiv ist, spricht man von einem "Matching".

Wer die folgenden Fragmente ausprobieren möchte, kann in Perl folgendes Code-Muster verwenden:

my $var = "string";
if ($var =~ /AUSDRUCK/)
{
    print "Der String lässt sich durch den Ausdruck beschreiben";
}
else
{
    print "Der String lässt sich NICHT durch den Ausdruck beschreiben";
}


 

Das erste Beispiel


Ein einfaches Beispiel (kein Pseudo-Code - es funktioniert wirklich!) dazu: Sie verwenden den regulären Ausdruck HAUS und die vorgegebene Zeichenkette ist HAUS. Nun wenden Sie den Ausdruck auf die Zeichenkette an. Zweifelsohne wird Ihr Automat feststellen, dass der Ausdruck passt - schließlich enthält er ja genau die gleichen Zeichen in der gleichen Reihenfolge. Fast alle Automaten prüfen übrigens in der Standardeinstellung, ob der Ausdruck irgendeinen Teil der Zeichenkette beschreiben kann - HAUS auf HOCHHAUS angewandt würde also auch zu einem positiven Ergebnis führen.

Wären damit die durch reguläre Ausdrücke eröffneten Möglichkeiten erschöpfend beschrieben, dann wäre dieser Artikel ziemlich witzlos. Ein Zusatznutzen gegenüber herkömmlichen String-Funktionen wäre kaum auszumachen. Das Besondere an regulären Ausdrücken ist, dass sie die Formulierung ziemlich komplexer Baupläne erlauben. Sätze wie "Erst ein A, dann ein oder zwei B, schließlich ein C" lassen sich problemlos auf Übereinstimmung prüfen.

 

Gierige Automaten


Behalten Sie dabei im Hinterkopf, dass die meisten (soll hier heißen: alle in verbreiteten Programmiersprachen integrierten) Automaten wirklich Zeichen für Zeichen auf Konformität prüfen. Wie sie dabei mit einer Bedingung "ein oder zwei B" umgehen, hängt von bestimmten Voreinstellungen ab. Der in Perl integrierte Automat ist per Voreinstellung "greedy", "gierig". Trifft er auf eine solche Bedingung, so probiert er es zuerst mit derjenigen Alternative, die mehr Zeichen umschließt - also "zwei B".

Dies mag Ihnen im Moment noch sehr trivial erscheinen. Eigentlich haben Sie Recht - dahinter steckt wirklich kein komplexes Verhaltensmuster. Interessant wird es erst, wenn man das einfache Prinzip auf ein reales Beispiel anwendet. Ein solches Beispiel eignet sich auch gut, um ein Gefühl für das Verhalten des Automaten beim Prüfen einer Zeichenfolge zu entwickeln.

 

Ein Beispiel für angewandte Gier


Ausgangspunkt ist der eben erwähnte reguläre Ausdruck - kürzer könnte man ihn vielleicht als AB{1,2}C formulieren, das sieht eleganter aus. Wir wenden ihn auf die Zeichenfolge ABBC an. Der Automat geht nun nach folgendem Schema vor:

1: Gesucht ist genau ein A. Trifft das auf das erste Zeichen der Zeichenkette zu? Wenn ja, schreite in der Zeichenkette um ein Zeichen voran und überprüfe Bedingung 2.
2: Gesucht sind ein oder zwei B. Da der "gierige" Modus aktiv ist, prüfe zuerst die zweite Möglichkeit. Dazu ersetze den Ausdruck B{1,2} einfach durch BB und fahre mit 2.1 fort.
2.1: Gesucht ist genau ein B. Trifft das auf das gerade aktive Zeichen in der Zeichenfolge zu? Wenn ja, schreite in der Zeichenfolge um ein Zeichen voran und fahre mit 2.2 fort.
2.2: Gesucht ist genau ein B. Trifft das auf das gerade aktive Zeichen in der Zeichenfolge zu? Wenn ja, schreite in der Zeichenfolge um ein Zeichen voran und fahre mit 3 fort.
3: Gesucht ist genau ein C. Trifft das auf das gerade aktive Zeichen in der Zeichenfolge zu? Wenn ja, ist die Überprüfung des Bauplans positiv beendet - ein positives Ergebnis kann zurückgegeben werden.

Doch was geschieht, wenn die Zeichenkette nur ein B enthält? Der Automat verhält sich zunächst wie im ersten Beispiel, bis er schließlich zu Regel 2.2 kommt. Dort stellt er fest, dass das gerade untersuchte Zeichen in der Zeichenfolge eben kein B ist. Doch das heißt ja noch nicht, dass der reguläre Ausdruck nicht zutrifft - es gibt ja immer noch eine andere Möglichkeit. Also kehrt der Automat zu Regel 2 zurück, ersetzt diesmal aber B{1,2} durch B. Auf diesem Weg findet er, dass es eine Übereinstimmung gibt.

Was würde der Automat tun, wenn die Zeichenkette nicht mit einem A anfinge? Weil unser Automat nicht viele Verhaltensmuster kennt, geht er einfach ein Zeichen in der Zeichenkette weiter und versucht hier erneut, die erste Regel anzuwenden. Und so fährt er fort, bis er endlich ein A gefunden hat - oder am Ende der Zeichenkette angelangt ist. In diesem Fall gibt es natürlich keine Übereinstimmung zwischen Ausdruck und Zeichenkette, was der Automat durch ein negatives (im logischen, nicht im quantitativen Sinne) Ergebnis anzeigt.

 

Der Aufbau eines regulären Ausdrucks


Schritt Eins bestand darin, einen Eindruck von der Arbeitsweise des Automaten zu gewinnen. Nun geht es um die regulären Ausdrücke selbst: welche Elemente kann ein regulärer Ausdruck überhaupt enthalten?

 

Atome


Grundbaustein eines jeden regulären Ausdrucks ist das Atom: eine einfache, nicht weiter teilbare Einheit wie z.B. ein einzelner Buchstabe.

 

Moleküle


Setzt man mehrere Atome zusammen, so erhält man - ganz wie in der Chemie - ein Molekül.

Zusammengesetzt wird in der Regel, indem man Klammern verwendet: (ATOM) ist ein Molekül, weil die einzelnen Buchstaben/Atome durch die Klammern zusammengefasst werden.

 

Quantifier


Schließlich noch die Quantifier: Sie geben an, wie häufig ein Atom oder Molekül vorkommen darf. Sie stehen immer direkt hinter dem Element, auf das sie sich beziehen. Manche Quantifier sind sehr konkret: z.B. "zwischen drei oder vier Mal". Andere sind "nach oben offen": das Plus-Zeichen steht für "mindestens einmal".

Die wichtigsten Quantifier sind folgende:

?: Mindestens null-, höchstens einmal.
+: Mindestens einmal.
*: Mindestens nullmal.
{n,m}: Zwischen n- und m-mal.

Das ist zu abstrakt? Nehmen wir die Beispiel-Zeichenkette AAAAAAAAAA:



Das funktioniert auch mit Molekülen: als Beispiel-Zeichenkette nehmen wir nun ABCABCABC, angewandt werden folgende reguläre Ausdrücke



Durch Hinzufügen eines Fragezeichens schalten die Quantifier in einen "nicht gierigen" Modus um. Als Beispiel dient uns wieder AAAAAAAAAA: A+ erfasst die gesamte Kette, A+? dagegen nur das erste Zeichen.

 

Zeichenklassen


Die enorme Nützlichkeit regulärer Ausdrücke ergibt sich nicht zuletzt daraus, dass intelligent gewählte Zeichenklassen zur Auswahl stehen. Eine Zeichenklasse ist eine Art "unbestimmtes Atom": in der untersuchten Zeichenkette entspricht sie einem einzelnen Zeichen, doch auf der Seite des regulären Ausdrucks sind die Prüfkriterien weitaus toleranter. So steht die Klasse \w beispielsweise für ein beliebiges "Wort-Zeichen", was alle alphanumerischen Zeichen sowie den Unterstrich beinhaltet. Der String IchBaueMirEin_Haus könnte also durch den regulären Ausdruck \w+ vollständig beschrieben werden. Die vordefinierten Klassen bringen ihr jeweiliges Gegenstück mit, das fast immer durch Großschreibung des Buchstabens gebildet wird. \W erfasst also alle Zeichen, die von \w nicht erfasst werden.

Zur Erkennung einer Ziffer verwendet man \d, zur Erfassung eines "Leer-Zeichens" (z.B. das Leerzeichen, der Tabulator..) gibt es \s.

Wer einfach ein beliebiges Zeichen erkennen möchte, verwendet einfach den Punkt: .+ erkennt fast alles. Einzige Ausnahme: das Newline-Zeichen. Nahezu jeder Automat hat jedoch eine Option, die den Punkt auch das Newline-Zeichen erkennen lässt. In Perl ist das der s-Modifier:
if ($string =~ /.+/s) {...

 

Eigene Klassen


Das Definieren eigener Zeichenklassen geschieht über eckige Klammern, die alle enthaltenen Atome zu einer Klasse zusammenfassen.

Der String ABCABCABC lässt sich durch [ABC]+ beispielsweise komplett beschreiben, nicht aber durch [AB]+.

 

Pseudoklassen


Reguläre Ausdrücke unterstützen die Erkennung bestimmter, zwischen Atomen liegender Stellen. So steht ^ für den Anfang einer Zeichenkette und $ für ihr Ende. \b erkennt eine Wortgrenze, eine Stelle, die durch ein \w auf der einen und ein \W auf der anderen Seite definiert ist.

Weil es sich hierbei nicht um Atome handelt, schreitet der Automat bei ihrer Erkennung in der Zeichenfolge nicht voran.

^ABC$ beschreibt z.B. nur den String ABC, nicht aber ABCD, HAUS ABC oder 1ABC1.

 

Gruppierung


Bisher kennen wir Klammern als Mittel, aus Atomen ein Molekül herzustellen. Neben dieser sehr wichtigen Anwendungsmöglichkeit haben sie jedoch noch eine andere Funktion: alle Teile der Zeichenfolge, die durch in Klammern stehende Teile des regulären Ausdrucks spezifiziert werden, stehen nach dem Ende des Vergleichs als Variablen zur Verfügung. In Perl heißen diese Variablen $1, $2, $3, einfach nach der Reihenfolge der öffnenden Klammern im regulären Ausdruck.

Beispiel:

my $str = "Ich gehe";
$str =~ /(\w+) (\w+)/;
print $2, $1;


Dieses Programm gibt gehe Ich aus.

 

Backtracking


Besonders schön ist die Möglichkeit, auf bereits erkannte Gruppen im Verlauf der weiteren Überprüfung zugreifen zu können. Dies geschieht analog zu dem späteren Zugriff über Variablen, nur dass der Nummer diesmal ein Backslash vorangestellt wird.

Beispiel:

my $str = "Gehe Gehe Gehe Gehe Nicht Gehe";
$str =~ /(\w+) ((\1 )+)/;
print $2;

Ausgabe: Gehe Gehe Gehe

Zur Erklärung: Die erste durch Klammern gebildete Gruppe spezifiziert das erste Wort. Die zweite Gruppe enthält alle direkten Wiederholungen dieses Worts, auf das hier mit \1 zurückgegriffen wird. Ausgegeben wird nur die zweite Gruppe, daher auch nur dreimal "Gehe" - sie enthält ja nur die Wiederholungen.

 

Alternierung


Wer gern auf Alternativen setzt, wird an der Alternierung seine Freude haben: hier kombiniert man Klammern und den geraden Strich des logischen ODER, um eine Art Zeichenklasse auf Molekülebene zu erzeugen. Dazu ein Beispiel:

my $str = "Ich gehe heute nach Hause";
print ($str =~ /^Ich gehe (heute|nicht) nach Hause$/), "\n";
$str = "Ich gehe nicht nach Hause";
print ($str =~ /^Ich gehe (heute|nicht) nach Hause$/), "\n";


Das Programm erzeugt die Ausgabe heutenicht - warum? Erstens, weil in beiden Fällen eine Übereinstimmung zwischen Muster und Zeichenkette gefunden wurde. Zweitens, weil Perl die Anwendung eines regulären Ausdrucks in einem Listen-Kontext so durchführt, dass die geklammerten Fundstellen als Elemente der Liste erscheinen.

 

Fortgeschrittene Konzepte


Wenn Sie die regulären Ausdrücke bis zu diesem Punkt verstanden haben, können Sie schon viel damit anfangen. Wir werden im Folgenden noch ein zusätzliches Konzept vorstellen - etwas unbeholfen übersetzt die "Nicht voranschreitende Vorschau". Natürlich haben wir, auch wenn unser Tutorial dann mit einigen Beispielen ausklingt, das Thema der regulären Ausdrücke nicht erschöpfend behandelt. Beeindruckend voluminöse Bücher wurden über dieses Thema geschrieben. Wenn Sie ein tieferes Interesse an dem Thema entwickeln, empfehlen wir Ihnen das Buch "Reguläre Ausdrücke" aus dem O'Reilly-Verlag.

Nun, was ist die "Nicht voranschreitende Vorschau" (engl. "zero-width look-ahead assertion")? Das Konzept ist einfach: ein Element wird durch den Zusatz ergänzt, dass es nur dann als zum Muster passend eingestuft wird, wenn die dem Element nachfolgenden Teile ebenfalls einem bestimmten Muster genügen - letzteres aber ohne Effekt auf den eigentlichen Vergleichsprozess, d.h. der Automat schreitet beim Überprüfen dieser Zusatzbedingung formal nicht voran. Das hört sich komplizierter an, als es eigentlich ist.

my $str = "Nicht nicht zu sagen ist wirklich nicht einfach!";
print ($str =~ /(nicht)(?= zu)( \w+)( \w+)?/i), "\n";


Ausgabe: nicht zu sagen

Dieser reguläre Ausdruck sucht nach einem nicht, dem ein Leerzeichen und dann ein zu folgt. Weiterhin gesucht werden die nächsten beiden auf das nicht folgenden Wörter, wobei ersteres gefunden werden muss, letzteres dagegen nur optional ist.

Die Syntax für eine nicht voranschreitende Vorschau-Abfrage ist also (ELEMENT)(?=FOLGENDESMUSTER).

Und was, wenn Sie eine nicht voranschreitende, negative Vorschau-Abfrage durchführen wollen, also ein Element suchen, dem ein bestimmtes Muster explizit nicht folgt? Verwenden Sie (?!..):

my $str = "Nicht nicht zu sagen ist wirklich nicht einfach!";
print ($str =~ /(nicht)(?! (nicht|zu))( \w+)( \w+)?/i), "\n";


Ausgabe: nicht einfach

Hier wird ein nicht gesucht, das vor keinem nicht oder zu steht. Mit dem i-Schalter am Ende des Ausdrucks wird übrigens die Unterscheidung zwischen Groß- und Kleinbuchstaben deaktiviert.

 

Ersetzungen


Wer will, kann reguläre Ausdrücke auch einsetzen, um bestimmte Abschnitte einer Zeichenkette durch andere zu ersetzen. Folgendes Beispiel zeigt eine sehr einfache Anwendung:

my $str = "ABABABABABA";
$str =~ s/A/B/g;
print $str;


Ausgabe: BBBBBBBBBBB

Wie unschwer ersichtlich ist, wird die eigentliche Ersetzung in der mittleren Zeile erledigt. Perl stellt dafür den s/SUCHMUSTER/ERSETZUNGSMUSTER/-Operator zur Verfügung. Mit dem Modfifier g legen wir fest, dass die Ersetzung global, also alle Fundstellen erfassend, durchgeführt werden soll.

Bei Ersetzungen lassen sich alle Features einsetzen, die auch bei reinen Suchen verfügbar sind. So z.B. Backtracking, wie das nächste Beispiel zeigt:

my $str = "A B C D E F G H";
$str =~ s/(\w)/\1\1/g;
print $str;


Ausgabe: AA BB CC DD EE FF GG HH

 

Einige Beispiele


Um das Tutorial ausklingen zu lassen, geben wir nun noch einige Beispiele. Wer davon gern mehr hätte, kann einfach bei Google nach 'regex examples' suchen - und finden.

 

Fettgedruckte Wörter in HTML


$line =~ /<b>(.*)<<\/b>/i;

 

Der Inhalt des ersten Elements (HTML/XML)


$line =~ /<(\w+)>(.*)<\/\1>/i;

Achtung: dieses Beispiel ist mit Vorsicht zu genießen, da es mit ineinander verschachtelten Tags gleichen Typs zu Problemen kommen kann. Verwenden Sie es also nur für simple, einfach aufgebaute Markup-Dokumente. Der Inhalt des Elements befindet sich anschließend in $2.

 

Angloamerikanische Zeitangaben extrahieren


my $str = "16:01:10";
$str =~ /(\d\d):(\d\d):(\d\d)/);


 

Sehr naiver Test, ob Email-Adresse gültig ist


my $str = "alex\@ccin.de";
unless ($str =~ /^\w+?\@\w+?\.\w{2,4}$/)
{
    die "Keine gültige Mail-Adresse!";
}

 

[ top ]