Regulärer Ausdruck

In der Informatik ist ein Regulärer Ausdruck (Abk. RegExp oder Regex, engl. regular expression) eine Zeichenkette, die der Beschreibung von Mengen beziehungsweise Untermengen von Zeichenketten mit Hilfe bestimmter syntaktischer Regeln dient. Reguläre Ausdrücke finden vor allem in der Softwareentwicklung Verwendung; für fast alle Programmiersprachen existieren Implementierungen.

Reguläre Ausdrücke stellen erstens eine Art Filterkriterium für Texte dar, indem der jeweilige reguläre Ausdruck in Form eines Musters mit dem Text abgeglichen wird. So ist es beispielsweise möglich, alle Wörter, die mit S beginnen und mit D enden, zu matchen (von englisch „to match“ – „auf etwas passen“, „übereinstimmen“, „eine Übereinstimmung finden“), ohne die zwischenliegenden Buchstaben explizit vorgeben zu müssen.

Ein weiteres Beispiel für den Einsatz als Filter ist die Möglichkeit, komplizierte Textersetzungen durchzuführen, indem man die zu suchenden Zeichenketten durch reguläre Ausdrücke beschreibt.

Zweitens lassen sich aus regulären Ausdrücken, als eine Art Schablone, auch Mengen von Wörtern erzeugen, ohne jedes Wort einzeln angeben zu müssen. So lässt sich beispielsweise ein Ausdruck angeben, der alle denkbaren Zeichenkombinationen (Wörter) erzeugt, die mit S beginnen und mit D enden.

[Bearbeiten] Reguläre Ausdrücke in der theoretischen Informatik

[Bearbeiten] Theoretische Grundlagen

Hinweis: In diesem Abschnitt wird die Kenntnis einiger Konzepte der Theorie der formalen Sprachen vorausgesetzt.

Reguläre Ausdrücke beschreiben eine Familie von formalen Sprachen und gehören damit zur Theoretischen Informatik. Hier bilden sie die unterste und somit ausdrucksschwächste Stufe der Chomsky-Hierarchie (Typ-3). Es lässt sich zeigen, dass zu jedem regulären Ausdruck ein gleichwertiger endlicher Automat existiert und umgekehrt. Dieser Automat ist einfach bestimmbar. Hieraus folgt die relativ einfache Implementierbarkeit regulärer Ausdrücke.

Der Mathematiker Stephen Kleene benutzte eine Notation, die er reguläre Mengen nannte. Die Mächtigkeit regulärer Ausdrücke reicht aus, um – von wenigen Ausnahmen abgesehen – die Morphologie einer natürlichen Sprache zu beschreiben.

Reguläre Ausdrücke unterstützen genau drei Operationen: Alternative, Verkettung und Wiederholung. Die formelle Definition sieht folgendermaßen aus:

[Bearbeiten] Syntax

1. (die leere Menge) ist ein regulärer Ausdruck.
2. (das leere Wort) ist ein regulärer Ausdruck.
3. ist a_i (jedes Zeichen aus dem zugrundeliegenden Alphabet) ein regulärer Ausdruck.
4. Sind x und y reguläre Ausdrücke, so auch (x | y) (Alternative), (xy) (Verkettung) und x ^* (Kleenesche Hülle).
5. Es gibt keine weiteren regulären Ausdrücke.

[Bearbeiten] Anwendung regulärer Ausdrücke

Ken Thompson nutzte diese Notation in den 1960ern um qed (eine Vorgängerversion des Unix-Editors ed) zu bauen und später das Werkzeug grep zu schreiben. Seither implementieren sehr viele Programme und Bibliotheken von Programmiersprachen Funktionen, um reguläre Ausdrücke zum Suchen und Ersetzen von Zeichenketten zu nutzen. Beispiele dafür sind die Programme sed, grep, emacs und Bibliotheken der Programmiersprachen Perl, C, Java, Python, Ruby und das .NET Framework; auch die Textverarbeitung und die Tabellenkalkulation des Office-Paketes OpenOffice.org bieten die Möglichkeit, mit regulären Ausdrücken im Text zu suchen.

