Die Ursprünge regulärer Ausdrücke

(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)

Die Keime zu regulären Ausdrücken wurden in den frühen 1940er Jahren von zwei Neurophysiologen angelegt. Warren McCulloch und Walter Pitts hatten Modelle dafür entwickelt, wie nach ihrer Meinung das Nervensystem auf der Ebene der Neuronen arbeitet. (Anmerkung: »A logical calculus of the ideas immanent in nervous activity«, zuerst erschienen in Bulletin of Math. Biophysics 5, 1943, Neuabdruck in Embodiments of Mind, MIT Press, 1965. Der Artikel beginnt mit einer interessanten Zusammenfassung darüber, wie Nervenzellen, also Neuronen, funktionieren - wussten Sie, dass die Geschwindigkeit von Nervenimpulsen zwischen einem und 150 m/s variiert? Dann aber besteht der Artikel fast nur aus Formeln, die für mich, im wahrsten Sinne des Wortes, griechisch aussehen.) Reguläre Ausdrücke wurden ein paar Jahre später Realität, als der Mathematiker Stephen Kleene für diese Modelle eine Algebra formulierte und diese reguläre Mengen nannte. Er entwarf auch eine einfache Notation dafür und nannte diese Regular Expressions, eben reguläre Ausdrücke.

In den 1950er und 1960er Jahren wurden reguläre Ausdrücke zu einem beliebten Forschungsgebiet in der theoretischen Mathematik. Robert Constable hat dazu einen guten Übersichtsartikel (Robert L. Constable, »The Role of Finite Automata in the Development of Modern Computing Theory«, in: The Kleene Symposium, hrsg. von Barwise, Keisler und Kunen, North-Holland Publishing Company, 1980, S. 61-83.) für den mathematisch Interessierten veröffentlicht.

Es gibt Hinweise auf frühere Arbeiten, aber die erste Veröffentlichung über den Gebrauch von regulären Ausdrücken im Zusammenhang mit Computern, die ich gefunden habe, ist der Artikel von Ken Thompson aus dem Jahr 1968, Regular Expression Search Algorithm (Communications of the ACM, Vol. 11, No. 6, Juni 1968), in dem er einen Compiler für reguläre Ausdrücke beschreibt, der Code für die IBM 7094 erzeugte. Diese Arbeit führte zu qed, einem Editor, der die Basis für den Unix-Editor ed bildete.

Erstaunlicherweise waren die regulären Ausdrücke von ed nicht so mächtig wie die früheren von qed, aber sie waren die ersten, die von einer größeren Benutzergemeinde eingesetzt wurden und nicht nur Forschungsthema waren. ed hatte (und hat) einen Befehl, der Zeilen ausgibt, die auf einen regulären Ausdruck passen. Dieser Befehl, »g/Regular Expression/p«, bedeutete »Global Regular Expression Print«. Dieser ed-Befehl war so beliebt, dass ein eigenes Programm dafür geschrieben wurde, und damit war grep geboren (aus dem später egrep – extended grep – entstand).

Metazeichen bei grep

Die regulären Ausdrücke dieser frühen Programme waren sehr beschränkt, auch im Vergleich zu egrep. Das Metazeichen * wurde unterstützt, aber weder + noch ? (das Fehlen des Fragezeichens ist ein besonders schwerwiegender Nachteil). Die Metazeichen zur Gruppierung waren \(...\); normale Klammern waren Literale. (Anmerkung: Ein historisches Detail: ed (und damit grep) benutzt \(...\) statt Klammern ohne Backslash, weil Ken Thompson dachte, dass reguläre Ausdrücke vor allem im Zusammenhang mit C-Programmen benutzt würden und dass dabei literale Klammern viel häufiger vorkommen würden als Rückwärtsreferenzen.) grep unterstützte Zeilenanker, aber nur in eingeschränkter Form. Wenn ^ am Anfang einer Regex vorkam, war es ein Metazeichen für den Zeilenanfang, wie in egrep oder Perl. Sonst aber war es ein normales Zeichen, ein literaler Zirkumflex. Analog war $ nur als letztes Zeichen eines regulären Ausdrucks das Zeilenende-Metazeichen. Damit konnte man Dinge wie ˹end$|^start˼ nicht schreiben, was aber nicht weiter tragisch war, denn auch die Alternation wurde nicht unterstützt!

