Dieser Artikel zeigt, dass es beim Zurückverfolgen eine gewisse Regexp gibt, die O (2 ^ n) ist.
Das Beispiel ist (x+x+)+y .
Wenn versucht wird, eine Zeichenkette wie xxxx ... p zu finden, wird es eine Weile zurücklaufen, bevor Sie herausfinden, dass es nicht passt.
Gibt es eine Möglichkeit, solche Regexp zu erkennen?
Danke
Wenn Ihre regexp-Engine Exponentiallaufzeitverhalten für (x + x +) + y exponiert, dann ist es gebrochen , weil ein DFA oder NFA dieses Muster in linearer Zeit erkennen kann:
%Vor%antworten beide sofort.
Tatsächlich gibt es nur wenige Fälle (wie Rückwärtsreferenzen), bei denen Backtracking wirklich benötigt wird (hauptsächlich, weil ein Regexp mit einer Rückreferenz nicht mehr ein regulärer Ausdruck im sprachentheoretischen Sinn ist). Eine fähige Implementierung sollte nur dann zu Backtracking wechseln, wenn diese Eckfälle angegeben werden.
Fairerweise haben DFAs auch eine dunkle Seite, weil einige Regexps exponentielle Größenanforderungen haben, aber eine Größenbeschränkung ist einfacher durchzusetzen als eine Zeitbeschränkung und der riesige DFA läuft linear am Input, also ist es ein besseres Schnäppchen als ein kleiner Backtracker, der auf ein paar X erstickt.
Sie sollten wirklich Russ Cox ausgezeichnete Artikelserie über die Implementierung von regexp (und das pathologische Verhalten von backtracking) lesen: Ссылка
Um Ihre Frage zur Entscheidbarkeit zu beantworten: Sie können nicht. Weil es nicht das Zurückverfolgen für regexpr gibt. Jede Implementierung hat ihre eigenen Strategien, um mit exponentiellem Wachstum ihres Algorithmus für bestimmte Fälle umzugehen, und sie deckt andere nicht ab. Eine Regel mag hier und dort katastrophal sein.
UPDATE:
Zum Beispiel könnte eine Implementierung einen Optimierer enthalten, der algebraische Transformationen verwenden könnte, um Regexps vor der Ausführung zu vereinfachen: (x+x+)+y ist gleich a xxx*y , was kein Problem für Backtracker sein sollte. Aber derselbe Optimierer würde den nächsten Ausdruck nicht erkennen und das Problem ist wieder da. Hier hat jemand beschrieben, wie man einen Regexpr fertigt, der Perls Optimierer täuscht:
Nein, ich denke nicht, aber Sie können diese Richtlinien verwenden:
Quantifizierer, die dies verursachen können, sind: * , + und {k,} .
Beachten Sie auch, dass die Worst-Case-Komplexität beim Auswerten eines regulären Ausdrucks sehr von der Komplexität typischer Strings abweichen kann und dass die Komplexität von der spezifischen Engine für reguläre Ausdrücke abhängt.
Jeder Regex ohne Rückreferenzen kann in linearer Zeit abgeglichen werden, obwohl viele Regex-Engines es in der realen Welt nicht so machen (zumindest unterstützen viele Regex-Engines, die an Programmiersprachen-Laufzeitumgebungen angeschlossen sind, Rückreferenzen und don Wechseln Sie nicht zu einem effizienteren Ausführungsmodell, wenn keine Rückverweise vorhanden sind.
Es gibt keinen einfachen Weg herauszufinden, wie viel Zeit eine Regex mit Rückreferenzen verbrauchen wird.
Sie konnten verschachtelte Wiederholungen mit einem Regex-Parser erkennen und ablehnen, was einer Sternenhöhe von 1 entspricht. Ich habe gerade ein Modul geschrieben, um Anfangshöhen von & gt; 1 mit einem Regex-Parser von npm zu berechnen und abzulehnen.
%Vor%Tags und Links algorithm regex complexity-theory