Kommentare 2

Die Geschichte des Begriffs „regulärer Ausdruck“

Der Begriff regulärer Ausdruck kommt aus der Mathematik und der theoretischen Informatik. Dort steht er für eine Eigenschaft mathematischer Ausdrücke namens Regularität. Solch ein Ausdruck kann als Software mithilfe eines deterministischen endlichen Automaten
(DEA) implementiert werden. Ein DEA ist ein endlicher Automat, der kein Backtracking nutzt.

Die Textmuster, die von den ersten grep-Tools genutzt wurden, waren reguläre Ausdrücke im mathematischen Sinn. Auch wenn der Name  geblieben ist, sind aktuelle reguläre Ausdrücke im Perl-Stil keine regulären Ausdrücke im mathematischen Sinn. Sie sind mit einem nicht deterministischen endlichen Automaten (NEA) implementiert.  Alles, was ein  normaler Entwickler aus diesem kleinen Artikel mitnehmen muss, ist, dass ein paar Informatiker in ihren Elfenbeintürmen sehr verärgert darüber sind, dass ihr wohldefinierter Begriff durch eine Technologie überlagert wurde, die in der realen Welt viel nützlicher ist.

Bei O’Reilly ist soeben das Reguläre Ausdrücke Kochbuch erschienen, aus dem dieser Textauszug entnommen ist.

2 Kommentare

  1. Afirel sagt

    Schöne Geschichte, leider nur unzureichend recherchiert. Nicht-deterministische endliche Automaten (NEA) lassen sich in deterministische (DEA) überführen, die Umkehrung gilt per Definition.

    Das soll heißen: Die Mächtigkeit der NEA geht nicht über reguläre Ausrücke hinaus.

    Vermutlich meinte die Autorin Funktionen wie backreferences in Perl-kompatiblen regulären Ausdrücken (PCRE). Diese gehen schon über den ursprünglichen Begriff der regulären Ausdrücke im Sinne der theoretischen Informatik hinaus.

    Elfenbeintürme hin oder her, da reicht schon ein Blick in Wikipedia [1].

    [1] http://de.wikipedia.org/wiki/Regul%C3%A4rer_Ausdruck

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.