Wie kann ich ein endliches Muster in alle möglichen Übereinstimmungen erweitern?

Question

beispielsweise angesichts der Muster

[a-zA-Z]_[0-9]{2} 

eine Funktion des Musters nehmen würde und ein Array oder eine Liste zurück, enthaltend

a_00, a_01, a_02, ... , a_98, a_99, ... , z_98, z_99 

nur Zahlen und Buchstaben (und finite Gruppierungen davon) erweitert werden müssen. Wie würde ich das machen? Ein Beispiel in Python oder Perl wäre bevorzugt. Vielen Dank!

Answer 1

Analysieren Sie zunächst den Ausdruck und erstellen Sie einen Baum, der die syntaktische Struktur des regulären Ausdrucks widerspiegelt, und schließen Sie einen Terminatorknoten ein, der am Ende logisch erscheint. Zum Beispiel in Lisp-Notation, könnte Ihr Beispiel wie folgt aussehen:

(concat 
    (repeat 2 
    (concat 
     (charset 
     (range a z) 
     (range A Z)) 
     (literal _) 
     (charset 
     (range 0 9)))) 
    terminator) 

Als nächstes fädeln den Baum, so dass Sie die Rekursion verwenden können, die kombinatorische Expansion zu erzeugen. Damit meine ich z.B. dass Knoten a..z in (concat a .. z) alle müssen Zeiger von einem zum nächsten haben, so a Punkte auf b, und so weiter, und der concat Knoten selbst verweist auf seinen Nachfolger. Die Idee ist, dass Sie eine Version des aktuellen Elements in der Erweiterung erzeugen und in das nächste Element zurückspringen können. Wenn das nächste Element zurückkehrt, können Sie die nächste Version des aktuellen Elements usw. ausprobieren, bis alle Versionen erschöpft sind und Sie kehren zu Ihrem Anrufer (Vorgänger oder Eltern) zurück. Dieses Threading erfolgt am einfachsten mit einem Stack und einer Traversierung des Baums nach der Order. Wenn Sie Knoten während des Post-order-Traversalvorgangs vorsichtig drücken, ist der Anfang des Stapels das nächste Element in der Sequenz.

(Eine Alternative zum Einfädeln ist der Baum so zu strukturieren, dass das nächste Element in jedem concat Knoten ein Kind des vorherigen Knoten ist, und repeat Knoten Kinder zeigen auf den Wiederholungsknoten zurück.)

Dann schreiben eine Routine (oder ein Satz von Routinen, die Mustervergleiche verwenden, oder virtuelle Methoden, wenn Knoten in dem Baum unter Verwendung von Polymorphismus in einer objektorientierten Sprache implementiert sind), die für jeden gegebenen Knotentyp die korrekte Ausgabe erzeugen und in den nächsten Knoten oder die nächsten Kinder zurückführen in der richtigen Weise. Zum Beispiel in Pseudo-Code:

if node is of form (repeat n): # non-variable repeat 
    for i in 1 to n 
     recurse into child 
    recurse into threaded successor 

if node is of form (concat ...): 
    recurse into first element # last element will recurse into successor 

if node is of form (literal x): 
    emit x 
    recurse into successor 
    remove x 

if node is of form (charset ...): 
    for each element in charset: 
     emit element 
     recurse into successor 
     remove element 

if node is terminator: 
    add string created thus far to final output list 

usw. Wie Sie beobachten können, Kinder eines Wiederholungsknoten dürfen nicht in den Nachfolger des repeat Knoten rekursiv, so dass berücksichtigt werden muss, wenn der Baum Threading. Eine ähnliche Sorgfalt ist darauf zu richten, dass der "aktuelle Fortschritt" nicht verloren geht, wenn das Ende der Kindknoten eines repeat Knotens erreicht wird; alternativ könnte der Nachfolger von Kindknoten auf den Wiederholungsknoten selbst zeigen (d. h. eine echte Schließung über dem Graphen von Knoten), aber das erfordert das Speichern eines Zählers irgendwo.

Alles in allem könnte die Fertigstellung mehrere Tage dauern, je nachdem wie flexibel und performant es sein muss. Beachten Sie auch, dass bestimmte Konstrukte wie Kleene Stern oder Schließung (* oder + in erweiterten Regex) zu einer unendlichen Liste führen. Eine Sprache, die Generatoren (z. B. die Iteratorsyntax von C#) oder Korotinen/Fortsetzungen (z. B. Schemes Aufruf/cc) oder Lazy Evaluation (z. B. Haskell) unterstützt, kann eine Iteration über die ersten Elemente der Liste ermöglichen, ohne die gesamte Liste auswerten zu müssen. Alternativ kann das Wählen eines Zufallspotentialausgangs anstatt einer erschöpfenden Iteration zum Vorsehen von Beispielen, die einem regulären Ausdruck entsprechen, bevorzugt sein.

Answer 2

Vorausgesetzt, dass Sie die Länge der Zeichenfolgen der passenden Längen, herausfinden können, könnten Sie es zwingen, indem Sie alle möglichen Zeichenketten mit den korrekten Längen erzeugen und dann nur versuchen, zusammenzupassen.

Answer 3

Verwenden Sie thrax !! Thrax bietet Befehlszeilentools für die Interaktion mit dem leistungsstarken OpenFST-Toolkit. Sie können es wahrscheinlich auf Paket-Managern wie apt oder macports finden.

Hier ist ein Beispiel, wie Thrax verwendet wird, um eine Regex zu testen. Heute wollte ich einen Namen für eine Bibliothek herausfinden, die ich schreibe. Ich wollte, dass der Name ein Akronym für complete embedded? mrf? (optimization|inference) toolkit ist. Nach dem Versuch, einen Namen manuell zu finden, gab ich auf und schrieb die folgende Regex für mögliche Akronyme: co?m?e?m?[io]to?.

So jetzt das Problem reduziert, um einige Zeichenfolgen, die dieses Akronym erfüllen. Hier kommt der Thrax ins Spiel. Wir können den Regex zuerst in eine grm Datei schreiben.

[Save following in file named tmp.grm] 
sigma=("c"|"o"|"m"|"e"|"i"|"o"|"t"); 
export a= Optimize[ ("c":"c") (("o":"")|("o":"o")) (("m":"")|("m":"m")) (("e":"")|("e":"e")) (("m":"")|("m":"m")) (("o":"o")|("i":"i")) ("t":"t") (("o":"")|("o":"o")) ]; 

Sie können wahrscheinlich raten, was vor sich geht. Für jede x? habe ich angegeben, dass entweder x ausgegeben wird oder '' ausgegeben wird. Jetzt können wir diese grm Datei kompilieren und Zeichenfolgen aus der Sprache extrahieren.

thraxcompiler --save_symbols --input_grammar=tmp.grm --output_far=tmp.far 
thraxrandom-generator --far=tmp.far --rule=a --noutput=100 

Die Ausgabe enthält mögliche Zeichenfolgen, die die Regex abgleichen kann. Ich denke, es gibt auch Dienstprogramme für die Erzeugung aller möglichen Ausgänge mit Thrax, aber wenn Sie nur eine große Anzahl von Zeichenfolgen und uniq sie, die eine gute 90% solution sein sollte.

**************************************** 
comemoto 
cmemot 
**************************************** 
comemoto 
comoto 
**************************************** 
comemoto 
comot 
**************************************** 
comemito 
coemito 
**************************************** 
comemoto 
coeot 
**************************************** 
comemoto 
cmeot 
**************************************** 
comemito 
coit 
**************************************** 
comemoto 
cemot 
**************************************** 
comemoto 
ceoto