Die Art, wie Metazeichen untereinander zusammenspielen, ist auch wichtig. Die vielleicht ernsthafteste Einschränkung von grep war die, dass sich der Stern nicht auf eine geklammerte Gruppe beziehen konnte, sondern nur auf Literale, Zeichenklassen oder den Punkt. Damit waren die Klammern bei grep nur dazu nützlich, sich Text zu merken, der weiter vorne im regulären Ausdruck gepasst hatte, aber nicht für das Bilden von Gruppen im Allgemeinen.

grep entwickelt sich

Obwohl es grep auf vielen modernen Systemen gibt, habe ich eben die Vergangenheitsform benutzt. Das bezog sich nämlich auf die ursprünglichen Versionen von grep, also auf 30 Jahre alte und ältere. Mit dem Fortschreiten der Entwicklung werden solche Programme oftmals überholt und erweitert, und grep ist da keine Ausnahme.

Dabei erhielt grep bei AT&T Bell Labs ein paar neue Merkmale, etwa die \{min, max\}-Notation vom lex-Programm. Außerdem wurde die -y-Option korrigiert, die bei frühen Versionen Groß- und Kleinschreibung ignorieren sollte, die aber nie zuverlässig funktioniert hatte. Etwa zur selben Zeit fügten Leute an der Universität Berkeley Metazeichen für Wortgrenzen hinzu und benannten die -y-Option in -i um. Den Stern oder andere Quantoren konnte man leider noch immer nicht auf geklammerte Unterausdrücke anwenden.

egrep entwickelt sich

Zu dieser Zeit schrieb Alfred Aho (auch bei AT&T Bell Labs) egrep, das ein wesentlich reicheres Spektrum von Metazeichen kannte; die meisten davon haben Sie unter Einführung in reguläre Ausdrücke kennengelernt. Wichtiger ist aber, dass er diese in einer völlig anderen (und im Allgemeinen besseren) Art implementierte. (Auf diese verschiedenen Methoden zur Implementation von regulären Ausdrücken konzentrieren sich die Kapitel Wie Regex-Maschinen arbeiten und Regex-Methoden aus der Praxis.) Die Zeichen ˹+˼ und ˹?˼ wurden hinzugefügt und konnten sich nun auch auf Unterausdrücke beziehen; damit erhielten die regulären Ausdrücke von egrep eine wesentlich größere Ausdruckskraft.

Auch die Alternation kam dazu, und die Zeilenanker wurden zu vollwertigen Metazeichen, so dass sie überall im regulären Ausdruck benutzt werden konnten. egrep hatte aber auch schwere Probleme – manchmal wurde ein Treffer gefunden, aber nicht ausgegeben – und manche der heute viel verwendeten Optionen waren noch nicht dabei. Trotzdem war es ein wesentlich brauchbareres Werkzeug.

Neue Spezies entstehen

Um dieselbe Zeit entwickelten sich auch Programme wie awk, lex und sed weiter, sie wuchsen jedoch oft in eine eigene Richtung. Oft haben Entwickler versucht, Features des einen Programms in ein anderes einzubauen. Manchmal endete dies mit einem Misserfolg. Wenn zum Beispiel das Plus-Metazeichen zu den vorhandenen Metazeichen von grep hinzugefügt werden soll, kann nicht einfach + benutzt werden; es gibt viel zu viele Skripten, bei denen grep mit einem ›+‹ als literalem Zeichen benutzt wird. Dagegen ist ›\+‹ nicht etwas, was ein grep-Benutzer häufig braucht, und kann deshalb als neues »Eins oder mehr«-Zeichen eingeführt werden, ohne dass die Benutzer umlernen müssen.

Manchmal entstehen neue Fehler (»Bugs«), wenn in ein Programm neue Features eingebaut werden. Manchmal wird ein neues Feature wieder entfernt. Die Werkzeuge waren schlecht dokumentiert, und die subtilen Punkte, die den Regex-Dialekt von regulären Ausdrücken ausmachen, waren meist gar nicht beschrieben. Viele der neu entstehenden Programme haben versucht, Bestehendes nachzuahmen, und dabei ist jeweils fast unweigerlich ein neuer Dialekt entstanden.

Wenn eine solche Änderung mehrfach stattfindet, gibt es eine große Konfusion (besonders, wenn man versucht, mit vielen oder allen Werkzeugen gleichzeitig zu arbeiten (Anmerkung: Wie zum Beispiel jemand, der ein Buch über reguläre Ausdrücke schreibt. Fragen Sie mich, ich kann ein Lied davon singen!)).

POSIX – ein Standardisierungsversuch

