Facebook
0
Twitter
0
Google+
0
Kommentare
18

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 = c1c2…cn über Σ aus den Buchstaben aus Σ bestehen, d.h. c1 ∈ Σ, c2 ∈ Σ, …, cn ∈ Σ. 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 w1 = c1c2…cn und w2 = d1d2…dm verketten. Für das verkettete Wort w = w1⋅w2 gilt dann w = c1c2…cnd1d2…dm. 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, L1 und L2 für die nachfolgenden Definitionen beliebige Sprachen:

  • Vereinigung: Die Sprache L1∪L2 enthält alle Wörter, die in L1 oder L2 oder in beiden enthalten sind.
  • Verkettung: Die Sprache L1⋅L2 enthält alle Wörter w = w1⋅w2 für die gilt, dass w1 ∈ L1 und  w2 ∈ L2. D.h. L1⋅L2 = { w1⋅w2 |  w1 ∈ L1, w2 ∈ L2}.
  • 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, …} = { 0n1m | 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, …} = { 0n1m | 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.

Über den Autor

Andre Moelle

Kommentare

18 Comments

  1. Holla die Waldfee. Sollte mir abgewöhnen phphatesme vor dem ersten kaffee zu lesen, das schlägt auf den magen :)

    Danke für den Artikel, auch wenn ich ihn in 1-2h, mit mehr koffein im körper und wachen synapsen nochmal lesen muss :-)

    Ludwig

    Reply
  2. Uff, also die Formeln hauen schon richtig gut rein :D Ich glaub ich hab’s nach einem Mal lesen schon gut zu 40% verstanden ;) Genauso wie LudwigR brauch ich wohl auch erstmal nen Kaffee, um das richtig verdauen zu können :D

    Reply
  3. Vielleicht liegt’s daran, dass ich nicht so der Kaffee-Trinker bin – aber irgendwie lacht mich der Artikel nicht so wirklich zum Durchlesen an :)

    Ich denke ich kann Regex einigermaßen gut – aber das is mir dann doch ne Ecke zu theoretisch *g

    Reply
  4. Man haette noch den Weg zur Chomsky-Hierarchie schlagen sollen, und darauf hinweisen sollen, dass regulaere Sprachen nur links- oder rechtslinearen Grammatiken entsprechen. Die entscheidende und oft ignorierte Konsequenz daraus ist, dass regulaere Ausdruecke keine rekursiven Strukturen erfassen koennen (und somit weder XML noch BBCode parsen _koennen_).

    Uebrigens laesst sich (z.B. mit dem erwaehnten pumping lemma) sehr einfach nachweisen, dass die in PHP ueber pcre implementierten “regulaeren Ausdruecke” weit ueber die Maechtigkeit formaler regulaerer Ausdruecke hinausgehen, mehr dazu hier http://kore-nordmann.de/blog/do_NOT_parse_using_regexp.html und hier http://kore-nordmann.de/blog/parse_with_regexp.html

    Reply
  5. @Kore: Das Thema ist so vielfältig, dass ich einige Themen bewusst weggelassen habe, um den Umfang des relativ lang gewordenen Artikels nicht zu sprengen. Außerdem sollte es auch noch Ansatzpunkte für weiterführende Themen (Chomsky-Hierarchie, Reguläre Sprachen, Automaten, …) geben, die man in weiteren Artikel ansprechen kann.
    Die Intention dieses Artikels war lediglich, einige Grundlagen zu regulären Ausdrücken zu beschreiben, die beim Verständnis regulärer Ausdrücke helfen könnten – mir persönlich hatte es geholfen, diese Kenntnisse zu besitzen.
    Dass die “regulären Ausdrücke” in verschiedenen Implementierungen mächtiger als die formalen regulären Ausdrücke sind, war mir bekannt, aber bisher habe ich keinen Artikel gesehen, der das so schön ausgearbeitet hat (der Link ist direkt in meine Lesezeichen gewandert – danke).

    Reply
  6. Super Artikel!
    Macht spass, von Zeit zu Zeit das Theoriewissen aufzufrischen – man vergisst es dann eh wieder ;-)

    Eine Sache hat mich allerdings irritiert: die zwei Beispiele {0}*⋅{1}* – soweit ich das verstehe, sollte die daraus resultierende Sprache nur Woerter enthalten, die mit beliebig vielen Nullen beginnen, gefolgt von beliebig vielen Einsern… Woerter wie “010″ sollten also nicht enthalten sein.

    Kann natuerlich auch sein, dass ich einen Denkfehler habe ;-)

    Gut. Klugscheiss-Modus aus, und nochmal vielen Dank fuer die “Akademischer Tag”-Artikel.

    lg r.

    Reply
  7. Gut, habe den Artikel mal als Lesezeichen hinzugefügt, und wenn ich dann in so 5-6 Jahren Informatik studiert habe, werde ich ihn aufrufen und noch mal lesen und dann weiter als bis zum ersten Viertel kommen…

    Reply
  8. @sebastian: wenn du informatik studierst kommt sowas gleich im ersten semester, nur viel ausführlicher :-)

    Echt guter Artikel, teilweise sogar besser erklärt wie unser prof dazu.

    Reply
  9. Na toll. Da war ich heute das erste mal auf diesem Blog und bin dann gleich über diesen “Brummer” gestolpert ;-)

    Reply
  10. Hat jemand vielleicht eine gute Buchempfehlung zu diesem Thema ? So das man sich mal einlesen kann in die Materie ?

    Reply
  11. Ich kann dir für das Verständnis “Kompendium Theoretische Informatik: Eine Ideensammlung” [1] von Ingo Wegener empfehlen. Bei ihm geht es hauptsächlich um Beweisideen und eine Beschreibung der wichtigsten Themen der theoretischen Informatik – es geht also nicht nur um formale Sprachen. Für eine formalere Einführung (mit Beweisen) kann ich dir leider keine Buchempfehlung aussprechen.

    [1] http://www.amazon.de/Kompendium-Theoretische-Informatik-Eine-Ideensammlung/dp/3519021455

    Reply

Leave a Comment.

Link erfolgreich vorgeschlagen.

Vielen Dank, dass du einen Link vorgeschlagen hast. Wir werden ihn sobald wie möglich prüfen. Schließen