Die jeweiligen Regexp-Implementierungen sind jedoch nicht alle gleich. In den Programmiersprachen haben sich überwiegend die PCRE (Perl Compatible Regular Expressions) durchgesetzt, die sich an der Umsetzung in Perl orientieren. Daneben wird – vor allem in der Linux-Welt – z. B. zwischen BRE (basic regular expressions) und ERE (extended regular expressions) unterschieden.
Einige Programme wie z. B. der Texteditor vim bieten die Möglichkeit, zwischen verschiedenen Regexp-Umsetzungen hin- und herzuschalten.

Die meisten heutigen Implementierungen unterstützen Erweiterungen wie z. B. Rückwärtsreferenzen (backreferences). Hierbei handelt es sich nicht mehr um reguläre Ausdrücke im Sinne der theoretischen Informatik, denn die so erweiterten Ausdrücke gehören nicht mehr notwendigerweise zum Typ 3 der Chomsky-Hierarchie.

Häufig werden reguläre Ausdrücke angewendet, um Programm-Quelltexte lexikalisch zu analysieren, beispielsweise in Compilern oder zur Syntaxhervorhebung in Editoren. Dazu wird der Quelltext mit einem (dann vergleichsweise komplexen) regulären Ausdruck in sogenannte Tokens (Schlüsselwörter, Operatoren usw.) zerlegt. Werden Teile des Quelltextes nicht vom regulären Ausdruck erkannt, so hat sich ein Syntaxfehler in den Quelltext eingeschlichen. Die syntaktische oder semantische Analyse eines Programms kann jedoch normalerweise nicht mit regulären Ausdrücken durchgeführt werden, dafür wird eine kontextfreie Sprache benötigt.

[Bearbeiten] Elemente, mit denen sich ein regulärer Ausdruck festlegen lässt

Die folgenden Syntaxbeschreibungen beziehen sich auf die Syntax der gängigen Regex-Implementierungen mit Erweiterungen, sie entsprechen also nur teilweise der obigen Definition aus der theoretischen Informatik.

Eine häufige Anwendung regulärer Ausdrücke besteht darin, spezielle übereinstimmende Zeichenketten in einer Menge von Zeichenketten zu finden. Die im Folgenden angegebene Beschreibung ist eine (oft benutzte) Konvention, um Konzepte wie Zeichenklasse, Quantifizierung, Verknüpfung und Zusammenfassen konkret zu realisieren. Hierbei wird ein regulärer Ausdruck aus den Zeichen des zugrunde liegenden Alphabets in Kombination mit sogenannten Metazeichen ( [ ] ( ) { } |  ? + * ^ $ \ . ) gebildet. Alle übrigen Zeichen des Alphabets stehen für sich selbst.

[Bearbeiten] Zeichenliterale

Diejenigen Zeichen, die direkt (wörtlich, literal) übereinstimmen müssen, werden auch direkt notiert. Je nach System gibt es auch Möglichkeiten, den Oktal- oder Hexadezimalcode anzugeben.

[Bearbeiten] Beliebiges Zeichen

Ein Punkt (.) bedeutet, dass an seinem Platz ein (fast) beliebiges Zeichen stehen kann. Abhängig vom verwendeten Programm oder dessen Einstellungen kann ein Punkt auch für Newline (Zeilenumbruch) stehen. Die meisten Implementierungen sehen standardmäßig Newline nicht als beliebiges Zeichen an, jedoch kann in einigen Programmen mithilfe des sogenannten s-Modifiers (z. B. in /foo.bar/s) ebendies erreicht werden.

[Bearbeiten] Ein Zeichen aus einer Auswahl