POSIX, kurz für Portable Operating System Interface, ist ein Standard, dessen Ziel es ist, die Portabilität von Programmen zwischen verschiedenen Betriebssystemen sicherzustellen. Innerhalb dieses sehr ambitiösen Standards gibt es auch Spezifikationen für reguläre Ausdrücke und viele der traditionellen Programme, die sie benutzen; deshalb betrifft der Standard auch uns, obwohl keines der in diesem Buch behandelten Programme alle Teile des Standards vollständig erfüllt. POSIX ist ein Versuch, die Unordnung zu beseitigen, die über die Jahre entstanden war. Zu diesem Zweck destilliert POSIX aus den zig vorhandenen Varianten genau zwei Typen von regulären Ausdrücken heraus: Basic Regular Expressions (BREs, »grundlegende reguläre Ausdrücke«) und Extended Regular Expressions (EREs, »erweiterte reguläre Ausdrücke«). POSIX-konforme Systeme müssen einen der beiden Dialekte unterstützen. Die folgende Tabelle stellt die Metazeichen der zwei POSIX-Varianten vor.

Tabelle: Regex-Varianten bei POSIX.

Regex-Feature	BRE	ERE
Punkt, ^, $, [...], [^...]	✓	✓
Quantor »Jede beliebige Anzahl«	*	*
Quantoren + und ?		+ ?
Quantor für Bereiche	\{min, max\}	{min, max}
Gruppenbildung	\(...\)	(...)
Quantoren wirken auf Klammerausdrücke	✓	✓
Rückwärtsreferenzen	\1 bis \9
Alternation		✓

Ein Punkt in den POSIX-Standards ist das Konzept eines Locale. Das sind Einstellungen, mit denen ein System an die sprachlichen und kulturellen Konventionen einer bestimmten Umgebung angepasst werden kann. Es geht hier um Dinge wie die Darstellung von Kalenderdaten, Uhrzeiten, Geldbeträgen, die Interpretation von Zeichen in der gewählten Kollationssequenz und anderes mehr. Damit wird eine Internationalisierung der Programme angestrebt. Es handelt sich nicht um ein Regex-spezifisches Konzept, aber es hat auch Auswirkungen auf den Gebrauch von regulären Ausdrücken. Wenn ich in einem Locale arbeite, das den Latin-1-Zeichensatz (ISO-8859-1) benutzt, dann werden Zeichen wie Ä und ä als »Buchstaben« (alphabetische Zeichen mit den numerischen Werten 196 bzw. 228) behandelt, und Programme, die die Groß- und Kleinschreibung ignorieren, betrachten diese zwei als identisch. Diese liegen außerhalb des ASCII-Bereichs (Anmerkung: Mit ASCII ist hier und im Weiteren der ursprüngliche, nicht erweiterte, nicht abgewandelte 7-Bit-Zeichensatz gemeint, der keine Umlaute oder akzentuierte Zeichen enthält.) und würden von den meisten Programmen sonst als Binärdaten betrachtet.

˹\w˼ wird oft als Abkürzung für ein »Wort-Zeichen« benutzt (dasselbe wie ˹[a-zA-Z0-9]˼). Dies wird von POSIX nicht gefordert, aber es ist erlaubt. Wenn ˹\w˼ unterstützt wird, dann passt es auf alle alphabetischen Zeichen, nicht nur auf die Buchstaben des englischen Alphabets.

Beachten Sie aber, dass der Umgang mit Locales durch die Verwendung von Unicode fast immer hinfällig wird.

Henry Spencers Regex-Paket

Ebenfalls 1986, und vielleicht ist dieses Ereignis wichtiger, hat Henry Spencer ein Regex-Paket in C veröffentlicht. Er machte das Paket frei verfügbar – zu der Zeit ein absolutes Novum –, sodass es jeder in sein Programm einbauen konnte. Jedes Programm, das diese Bibliothek benutzte (das waren und sind sehr viele), hatte automatisch den gleichen, konsistenten Regex-Dialekt (außer der Autor hätte sich die Mühe gemacht, das Paket zu verändern).

Auch Perl entwickelt sich

Ungefähr zu dieser Zeit begann Larry Wall mit der Entwicklung eines Werkzeugs, das später Perl werden würde. Er hatte bereits das patch-Programm geschrieben, mit dem die verteilte Software-Entwicklung stark vereinfacht wurde, aber Perl hatte im weiteren Verlauf einen wirklich monumentalen Erfolg.

Larry hat Perl Version 1 im Dezember 1987 veröffentlicht. Von Anfang an war es ein Erfolg, weil es die in der Praxis nützlichen Eigenschaften von vielen bereits vorhandenen Sprachen und Programmen in einem Werkzeug zusammenfasste, Perl war brauchbar im Wortsinn.

