Regex-Implementierung, die maschinengenerierte reguläre Ausdrücke verarbeiten kann: * kein Backtracking *, O (n)?
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:
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.