Reguläre Ausdrücke: Viel mächtiger, als Sie denken

The true power of regular expressions (2012)

Dieser Artikel aus dem Jahr 2012 räumt mit dem Mythos auf, dass reguläre Ausdrücke nur reguläre Sprachen verarbeiten können. Der Autor zeigt anhand von PCRE, wie moderne Regex-Engines dank Rekursion und benannten Untergruppen sogar kontextfreie Grammatiken wie E-Mail-Adressen nach RFC 5322 matchen können. Er erklärt den Unterschied zwischen formaler Sprachtheorie und praktischer Implementierung und beweist, dass reguläre Ausdrücke jede kontextfreie Sprache erkennen können – auch wenn das Parsen in einen Syntaxbaum nicht möglich ist.