Eine wichtige Eigenschaft waren die regulären Ausdrücke, die Perl von sed und awk übernommen hatte – das war für eine Skriptsprache neu. Die Implementation dafür hat Larry von einem seiner früheren Projekte übernommen, von seinem Newsreader rn (der sie wiederum von James Goslings Version von Emacs hatte). (Anmerkung: James Gosling hat später unter anderem auch eine eigene Programmiersprache entworfen, Java, die ab der Version 1.4 eine eigene Regex-Implementation enthält.) Dieser Regex-Dialekt war für die damalige Zeit ganz gut, aber nach heutigen Vorstellungen sehr mager ausgestattet. Man konnte maximal neun Klammerpaare und maximal neun Alternativen mit ˹|˼ verwenden, besonders nachteilig war aber, dass die Alternativen nicht geklammert werden konnten. Es war nicht möglich, Groß- und Kleinschreibung zu ignorieren, ˹\w˼ konnte nicht in Zeichenklassen verwendet werden, ˹\s˼, ˹\d˼ und der Quantor für Bereiche, ˹{min, max}˼, waren unbekannt.

Perl 2 kam im Juni 1988 heraus. Larry hatte den Regex-Code vollständig ersetzt, und zwar durch eine stark erweiterte Version von Henry Spencers Implementation aus dem Abschnitt oben. Nach wie vor waren nur neun Klammerpaare möglich, aber zumindest konnte man jetzt ˹|˼ innerhalb von Klammern verwenden. ˹\d˼ und ˹\s˼ tauchten auf, und die Zeichenklasse ˹\w˼ enthielt jetzt auch den Unterstrich, weil dieser in Perls Bezeichnern erlaubt war und ist. Diese Metazeichen konnten jetzt auch in Zeichenklassen verwendet werden. (Die Gegenstücke ˹\D˼, ˹\W˼ und ˹\S˼ konnten allerdings nicht in Zeichenklassen verwendet werden und funktionierten in bestimmten Fällen ohnehin nicht.) Wichtiger war, dass man mit dem neuen /i-Modifikator unabhängig von Groß- und Kleinschreibung suchen konnte.

Perl 3 erschien mehr als ein Jahr später, im Oktober 1989. Der /e-Modifikator kam dazu, mit dem man mit dem Ersatztext ungeahnte Dinge anstellen konnte, und die Fehler im Zusammenhang mit Rückwärtsreferenzen wurden beseitigt. Der ˹{min, max}˼-Quantor kam dazu, leider mit Kinderkrankheiten. Schlimm war, dass die Regex-Maschine von Version 3 manchmal Probleme mit 8-Bit-Daten hatte; man konnte sich nicht darauf verlassen, dass Nicht-ASCII-Daten korrekt verarbeitet wurden.

Perl 4 wurde anderthalb Jahre später vorgestellt, im März 1991, und wurde in den nächsten zwei Jahren kontinuierlich verbessert, bis zur letzten Version im Februar 1993. Die Fehler früherer Versionen und auch bestimmte Einschränkungen waren beseitigt (man konnte jetzt ˹\D˼ usw. auch in Zeichenklassen verwenden und praktisch beliebig viele Klammern verwenden). Die Leistung der Regex-Maschine wurde optimiert, aber der wirkliche Durchbruch kam erst 1994.

Perl 5 wurde offiziell im Oktober 1994 freigegeben. Perl wurde weitgehend überholt und erweitert, und das Resultat war eine in allen Aspekten wesentlich bessere Programmiersprache. Bei den regulären Ausdrücken wurde intern einiges optimiert, und ein paar neue Metazeichen kamen dazu (z.B. ˹\G˼, mit dem man die iterative oder »globale« Mustersuche feiner steuern kann, siehe Beginn der neuen (oder Ende der letzten) Mustersuche: \G), nicht-einfangende Klammern (siehe Lösung 5), nicht-gierige Quantoren (siehe Nicht-gierige, genügsame Quantoren: *?, +?, ??, {min, max}?), Lookahead (siehe Abschnitt zu Lookahead) und der /x-Modifikator (Anmerkung: Ich habe hier ein bisschen Perl-Geschichte geschrieben: Larry hat bei einer längeren Diskussion über eine große und komplizierte Regex einen Artikel von mir gesehen, in dem ich die Regex nur der Lesbarkeit halber auf mehrere Zeilen verteilt hatte. Das gefiel ihm, und er dachte, dass man auch im Skript eine Regex so schreiben dürfen sollte; er ging hin und implementierte das Feature, das heute /x-Modifikator heißt.) (siehe Abschnitt zum /x-Modifikator).

