Reguläre Ausdrücke verstehen und anwenden

Wir schreiben JavaScript-Muster zwischen Schrägstrichen, etwa /uv/. Die Schrägstriche begrenzen das Muster und gehören nicht zum gesuchten Text. Wir verwenden zunächst keine Zusatzkennzeichen, auch Flags genannt. Solche Kennzeichen können das Suchverhalten ändern. Hier muss die Groß- und Kleinschreibung übereinstimmen. Alle Beispiel-Eingaben bestehen aus einer Zeile ohne Zeilenumbruch.

Ein Literal steht für das Zeichen selbst. Im Muster /uv/ sind „u“ und „v“ Literale: Gesucht ist die zusammenhängende Folge „uv“. Eine Zeichenklasse in eckigen Klammern steht dagegen für genau ein Zeichen aus einer Auswahl. [KR] erlaubt „K“ oder „R“. [0-9] erlaubt eine Ziffer von 0 bis 9; der Bindestrich bezeichnet hier den Bereich.

Ein Quantor gibt an, wie oft der direkt vorhergehende Baustein vorkommen darf. Er gilt für ein einzelnes Zeichen, eine Zeichenklasse oder eine geklammerte Gruppe. Die Tabelle zeigt die Schreibweisen am Zeichen „p“. Für null oder mehr Wiederholungen schreiben wir hier {0,}. Beim Sternquantor steht stattdessen das Sternzeichen unmittelbar hinter dem Baustein. Beide Schreibweisen sind gleichwertig und erlauben dieselben passenden Teilstücke.

Eine Gruppe fasst Bausteine mit runden Klammern zusammen. Bei /(te){2}/ wird die ganze Folge „te“ zweimal verlangt. Das Zeichen | trennt Alternativen: /(JA|NE)/ erlaubt die Folge „JA“ oder die Folge „NE“. Bei jeder Wiederholung einer Zeichenklasse darf ein anderes Zeichen gewählt werden. Auch bei einer wiederholten Gruppe mit Alternativen darf die Wahl wechseln: /(ha|ho){2}/ erlaubt etwa „haho“. Die Muster dieses Abschnitts suchen passende Teilstücke; davor und danach darf weiterer Text stehen.

Ein Teiltreffer ist ein passender zusammenhängender Ausschnitt der Eingabe. Ein Muster ohne Begrenzungen für Anfang und Ende kann einen solchen Ausschnitt finden. Deshalb verhindert eine längere Eingabe nicht automatisch einen Treffer. Die Zahl in einem Quantor begrenzt den passenden Baustein, nicht die Länge der gesamten Eingabe.

Anker legen eine Position fest, ohne selbst ein Zeichen zu verbrauchen. Ohne das Flag m steht der Anfangsanker ^ für den Anfang und der Endanker Dollarzeichen ($) für das Ende der Eingabe. Für eine Prüfung der gesamten Zeichenkette setzt du den Anfangsanker vor und den Endanker hinter das vollständige Muster. Bei Alternativen klammerst du die Auswahl ein: Für die Gesamtprüfung von „hi“ oder „ho“ steht die Gruppe (hi|ho) zwischen den beiden Ankern. In unseren einzeiligen Eingaben muss dann jedes Zeichen zum Muster gehören.

Das Flag m schaltet den mehrzeiligen Modus ein. Dann können die beiden Anker auch an Anfängen und Enden einzelner Zeilen passen. Ein Treffer zwischen diesen Ankern garantiert mit m deshalb keine Prüfung der gesamten mehrzeiligen Eingabe. Unsere Gesamtprüfungen verwenden kein m.

Prüfe zuerst, ob ein Teilstück gesucht oder die gesamte Eingabe geprüft wird. Zerlege dann das Muster in Bausteine. Suche eine zusammenhängende Zeichenfolge, die alle Bausteine in der verlangten Reihenfolge erfüllt. Beachte die Auswahl einer Zeichenklasse, die Wiederholungszahlen und die Groß- und Kleinschreibung.

Beim Muster /(mu|la){2}R?/ müssen zwei Folgen unmittelbar aufeinanderfolgen. Jede Folge darf „mu“ oder „la“ sein. Danach darf ein „R“ stehen, es muss aber nicht vorkommen. Ein einzelnes „mu“ reicht nicht für die zweimal verlangte Gruppe. Ein zusätzliches Zeichen zwischen den beiden Gruppenfolgen würde deren unmittelbare Folge unterbrechen.

Ein Muster kann auch null Zeichen treffen. Diese Folge ohne Zeichen heißt leere Zeichenkette oder leeres Wort. Zum Beispiel erlaubt /e{0,}/ null Wiederholungen von „e“. Es kann deshalb auch in „TUR“ einen leeren Treffer finden, obwohl dort kein „e“ steht. Bei der Gesamtprüfung mit Anfangs- und Endanker ohne das Flag m passt „TUR“ dagegen nicht zu e{0,}: Die vorhandenen Zeichen werden vom Muster nicht erfasst.

In der Theorie heißt eine festgelegte endliche Zeichenmenge Alphabet. Ein Wort ist eine endliche Folge von Zeichen dieses Alphabets; auch die leere Zeichenkette zählt dazu. Eine formale Sprache ist eine Menge solcher Wörter. Ein theoretischer regulärer Ausdruck beschreibt eine solche Menge. Dabei geht es um ganze Wörter der Sprache. Die praktische Suche nach einem passenden Teilstück ist eine zusätzliche Suchaufgabe.

Theoretische reguläre Ausdrücke beruhen auf drei Operationen: Alternative wählt zwischen Ausdrücken, Verkettung setzt sie hintereinander und Wiederholung erlaubt null oder mehr Wiederholungen. Zeichenklassen und feste Wiederholungszahlen sind bequeme Kurzschreibweisen für passende Kombinationen dieser Operationen.

Ein endlicher Automat ist ein Modell mit einer festen endlichen Menge von Zuständen. Ein Zustand beschreibt die aktuelle Situation des Modells beim Lesen. Der Automat beginnt in einem Startzustand und liest ein Wort Zeichen für Zeichen. Übergangsregeln legen fest, welcher Zustand als Nächstes erreicht wird. Nach dem letzten Zeichen wird das Wort angenommen, wenn der erreichte Zustand als annehmend festgelegt ist. Die Zustandsmenge ist fest; längere Eingaben erzeugen keine zusätzlichen Zustände.

Zu jedem theoretischen regulären Ausdruck gibt es einen endlichen Automaten, der genau seine Sprache annimmt. Umgekehrt lässt sich die Sprache jedes endlichen Automaten durch einen theoretischen regulären Ausdruck beschreiben. Diese Gleichwertigkeit betrifft die beschreibbaren Sprachen, nicht eine gleiche Schreibweise oder einen gleichen Aufbau.

Praktische Suchsysteme können zusätzliche Funktionen anbieten. Eine Rückwärtsreferenz verlangt erneut genau den Text, den eine Gruppe zuvor innerhalb desselben Treffers erfasst hat. Solche Erweiterungen können Sprachen beschreiben, die nicht regulär sind. Deshalb gilt die Gleichwertigkeit mit endlichen Automaten nicht pauschal für alle erweiterten Suchmuster.