Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 41

Reguläre Ausdrücke

Reguläre Ausdrücke bieten einfache Operatoren, um Konstruktionsregeln für Zeichenketten festzulegen:

 »Worte« sind die nicht weiter zerlegbaren Satzbestandteile, in unseren Beispielen etwa a, b etc.

Sequenz

 Die Sequenz beschreibt das »Hintereinanderschreiben«: pq

Auswahl

 Die Auswahl ermöglicht die Wahl zwischen zwei Alternativen: p + q

Iteration

 Die Iteration ermöglicht das Wiederholen von Satzbausteinen: p* (0-, 1- oder n-mal)Eine oft genutzte Variante der Iteration schließt die »leere« Iteration aus: p+ (1- oder n-mal)

 Zusätzlich besteht die Möglichkeit der Klammerung zur Strukturierung. Ansonsten gilt »Punkt- vor Strichrechnung«.

Der Einsatz regulärer Ausdrücke soll nun anhand einiger Beispiele erläutert werden:

 Mit L beginnende Binärzahlen über L und O können wie folgt beschrieben werden:L(L + O)*Eine Binärzahl beginnt also mit einem L, danach kann eine beliebig lange Folge von L und O kommen. Beispiele sind L, LO, LOLO, LOOOOOOLLLL.Mit einer kleinen Variation generieren wir zusätzlich auch die O als einzige mit diesem Symbol startende Zahl:O + L (L + O)*

 Ein weiteres Beispiel sind Bezeichner einer Programmiersprache, die mit einem Buchstaben anfangen müssen, nach dem ersten Buchstaben aber auch Ziffern enthalten dürfen:(a + b + … + z)(a + b + … + z + 0 + 1 + … 9)*Beispiele für generierte Wörter sind abba, mz4, u2; kein Beispiel wäre 124c4u.

Reguläre Ausdrücke sind für mehrere Bereiche der Informatik relevant: Sie werden zur Festlegung von Datenformaten für Programmeingaben genutzt, definieren Muster zum Suchen in Texten und Suchmasken in Programmiersprachen.

Reguläre Ausdrücke sind ein einfacher Mechanismus zur Festlegung einer generierten Sprache. Im Folgenden werden wir einen komplexeren Mechanismus kennen lernen.