Diese Erweiterungen machten abgesehen von der nackten Funktionalität auch klar, dass die regulären Ausdrücke zu einer eigenen Programmiersprache herangewachsen waren und noch weiter entwickelt werden konnten.

Die neuen nicht-einfangenden Klammern und die Lookahead-Konstrukte mussten syntaktisch irgendwie ausgedrückt werden. Alle Klammern – (...), [...], <...> oder {...} – waren schon vergeben, daher kam Larry auf die Lösung mit der ›(?‹-Notation, die wir heute in verschiedenen Varianten kennen. Er hat diese Notation gewählt, weil sie in früheren Regex-Versionen unzulässig war; so konnte man sicher sein, dass existierende Programme nicht per Zufall diese neue öffnende Klammer verwendeten. Larry hat dadurch, dass er nur bestimmte Dinge nach ›(?‹ zuließ, außerdem eine Möglichkeit für zukünftige Entwicklungen geschaffen.

Spätere Perl-Versionen wurden zuverlässiger, waren besser optimiert und hatten zusätzliche Features. Auch die erste Auflage dieses Buches hat dabei eine kleine Rolle gespielt, denn ich habe eine Anzahl von Regex-Features erforscht, getestet und die Resultate an Larry und die Perl-Porters-Gruppe weitergegeben und diesen Leuten so gezeigt, wo Verbesserungen anzubringen waren.

Über die Jahre kamen neue Features dazu: Lookbehind (siehe Abschnitt zu Lookbehind), die »atomaren« Gruppen (siehe im Abschnitt Atomare Klammern: (?>...)) und die Unterstützung von Unicode. Mit der Einführung von booleschen Konstrukten (siehe im Abschnitt Bedingte reguläre Ausdrücke: (? if then|else)) wurden If-then-else-Entscheidungen möglich, und mit der Möglichkeit, Perl-Code in regulären Ausdrücken unterzubringen, wurde der Kreis geschlossen (siehe Verrückte Dinge mit den Regex-Erweiterungen in Perl). Dieses Buch behandelt Perl Version 5.8.8.

Eine Flurbereinigung bei den Regex-Dialekten

Die Verbesserungen bei Perl kamen genau zum rechten Zeitpunkt für die WWW-Revolution. Die Stärke von Perl ist die Textverarbeitung, und das Aufbauen von Webseiten ist nichts anderes, daher wurde Perl schnell zu der Programmiersprache in der Webentwicklung. Perl wurde dadurch immer beliebter, und damit auch der Regex-Dialekt von Perl.

Den Entwicklern von anderen Programmiersprachen ist das nicht entgangen, und mit der Zeit entstand eine Reihe von mehr oder weniger »Perl-kompatiblen« Regex-Implementationen. Dazu gehören Tcl, Python, die .NET-Sprachen von Microsoft, Ruby, PHP, C/C++ und etliche Java-Packages.

Eine andere Art der Standardisierung ging von PCRE aus, einem Bibliothekspaket von Philip Hazel, das 1997 herauskam (das ist auch das Erscheinungsjahr der ersten Auflage dieses Buches). PCRE oder ›Perl Compatible Regular Expressions‹ ist ein qualitativ hochstehendes Paket, das Syntax und Semantik der Perl-Regex-Implementation sehr genau abbildet. Dieses Bibliothekspaket wurde von anderen Entwicklern in eine Reihe von Werkzeugen und Programmen integriert, worauf diese eine reiche, zuverlässige und vielen schon vorher bekannte Regex-Funktionalität erhielten. PCRE wird beispielsweise in PHP, Apache HTTPD Version 2, Exim, Postfix und Nmap verwendet.

Programmversionen in diesem Buch

In der folgenden Tabelle sind die Versionsnummern von einigen Programmiersprachen, Bibliotheken und sonstigen Programmen aus diesem Buch aufgeführt. Bei älteren Versionen gibt es meist weniger Features und mehr Fehler, neuere Versionen unterstützen vielleicht neue Features (und haben neue Fehler).

Tabelle: Versionen von in diesem Buch erwähnten Programmen.

GNU awk 3.1	java.util.regex (Java 1.5.0, d.h. Java 5.0)	Procmail 3.22
GNU egrep/grep 2.5.1	.NET Framework 2.0	Python 2.3.5
GNU Emacs 21.3.1	PCRE 6.6	Ruby 1.8.4
flex 2.5.31	Perl 5.8.8	GNU sed 4.0.7
MySQL 5.1	PHP (die preg-Routinen) 5.1.4 / 4.4.3	Tcl 8.4

  

<< zurück

vor >>