Friedl-Schema

Glossar > Friedl-Schema

Als Friedl-Schema wird hier ein Muster bezeichnet, das J.E.F. Friedl in seinem Buch: Reguläre Ausdrücke, formuliert hat, um ewiges Matching zu vermeiden.

Friedl nennt als besonders unglückliches Beispiel für ewiges Matching:

"(\\.|[^"\\\r\n]+)*"

Dieser Ausdruck besagt, dass ein String aus den beiden äußeren Anführungszeichen besteht und im Innern aus einer Wiederholung. Wiederholt wird die Alternative eines Backslashs gefolgt von einem weiteren Zeichen (so wird sichergestellt, das der Backslash nicht unmittelbar vor dem schließenden Anführungszeichen steht) und einer Folge von Zeichen, die weder Zeilenumbruchszeichen noch ein Anführungszeichen (das den String beenden würde) sind.

Das Problem an diesem Ausdruck ist, dass Zeichenfolgen vor einem Backslash auf mehrere Weisen interpretiert werden können und dass (bei einem POSIX-NFA Regex, wie er im TextTransformer verwendet wird) stets alle Permutationen durchprobiert werden. Wegen der Verschachtelung der beiden Wiederholungsoperatoren '*' und '+' sind dies extrem viele. ( drei Zeichen sind eine Folge aus einem und zwei Zeichen oder eine Folge aus zwei und einem Zeichen). Eine solches Durchprobieren (Backtracking) führt zu einer sehr langsamen Erkennung des gesamten Ausdrucks. Friedl gibt ein Beispiel, bei dem die Auswertung eines derartigen Ausdrucks die Lebenszeit des Programmierers übersteigen würde.

Das ewige Matching kann vermieden werden, wenn der obige Ausdruck folgendermaßen umformuliert wird:

"([^"\\\r\n]*(\\.[^"\\\r\n]*)*)"

Allgemein unterliegt der neue Ausdruck dem Schema:

öffnend normal * ( speziell normal *)* schließend

wobei der Anfang von speziell und normal nicht gleich sein darf.

( öffnend == schließend == " )

Hier verbietet normal einen Backslash: [^"\\\r\n]

und speziell fordert ihn: \\.

Hier gibt es an jedem Punkt der Erkennung nur eine klare Alternative. Tatsächlich ist das Friedl Schema eine LL(1)-Optimierung.

Diese Seite gehört zur TextTransformer Dokumentation