Wenn ich eine Liste von regulären Ausdrücken habe, gibt es eine einfache Möglichkeit festzustellen, dass keine von beiden eine Übereinstimmung für dieselbe Zeichenfolge zurückgibt?
Das heißt, die Liste ist nur dann gültig, wenn für alle Strings maximal ein Element in der Liste mit der gesamten Zeichenfolge übereinstimmt.
Es scheint, als wäre das sehr schwer (vielleicht unmöglich?), um definitiv zu beweisen, aber ich kann keine Arbeit zu diesem Thema finden.
Der Grund, warum ich frage, ist, dass ich an einem Tokenizer arbeite, der Regexes akzeptiert, und ich möchte sicherstellen, dass immer nur ein Token mit dem Kopf der Eingabe übereinstimmt.
Wenn Sie mit reinen regulären Ausdrücken arbeiten (keine Rückreferenzen oder andere Funktionen, die kontextfreie oder kompliziertere Sprachen erkennen lassen), ist das, was Sie fragen, möglich. Was Sie tun können, ist, jeden Regex in einen DFA umzuwandeln, und dann (da reguläre Sprachen unter einem Schnittpunkt geschlossen sind) diese zu einem DFA zu kombinieren, der erkennt der Schnittpunkt der beiden Sprachen. Wenn dieses DFA über einen Pfad vom Startstatus in einen akzeptierenden Status verfügt, wird diese Zeichenfolge von beiden Eingabe-Regexen akzeptiert.
Das Problem dabei ist, dass der erste Schritt des üblichen Regex- & Dgr; DFA-Algorithmus es ist Konvertieren Sie die Regex in ein NFA und konvertieren Sie dann das NFA in ein DFA. Aber dieser letzte Schritt kann zu einem exponentiellen Anstieg in der Anzahl der DFA-Zustände führen, so wird dies nur sein machbar für sehr einfache reguläre Ausdrücke.
Wenn Sie mit erweiterter Regex-Syntax arbeiten, sind alle Wetten deaktiviert: kontextfreie Sprachen sind unter Schnittpunkt nicht geschlossen, so dass diese Methode nicht funktioniert.
Der Wkipedia-Artikel über reguläre Ausdrücke gibt an
Es ist möglich, einen Algorithmus zu schreiben, der für zwei gegebene reguläre Ausdrücke entscheidet, ob die beschriebenen Sprachen im Wesentlichen gleich sind, jeden Ausdruck auf eine minimale deterministische endliche Zustandsmaschine reduziert und bestimmt, ob sie isomorph (äquivalent) sind / em>
gibt aber keine weiteren Hinweise.
Natürlich ist es die einfachste Art, viele Tests zu machen - aber wir alle kennen die Unzulänglichkeiten von Tests als Beweismethode.
Sie können das nicht tun, indem Sie nur auf den regulären Ausdruck schauen.
Betrachten Sie den Fall, in dem Sie [0-9] und [0-9]+ haben. Sie sind offensichtlich verschiedene Ausdrücke, aber wenn sie auf die Zeichenkette "1" angewendet werden, erzeugen beide das gleiche Ergebnis. Wenn sie auf die Zeichenfolge "11" angewendet werden, erzeugen sie unterschiedliche Ergebnisse.
Der Punkt ist, dass ein regulärer Ausdruck nicht genug Information ist. Das Ergebnis hängt sowohl von der Regex- als auch von der Zielzeichenfolge ab.
Tags und Links regex mutual-exclusion