Mit eckigen Klammern lässt sich eine Zeichenauswahl definieren. Der Ausdruck in eckigen Klammern steht dann für genau ein Zeichen aus dieser Auswahl. Innerhalb dieser Zeichenklassendefinitionen haben einige Symbole andere Bedeutungen als im normalen Kontext. Teilweise ist die Bedeutung eines Symbols sogar davon abhängig, wo es sich innerhalb der Klammern befindet.

So bedeutet z. B. ein Zirkumflex „^“ am Anfang einer Zeichenklassendefinition, dass die Zeichenklasse negiert/invertiert wird. Steht ein Zirkumflex jedoch irgendwo sonst in der Definition, ist es literal zu verstehen. Ebenfalls positionsabhängig ist das Minus-Zeichen. Steht es am Anfang oder Ende der Klassendefinition, so ist es literal gemeint. Steht es jedoch zwischen zwei Zeichen der Klasse, z. B. „[a-g]“, so ist es als Bis-Strich bzgl. der ASCII-Tabelle zu verstehen, d. h. hier im Beispiel wäre äquivalent dazu „[abcdefg]“. Die Meta-Eigenschaft eines Zeichens kann durch ein Backslash aufgehoben werden.

In vielen neueren Implementationen können innerhalb der eckigen Klammern nach POSIX auch Klassen angegeben werden, die selbst wiederum eckige Klammern enthalten. Sie lauten beispielsweise:

¹Was Buchstaben sind, ist im Allgemeinen locale-abhängig, also abhängig von der eingestellten Region und Sprache.^[1]

[Bearbeiten] Vordefinierte Zeichenklassen

Es gibt vordefinierte Zeichenklassen, die allerdings nicht von allen Implementierungen unterstützt werden, da sie lediglich Kurzformen sind und auch durch eine Zeichenauswahl beschrieben werden können. Wichtige Zeichenklassen sind:

[Bearbeiten] Quantoren (Angabe der Anzahl Wiederholungen)

Quantoren (auch Quantifizierer oder Wiederholungsfaktoren) erlauben es, den vorherigen Ausdruck in verschiedener Vielfachheit in der Zeichenkette zuzulassen.

Die Quantoren beziehen sich dabei auf den regulären Ausdruck, jedoch nicht zwangsläufig auf die durch ihn gematchte Zeichenkette. So wird zwar zum Beispiel durch a+ ein „a“ oder auch „aaaa“ vertreten, jedoch entspricht [0-9]+ nicht nur sich wiederholenden gleichen Ziffern, sondern auch Folgen gemischter Ziffern, beispielsweise „072345“.

Weitere Beispiele sind:

• „[ab]+“ entspricht „a“, „b“, „aa“, „bbaab“ etc.
• „[0-9]{2,5}“ entspricht zwei, drei, vier oder fünf Ziffern in Folge, z. B. „42“, „54072“, jedoch nicht zum Beispiel die Zeichenfolgen „0“, „1.1“ oder „a1a1“.

Soll eine Zeichenkette nur aus dem gesuchten Muster bestehen (und es nicht nur enthalten), so muss in den meisten RegExp-Implementierungen explizit definiert werden, dass das Muster von Anfang (\A oder ^)¹ bis zum Ende der Zeichenkette (\Z, \z oder $)¹ reichen soll, ansonsten matcht zum Beispiel [0-9]{2,5} auch bei der Zeichenkette „1234507“ die Teilzeichenkette „12345“. Aus dem gleichen Grund würde bspw. a* immer matchen, da jeder String, selbst der leere „“, mind. 0-mal das Zeichen „a“ enthält.

¹Die Zeichen ^ und $ matchen im multiline-Modus (d. i. wenn der m-Modifier gesetzt wird) auch Zeilenanfänge und -enden.

[Bearbeiten] Gieriges Verhalten

