Bearbeiten 2: Eine praktische Demonstration, warum dies weiterhin wichtig ist, finden Sie hierDer durch Regex verursachte Ausfall von stackoverflow heute (20.07.2016)!

Bearbeiten: Diese Frage hat sich erheblich entwickelt, seit ich sie zum ersten Mal gestellt habe. Im Folgenden finden Sie zwei schnelle + kompatible Implementierungen, die jedoch nicht über alle Funktionen verfügen. Wenn Sie mehr oder bessere Implementierungen kennen, erwähnen Sie diese bitte, hier gibt es noch keine ideale Implementierung!

Wo kann ich findenzuverlässig schnelle Regex-Implementierung?

Kennt jemand einen normalenNicht-Backtracking (System.Text.RegularExpressions Backtracks) lineare Time-Regex-Implementierung entweder für .NET oder native und vernünftigerweise von .NET verwendbar? Um nützlich zu sein, müsste es:

haben eineschlimmsten Fall Zeit-Komplexität der Regex-Auswertung vonO (m * n) Dabei ist m die Länge des regulären Ausdrucks und n die Länge der Eingabe.haben einenormale zeitliche Komplexität von O (n), da fast keine regulären Ausdrücke tatsächlich den exponentiellen Zustandsraum auslösen oder, falls dies möglich ist, nur bei einer winzigen Teilmenge der Eingabe.haben einevernünftige Baugeschwindigkeit (d. h. keine potenziell exponentiellen DFAs)zur Verwendung durch Menschen bestimmt sein, nicht durch Mathematiker - z. Ich möchte Unicode-Zeichenklassen nicht erneut implementieren:Zeichenklassen im .NET- oder PCRE-Stil sind von Vorteil.Bonuspunkte:Bonuspunkte für die Praktikabilität, wenn es Stack-basierte Funktionen implementiert, dieLass es mit dem Schachteln umgehen auf Kosten des Verbrauchs von O (n + m) Speicher anstelle von O (m) Speicher.Bonuspunkte fürentweder Unterausdrücke erfassenoder Ersetzungen (wenn es eine exponentielle Anzahl möglicher Übereinstimmungen mit Unterausdrücken gibt, dann Aufzählung)alles von ihnen ist von Natur aus exponentiell - aber das Aufzählen der ersten sollte nicht sein, und in ähnlicher Weise für Ersatz). Sie können das Fehlen einer der beiden Funktionen mithilfe der anderen umgehen. Daher ist es ausreichend, eine der beiden Funktionen zu verwenden.viele Bonuspunkte fürRegex als erstklassige Werte behandeln (Sie können also die Vereinigung, Schnittmenge, Verkettung, Negation - insbesondere Negation und Schnittmenge - nehmen, da diese durch String-Manipulation der Regex-Definition sehr schwierig sind.)Lazy Matching d.h. das Abgleichen auf unbegrenzten Streams, ohne alles in den Speicher zu stellen, ist ein Plus. Wenn die Streams das Suchen nicht unterstützen, ist das Erfassen von Unterausdrücken und / oder Ersetzungen (im Allgemeinen) nicht in einem Durchgang möglich.Rückverweise sind aussind sie grundsätzlich unzuverlässig; kann bei pathologischen Eingabefällen immer ein exponentielles Verhalten zeigen.

Solche Algorithmen gibt es (Dies ist die grundlegende Automatentheorie ...) - aber gibt es praktisch verwendbareImplementierungen erreichbar von .NET?

Hintergrund: (Sie können dies überspringen)

Ich benutze gerne Regex für schnelle und schmutzige Textbereinigungen, aber ich bin wiederholt auf Probleme gestoßen, bei denen die von Perl / Java / Python / .NET verwendete Backtracking-NFA-Implementierung exponentielles Verhalten aufweist. Diese Fälle sind leider ziemlich einfach auszulösen, sobald Sie beginnen, Ihre regulären Ausdrücke automatisch zu generieren. Sogar nicht-exponentielle Leistung kann außerordentlich schlecht werden, wenn Sie zwischen regulären Ausdrücken wechseln, die mit demselben Präfix übereinstimmen. Wenn Sie beispielsweise ein Wörterbuch in einen regulären Ausdruck umwandeln, müssen Sie mit einer schrecklichen Leistung rechnen.

Einen schnellen Überblick darüber, warum es seit den 60er Jahren bessere Implementierungen gibt, finden Sie unterDer Abgleich mit regulären Ausdrücken kann einfach und schnell sein.

Nicht ganz praktische Optionen:Fast ideal: FSA-Toolkit. Kann reguläre Ausdrücke für schnelle C-Implementierungen von DFAs + NFAs kompilieren, ermöglicht auch Wandler (!), Hat erstklassige reguläre Ausdrücke (Kapselung yay!), Einschließlich Syntax für Schnittmenge und Parametrisierung.Aber es ist im Prolog... (warum ist etwas mit dieser Art von praktischen Funktionen nicht in einer Standardsprache verfügbar ???)Schnell aber unpraktisch: ein voller Parser, wie der ausgezeichneteANTLR Unterstützt im Allgemeinen zuverlässig schnelle reguläre Ausdrücke. Die Syntax von antlr ist jedoch weitaus ausführlicher und erlaubt natürlich Konstrukte, die möglicherweise keine gültigen Parser generieren, sodass Sie eine sichere Teilmenge finden müssen.Gute Implementierungen:RE2 - eine Open Source-Bibliothek von Google, die eine angemessene PCRE-Kompatibilität ohne Rückverweise anstrebt. Ich denke, dies ist der Nachfolger der Unix-Portierung von plan9s Regex Lib, wenn man den Autor bedenkt.TRE - Auch meistens kompatibel mit PCRE und führt sogar Rückreferenzen durch, obwohl Sie bei diesen Geschwindigkeitsgarantien verlieren. Und es hat einen mega-nifty ungefähren Matching-Modus!

Leider handelt es sich bei beiden Implementierungen um C ++, und für die Verwendung von .NET ist Interop erforderlich.