Reguläre Ausdrücke – Akademischer Tag 2

Den Begriff „Regulärer Ausdruck“ oder kurz RegEx bzw. RegExp hat ein Großteil der PHP-Entwickler bereits gehört und viele dieser Entwickler haben bereits mit ihnen gearbeitet. Weshalb also gibt es einen Artikel in der Kategorie „Akademischer Tag“ über ein Thema, was die meisten Entwickler bereits kennen? Zum einen kann ein theoretisch fundiertes Verständnis von regulären Ausdrücken helfen, die pragmatischeren regulären Ausdrücke gezielt einzusetzen, und zum anderen kann man durch tiefgründigere Betrachtung generelle Fragen beantworten, wie z.B. ob es zu einer formalen Sprache einen regulären Ausdruck geben kann.

Bevor die regulären Ausdrücke betrachtet werden können, ist es notwendig einige Begriffe einzuführen, damit keine Unklarheiten bei der Formulierung auftreten.

Wörter sind endliche Folgen von Buchstaben aus dem Alphabet Σ. Formal muss ein Wort w = c₁c₂…c_n über Σ aus den Buchstaben aus Σ bestehen, d.h. c₁ ∈ Σ, c₂ ∈ Σ, …, c_n ∈ Σ. Noch formaler: w ∈ Σ^*. Ist beispielsweise Σ = {a,b}, so bestehen alle Wörter über Σ ausschließlich aus a und b. Es gibt nur ein Wort ε, das der o.g. Struktur nicht genügt, da es die Länge 0 besitzt.  ε wird deshalb auch als das leere Wort bezeichnet. Natürlich lassen sich Wörter w₁ = c₁c₂…c_n und w₂ = d₁d₂…d_m verketten. Für das verkettete Wort w = w₁⋅w₂ gilt dann w = c₁c₂…c_nd₁d₂…d_m. Das leere Wort ist das Einselement bzgl. Verkettung, d.h. für alle Wörter w gilt w⋅ε = ε⋅w = w. Bezogen auf PHP entspricht ⋅ dem Operator . und ε dem leeren String.

Reguläre Ausdrücke sind, formal gesehen, eine Darstellungsform regulärer Sprachen, die wiederum ein Spezialfall der formalen Sprachen darstellen. Eine formale Sprache L ist eine Teilmenge von Wörtern (L ⊆ Σ^*), die über einem Alphabet Σ gebildet werden können. Ein kleines Beispiel ist die Sprache die über der Syntax von PHP gebildet wurde. Diese Sprache enthält alle Wörter, die gültigen PHP-Code darstellt. Möchte man wissen, ob der Code syntaktisch korrekt ist, muss man lediglich testen, ob der Code in der formalen Sprache zu PHP vorhanden ist. Dieses Problem nennt man auch Wortproblem. Formal aufgeschrieben: Gilt für ein Wort w, dass w ∈ L?  Für einige Typen von formalen Sprachen ist dieses Problem lösbar, für andere nicht. Man darf dabei nicht vergessen, dass diese Sprachen i.d.R. unendlich viele Elemente enthalten. Ohne allzu sehr auf die Theorie der Formalen Sprachen einzugehen, lässt sich sagen, dass die regulären Sprachen den einfachsten Typ von formalen Sprachen darstellen, wenn man von endlichen Sprachen, d.h. endlichen Mengen, absieht.

Da Sprachen lediglich Mengen von Wörtern sind, lassen sich verschiedene Operationen auf diesen Sprachen definieren. Die für diesen Artikel relevanten Eigenschaften sind die (mengentheoretische) Vereinigung, die Verkettung und die Iteration. Seien L, L₁ und L₂ für die nachfolgenden Definitionen beliebige Sprachen:

• Vereinigung: Die Sprache L₁∪L₂ enthält alle Wörter, die in L₁ oder L₂ oder in beiden enthalten sind.
• Verkettung: Die Sprache L₁⋅L₂ enthält alle Wörter w = w₁⋅w₂ für die gilt, dass w₁ ∈ L₁ und  w₂ ∈ L₂. D.h. L₁⋅L₂ = { w₁⋅w₂ |  w₁ ∈ L_1, w₂ ∈ L₂}_.
  
• Iteration: Die Sprache L^* ist die Vereinigung aller Mengen die aus n-facher Verkettung von L mit sich selbst entsteht, d.h. L^* =  {ε} ∪ L ∪ L⋅L ∪ L⋅L⋅L ∪ …

Bevor die regulären Ausdrücke genauer erläutert werden, sollte es noch Beispiele zu diesen drei wesentlichen Operationen und einigen besonderen Elementen geben.

• {a,b}∪{b,c}  = {a,b,c}
• {a,b}⋅{b,c} = {a⋅b, a⋅c, b⋅b, b⋅c} = {ab, ac, bb, bc}
• {a,b}^* = {ε} ∪ {a,b} ∪ {a,b}⋅{a,b} ∪ {a,b}⋅{a,b}⋅{a,b} ∪ … = {ε, a,b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, …}
• ({a,b}∪{b,c})⋅{a,b} = {a,b,c}⋅{a,b} = {aa, ab, ba, bb, ca, cb}
• {0}^*⋅{1}^* = {ε, 0, 1, 01, 00, 11, 000, 001, 011, 111, …} = { 0ⁿ1^m | n, m sind natürliche Zahlen}
• ∅⋅L = L⋅∅ = ∅ (∅ ist das Nullelement bzgl. Verkettung)
• {ε}⋅L = L⋅{ε} = L ({ε} ist das Einselement bzgl. Verkettung)
• ∅∪L = L∪∅ = L (∅ ist das Einselement bzgl. Vereinigung)