Normalerweise wird von einem regulären Ausdruck die größtmögliche passende Zeichenkette ausgewählt, weshalb dieses Verhalten als „gierig“ (engl.: „greedy“) bezeichnet wird. Da dieses Verhalten jedoch nicht immer so gewollt ist, lassen sich bei manchen neueren RegEx-Implementierungen Quantoren als „genügsam“ bzw. engl. „non-greedy“ (also „nicht gierig“, auch reluctant, „zurückhaltend“) deklarieren. Z. B. in Perl wird hierfür dem Quantor ein Fragezeichen ? nachgestellt. Die Implementierung von genügsamen Quantoren ist vergleichsweise aufwändig, weshalb nicht alle Parser diese unterstützen. Der durch das angehängte Fragezeichen entstehende Ausdruck führt deshalb bei herkömmlichen RegEx-Implementierungen zu einer Fehlermeldung, wird ignoriert oder das Fragezeichen wird literal interpretiert.

Beispiel (Perl-Syntax)

Angenommen es wird auf den String „ABCDEB“ der reguläre Ausdruck A.*B angewendet, so würde er den kompletten String „ABCDEB“ finden. Mit Hilfe des „non-greedy“-Quantors „*?“ passt der neue Ausdruck, also A.*?B, nur auf die Zeichenkette „AB“, bricht also die Suche nach dem ersten gefundenen „B“ ab.

[Bearbeiten] Possessives Verhalten

Eine Variante des oben beschriebenen gierigen Verhaltens ist das possessive Matching. Da hierbei jedoch das Backtracking verhindert wird, werden einmal gematchte Zeichen nicht wieder freigegeben. Aufgrund dessen finden sich in der Literatur auch die synonymen Bezeichnungen atomic grouping, independant subexpression oder non-backtracking subpattern. Die Syntax für diese Konstrukte variiert bei den verschiedenen Programmiersprachen. Ursprünglich wurden solche Subpattern in Perl durch (?>Ausdruck) formuliert. Daneben existieren seit Perl 5.10 die äquivalenten, in Java bereits üblichen possessiven Quantoren ++, *+, ?+, {min,max}+.

Beispiel

Angenommen es wird auf den String „ABCDEB“ der reguläre Ausdruck A.*+B angewendet, so würde der Matchingversuch fehlschlagen. Bei der Abarbeitung des regulären Ausdrucks würde der Teil .*+ bis zum Ende des Strings matchen. Um einen erfolgreichen Match zu erzeugen, müsste ein Zeichen, hier also das „B“, wieder freigegeben werden. Der possessive Quantor verbietet dies aufgrund des unterdrückten Backtrackings, weshalb kein erfolgreiches Matching stattfinden kann.

[Bearbeiten] Gruppierung mit runden Klammern

Ausdrücke lassen sich mit runden Klammern ( und ) zusammenfassen: Etwa erlaubt „(abc)+“ ein „abc“ oder ein „abcabc“ etc.

Einige Programme speichern die Gruppierung ab und ermöglichen deren Wiederverwendung im Regulären Ausdruck oder bei der Textersetzung. Ein Suchen und Ersetzen mit AA(.*?)BB als regulären Suchausdruck und \1 als Ersetzung ersetzt alle Zeichenketten, die von AA und BB eingeschlossen sind, durch den zwischen AA und BB enthaltenen Text. D. h. AA und BB und der Text dazwischen werden ersetzt durch den Text, der ursprünglich zwischen AA und BB stand, also fehlen AA und BB im Ergebnis. \1, \2 usw. nennt man Rückwärtsreferenzen (engl. „Backreferences“). \1 bezieht sich auf das erste Klammerpaar, \2 auf das zweite usw.; dabei zählt man die öffnenden Klammern.

Interpreter von regulären Ausdrücken, die Rückwärtsreferenzen zulassen, entsprechen nicht mehr dem Typ 3 der Chomsky-Hierarchie. Mit dem Pumping-Lemma lässt sich einfach zeigen, dass folgender regulärer Ausdruck, der feststellt, ob in einem String vor und nach der 1 die gleiche Anzahl von 0 steht, keine reguläre Sprache ist.

[Bearbeiten] Alternativen

