Reguläre Ausdrücke beschreiben eine Stufe der formalen Sprachen, die regulären Sprachen. Dieser Sprachtyp befindet sich auf der untersten und somit ausdrucksschwächsten Stufe der Chomsky-Hierarchie (Typ-3). Sie werden erzeugt durch reguläre Grammatiken.
Zu jedem regulären Ausdruck existiert ein endlicher erkennender Automat (Akzeptor), der die vom Ausdruck spezifizierte Sprache akzeptiert. Diese endlichen Automaten können ausgehend von regulären Ausdrücken konstruiert werden. Daraus folgt die relativ einfache Implementierbarkeit regulärer Ausdrücke. Umgekehrt existiert zu jedem endlichen Automaten ein regulärer Ausdruck, der die vom Automaten akzeptierte Sprache beschreibt.
Definition
Definition: Regulärer Ausdruck
Es sei X ein Alphabet. Die regulären Ausdrücke über X und die Wortmengen, die sie bezeichnen, sind folgendermaßen definiert (Syntax):
1. \varnothing ist ein regulärer Ausdruck und bezeichnet die leere Menge {}.
2. \epsilon ist ein regulärer Ausdruck und bezeichnet die Menge \{ \epsilon \}.
3. Für jedes x \in X ist x ein regulärer Ausdruck und bezeichnet die Menge \{ x \}.
4. Sind a und b reguläre Ausdrücke für die Mengen A und B, so sind (a|b) Alternative, (ab) Verkettung (Konkatenation) und (a*) Iteration (Kleenesche Hülle) reguläre Ausdrücke.
5. Nur die gemäß den Regeln 1. bis 4. erzeugten Ausdrücke sind regulär.
Die Klammern können wir gegebenenfalls auch weglassen, wenn wir folgende Prioritätsregeln einführen: Die Iteration ist zuerst auszuführen, dann die Verkettung und dann die Alternative.
Die von einem regulären Ausdruck r bezeichnete Wortmenge heißt auch die zu ihm gehörende reguläre Sprache L(r). In mengentheoretischer Schreibweise gilt für die Verknüpfung von Sprachen:
- L (\varnothing) = \varnothing
- L (\epsilon) = \epsilon
- für jedes x \in X gilt: L (x) = \{ x \}
Gegeben sei ein Alphabet X mit S, T \in T^{*} als Sprachen über X. Dann definieren wir folgende Operationen:
- S \cup T = \{ w \mid w \in S \vee w \in T \} als Vereinigung von S und T.
- S \cap T = \{ w \mid w \in S \wedge w \in T \} als Durchschnitt von S und T
- S \setminus T = \{ w \mid w \in S \wedge w \notin T \} als Differenz von s und T
- ST = \{ uw \mid u \in S \wedge w \in T \} als Produkt von S und T
- S^{0} = \{ \epsilon \}
Formulierung regulärer Ausdrücke
Das Muster eines regulären Ausdrucks besteht aus Terminalen der Sprache und Metazeichen zur Konstruktion eines regulären Ausdrucks. Die hier vorgestellten Symbole sind die im Glossar vom Hess. Kultusministerium vorgegebenen Symbole – im Internet findet man durchaus andere Vereinbarungen.
| Metazeichen | Bedeutung |
|---|---|
| […] | Die in den eckigen Klammern stehenden Zeichen werden als Alternative verwendet. Es können Bereiche angegeben werden, z. B.: [a-p], [3-8]. Die Zeichenklasse steht für ein Zeichen, kann aber mit Quantoren (*, ?, +, {n,m}) vervielfältigt werden. |
| … | … | Stellt Alternativen für das Suchmuster. Die erste auftretende Alternative im String wird gefunden. |
| [^…] | negiert die Klasse, z. B. [^a] |
| (…) | Dient der Gruppierung von Suchmustern. Das gefundene Muster wird in ein Subpattern für spätere Verwendung gespeichert. |
| . | Der Punkt ist Platzhalter für ein beliebiges Zeichen außer für neue Zeile. |
| \ | Der Backslash hebt die besondere Bedeutung von Metazeichen auf, um diese als Text suchen zu können, bzw. macht aus Buchstaben Steuerzeichen. |
Die einzelnen Metazeichen können mit Quantoren ergänzt werden:
| Quantor | Bedeutung |
|---|---|
| ? | Der voranstehende Ausdruck ist optional, er kann einmal vorkommen, muss es aber nicht, d. h. der Ausdruck kommt null- oder einmal vor. (Dies entspricht {0,1}) |
| + | Der voranstehende Ausdruck muss mindestens einmal vorkommen, darf aber auch mehrfach vorkommen. (Dies entspricht {1,}) |
| * | Der voranstehende Ausdruck darf beliebig oft (auch keinmal) vorkommen. (Dies entspricht {0,}) |
| {n} | Der voranstehende Ausdruck muss exakt n-mal vorkommen. |
| {min,} | Der voranstehende Ausdruck muss mindestens min-mal vorkommen. |
| {min,max} | Der voranstehende Ausdruck muss mindestens min-mal und darf maximal max-mal vorkommen. |
| {0,max} | Der voranstehende Ausdruck darf maximal max-mal vorkommen. |
Beispiele
Gegeben sei das Alphabet X= \{a, b\}.
Dann ist a|b ein regulärer Ausdruck für die Sprache {a, b}, ab ein regulärer Ausdruck für die Sprache {ab} und a* ein regulärer Ausdruck für die Sprache \{\epsilon, a, aa, aaa, aaaa, ...\}.
Die Menge aller Worte X* lässt sich durch den regulären Ausdruck [ab]* beschreiben.
Der reguläre Ausdruck [ab]*aa[ab]* bezeichnet die Menge aller Worte aus X*, die wenigstens zwei aufeinander folgende a enthalten, und der reguläre Ausdruck [ab]*bba die Menge aller Worte, die auf bba enden.
Ferner bezeichnet (a|ab)* die Menge \{\epsilon, a, aa, ab, aaa, aab, aba, aaaa, aaab, aaba, abaa, abab, ...\}, d. h. die Menge der Worte, bei denen jedem b zwingend ein a vorsteht.
[egh] … eines der Zeichen e, g oder h.
[0-6] … eine Ziffer von 0 bis 6 (Bindestriche sind Indikator für einen Bereich).
[A-Za-z0-9] … ein beliebiger lateinischer Buchstabe oder eine beliebige Ziffer.
[^a] … ein beliebiges Zeichen außer a
[0-9]{2,5} … zwei, drei, vier oder fünf Ziffern in Folge, z. B. 42 oder 54072
(a|b)(ab)+b? … Wörter aus den Terminalen a und b, die mit einem a oder b beginnen, gefolgt von mindestens einem ab und abgeschlossen mit einem optionalem b (analog gilt: [ab](ab)+b?).
[A-Z]{1,3}-[A-Z]{1,2} [1-9][0-9]{,2} … Beschreibung der üblichen Autokennzeichen.