Nun gibt es einen Satz, der besagt, dass jede reguläre Sprache mittels Vereinigung, Verkettung und Iteration aus maximal einelementigen Sprachen, deren Element einbuchstabig ist, gebildet werden kann. Für reguläre Ausdrücke ergeben sich analoge Operationen. Daraus ergibt sich eine induktive Definition der regulären Ausdrücke.

1. Die leere Sprache ∅ ist ein regulärer Ausdruck.
2. Das leere Wort ε ist ein regulärer Ausdruck.
3. Jeder Buchstabe c ∈ Σ ist ein regulärer Ausdruck.
4. Sind α und β reguläre Ausdrücke, so auch (α|β) (Alternative), αβ (Verkettung) und α^* (Iteration).

Sei L(α) die Sprache, die über dem regulären Ausdruck α gebildet wird, dann ergeben sich folgende Zusammenhänge:

1. L(∅) = ∅
2. L(ε) = {ε}
3. L(c) = {c}, wenn c ∈ Σ.
4. L(α|β) = L(α)∪L(β)
5. L(αβ) = L(α)⋅L(β)
6. L(α*) = L(α)*

Als Beispiele dienen die o.g. Sprachen, die wir als reguläre Ausdrücke schreiben werden:

• α = ((a|b)|(b|c)):  L(α) = L((a|b)|(b|c)) = L(a|b)∪L(b|c) = L(a)∪L(b)∪L(b)∪L(c) = {a,b,c}
• α = (a|b)(b|c): L(α) = L(a|b)⋅L(b|c) = (L(a)∪L(b))⋅(L(b)∪L(c)) = {a,b}⋅{b,c} = {ab, ac, bb, bc}
• α = (a|b)^*: L(α) = L(a|b)* = (L(a)∪L(b))*= {a,b}^* = {ε} ∪ {a,b} ∪ {a,b}⋅{a,b} ∪ {a,b}⋅{a,b}⋅{a,b} ∪ … = {ε, a,b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, …}
• α = ((a|b)|(b|c))(a|b): L(α) = L((a|b)|(b|c))⋅L(a|b) = (L(a|b)∪L(b|c))⋅(L(a)∪L(b)) = (L(a)∪L(b)∪L(b)∪L(c))⋅{a,b} =  {a,b,c}⋅{a,b} = {aa, ab, ba, bb, ca, cb}
• α = 0^*1^*: L(α) = L(0^*)⋅L(1^*) = L(0)*⋅L(1)* = {0}^*⋅{1}^* = {ε, 0, 1, 01, 00, 11, 000, 001, 011, 111, …} = { 0ⁿ1^m | n, m sind natürliche Zahlen}

Offensichtlich sind diese regulären Ausdrücke noch viel umständlicher als es vielen bereits jetzt erscheint. Das liegt aber hauptsächlich daran, dass hier kein syntaktischer Zucker verwendet wird, der dem Pragmatiker das Leben erleichtert. Die heutzutage verwendeten Bibliotheken, die reguläre Ausdrücke zur Verfügung stellen, bieten granulare Möglichkeiten zum Erstellen von Mustern während die bisher gezeigten Operationen für die Theoretiker von Vorteil sind, da die Beweise dadurch kürzer werden. Da reguläre Ausdrücke lediglich eine andere Syntax von regulären Sprachen darstellen, lassen sich  Ergebnisse der Theorie der Formalen Sprachen auch sehr leicht auf reguläre Ausdrücke anwenden. Hierbei will ich vor allem das Pumping-Lemma für reguläre Sprachen erwähnen, mit dessen Hilfe man in vielen Fällen feststellen kann, dass eine Sprache nicht regulär ist. Ein mächtigeres Instrument ist der Satz von Myhill-Nerode mit dem man die Existenz eines regulären Ausdrucks zu einer gegebenen formalen Sprache sogar beweisen kann. Außerdem lässt sich mithilfe der sog. Nerode-Relation über den Umweg endlicher Automaten ein regulärer Ausdruck konstruieren, sofern er existiert.

Aber was kann denn nun der Pragmatiker mit diesem Wissen anfangen? Zuerst weiß er, dass preg_match das Wortproblem für reguläre Sprachen löst: Man gebe eine reguläre Sprache durch einen regulären Ausdruck und einen weiteren String, der überprüft werden soll, an: Gibt preg_match eine 1 zurück, so gibt es ein Teilwort, das in der angegebenen regulären Sprache enthalten ist. Außerdem hat man eine mengentheoretische Schreibweise für reguläre Ausdrücke, was in vielen Fällen verständlicher ist als der reguläre Ausdruck selbst. Insgesamt kann das theoretische Wissen vor allem helfen, wenn es um die Grenzen von regulären Ausdrücken geht: Man kann entweder zeigen, dass es zu einer formalen Sprache keinen regulären Ausdruck gibt, oder man konstruiert sich einen regulären Ausdruck.

Einige Themen, die man in diesem Zusammenhang noch hätte klären können, wurden nicht weiter vertieft. Außerdem fehlt noch eine genauere Einordnung der regulären Sprachen… Es gibt also noch viele Themen, an denen man in nachfolgenden Artikeln ansetzen könnte.