Man kann alternative Ausdrücke mit dem „|“-Symbol zulassen:

• „ABC|abc“ bedeutet „ABC“ oder „abc“, aber z. B. nicht „Abc“.

[Bearbeiten] Weitere Zeichen

Um die oft auf Zeichenketten bezogenen Anwendungen auf dem Computer zu unterstützen, werden in der Regel zusätzlich zu den bereits genannten die folgenden Zeichen definiert:

[Bearbeiten] Look-around assertions

Perl Version 5 führte zusätzlich zu den üblichen regulären Ausdrücken auch look-ahead und look-behind assertions (etwa "vorausschauende" bzw. "nach hinten schauende" "Annahme/Behauptung") ein, was unter dem Begriff look-around assertions zusammengefasst wird.^[2] Diese Konstrukte erweitern die regulären Ausdrücke um die Möglichkeit, kontextsensitive Bedingungen zu formulieren, ohne den Kontext selbst zu matchen. D. h., möchte man alle Zeichenfolgen "Sport", denen die Zeichenfolge "verein" folgt, matchen, ohne die Zeichenfolge "verein" selbst zu matchen, wäre dies mit einer look-ahead assertion möglich: Sport(?=verein). Aufgrund der Eigenschaft, dass der angegebene Kontext (im Beispiel "verein") zwar angegeben wird, jedoch kein expliziter Bestandteil des gematchten Strings (hier "Sport") ist, wird im Zusammenhang mit den assertions meist das Attribut zero-width mitgenannt. Die vollständigen Bezeichnungen lauten somit, je nachdem ob ein bestimmter Kontext gefordert (positiv) oder verboten (negativ) ist, zero-width positive/negative look-ahead/behind assertions. Die Bezeichnungen der Richtungen rühren daher, dass Regexp-Parser einen String immer von links nach rechts abarbeiten.

Look-arounds werden neben Perl und PCRE unter anderem von .NET Framework sowie von Python unterstützt. Auch einige Texteditoren wie z. B. Vim bieten die Möglichkeit, wenn auch mit teilweise anderer Syntax.

[Bearbeiten] Bedingte Ausdrücke

Relativ wenig verbreitet sind bedingte Ausdrücke. Diese sind u. a. in Perl, PCRE und dem .NET Framework einsetzbar. Python bietet für solche Ausdrücke in Zusammenhang mit look-around assertions nur eingeschränkte Funktionalität.^[3]

[Bearbeiten] Literatur

Reguläre Ausdrücke

• Jeffrey Friedl: Reguläre Ausdrücke. O’Reilly, ISBN 3-89721-720-1.
• Tony Stubblebine: Reguläre Ausdrücke – kurz und gut. O’Reilly, ISBN 3-89721-264-1.
• Mehran Habibi: Real World Regular Expressions with Java 1.4. Springer, ISBN 1-59059-107-0.

Reguläre Ausdrücke und natürliche Sprachen

• Kenneth R. Beesley,Lauri Karttunen: Finite-State Morphology. Distributed for the Center for the Study of Language and Information. 2003, 696 p. (est.). 2003 Series: (CSLI-SCL) Studies in Computational Linguistics,

[Bearbeiten] Siehe auch

• Wildcard
• PCRE (Perl-kompatible reguläre Ausdrücke)
• ω-regulärer Ausdruck

[Bearbeiten] Weblinks

• Regex-Evaluator
• Reguläre Sprachen, reguläre Ausdrücke
• Regex-Kurs für Anfänger mit Übungen
• POSIX-Spezifikation für reguläre Ausdrücke (englisch)
• Perl–Syntax regulärer Ausdrücke (englisch)

[Bearbeiten] Referenzen

1. ↑ The Open Group Base Specifications, RE Bracket Expression, IEEE Std 1003.1, 2004
2. ↑ Regular-Expressions.info: Lookahead and Lookbehind Zero-Width Assertions
3. ↑ Regular-Expressions.info: If-Then-Else Conditionals in Regular Expressions