Ich habe versucht, invRegex.py zu portieren für eine Weile auf eine node.js-Implementierung, aber ich kämpfe immer noch damit. Ich habe bereits den regulären Ausdruck parse Baum dank der ret.js Tokenizer und es funktioniert ziemlich gut, aber die tatsächliche Generation und Die Verkettung aller einzelnen Elemente in einer Weise, die speichereffizient ist, ist für mich sehr herausfordernd. Um es einfach zu halten, sagen wir, ich habe die folgende Regex:
%Vor% Die Ausgabe an invRegex.py erzeugt die folgende Ausgabe ( tabbified , um weniger Platz zu beanspruchen):
Wenn ich bedenke, dass ich jedes einzelne Token erhalten und ein Array aller gültigen einzelnen Ausgaben erzeugen kann:
%Vor%Ich kann das kartesische Produkt aller Arrays berechnen und die gleiche erwartete Ausgabe erhalten:
%Vor% Das Problem dabei ist, dass es alle 36 Werte im Speicher hält. Wenn ich einen etwas komplizierteren regulären Ausdruck hätte, wie zum Beispiel [a-z]{0,10} , würde es 146813779479511 Werte im Speicher halten, was völlig undurchführbar ist. Ich möchte diese riesige Liste auf eine asynchrone Art und Weise verarbeiten, jede generierte Kombination an einen Callback übergeben und es mir erlauben, den Prozess an jedem vernünftigen Punkt zu unterbrechen, den ich für richtig halte, ähnlich wie invRegex.py oder dieses Haskell-Paket - leider kann ich Haskell nicht verstehen und ich weiß auch nicht, wie ich das generator-Verhalten in Python auch auf Javascript anwenden soll.
Ich habe versucht, ein paar einfache Generator-Experimente in Knoten 0.11.9 (mit --harmony ) wie diesem auszuführen:
Es ist unnötig zu sagen, dass das obige nicht funktioniert. = /
Hier mit dem Kopf gegen die Wand schlagen, also wäre jede Hilfe, die dieses Problem angeht, sehr geschätzt.
UPDATE : Hier ist ein Beispiel für den ret.js-Syntaxbaum für b[a-z]{3} :
Der SET / RANGE -Typ sollte 26 verschiedene Werte ergeben, und der übergeordnete REPETITION -Typ sollte diesen vorherigen Wert auf die Potenz von 3 bringen, was 17576 verschiedene Kombinationen ergibt. Wenn ich ein verflachtes tokens -Array wie zuvor für cartesianProductOf erzeugen würde, würden die abgeflachten Zwischenwerte so viel Platz beanspruchen wie das eigentliche kartesische Produkt selbst.
Ich hoffe, dieses Beispiel erklärt das Problem, dem ich gegenüberstehe, besser.
Ich rate Ihnen, Iterator-Klassen zu schreiben. Sie sind einfach zu implementieren (im Grunde sind sie State-Maschinen), sie haben einen geringen Speicherbedarf, sie können kombiniert werden, um immer komplexere Ausdrücke aufzubauen (bitte scrollen Sie nach unten, um das Endergebnis zu sehen), und der resultierende Iterator kann in ein Aufzähler.
Jede Iterator-Klasse hat die folgenden Methoden:
Beginnen Sie mit dem einfachsten Fall: eine Folge von einem oder mehreren Zeichen, die wörtlich zusammenpassen sollten (z. B. / foo / ). Unnötig zu sagen, dass es nur eine Übereinstimmung gibt, also wird 'ok' beim ersten Aufruf von 'next' falsch.
%Vor%Zeichenklassen ( [abc] ) sind ebenfalls trivial. Der Konstruktor akzeptiert eine Zeichenfolge; Wenn Sie Arrays bevorzugen, ist das leicht zu beheben.
%Vor%Jetzt brauchen wir Iteratoren, die andere Iteratoren kombinieren, um komplexere reguläre Ausdrücke zu bilden. Eine Sequenz besteht aus zwei oder mehr Mustern in einer Reihe (wie foo [abc] ).
%Vor%Eine andere Möglichkeit zum Kombinieren von Iteratoren ist die Wahl (auch Alternativen), z. foo | bar .
%Vor%Andere Regex-Funktionen können durch Kombination der vorhandenen Klassen implementiert werden. Klassenvererbung ist eine großartige Möglichkeit, dies zu tun. Zum Beispiel ist ein optionales Muster ( x? ) nur eine Wahl zwischen der leeren Zeichenfolge und x .
%Vor%Wiederholung ( x {n, m} ) ist eine Kombination aus Sequenz und Optional. Da ich das eine oder das andere erben muss, besteht meine Implementierung aus zwei voneinander abhängigen Klassen.
%Vor%Wie ich bereits sagte, kann ein Iterator in einen Enumerator eingebunden werden. Dies ist einfach eine Schleife, die Sie brechen können, wann immer Sie wollen.
%Vor%Zeit, alles zusammen zu stellen. Nehmen wir einen dummen regulären Ausdruck:
%Vor%Das Erstellen des Iterator-Objekts ist sehr einfach:
%Vor%Das ergibt 28 Treffer, aber ich erspare Ihnen die Ausgabe.
Ich entschuldige mich, wenn mein Code nicht mit Softwaremustern kompatibel ist, nicht browserkompatibel ist (funktioniert in Chrome und Firefox einwandfrei) oder er leidet unter einem schlechten OOP. Ich hoffe nur, es macht das Konzept klar.
EDIT: Der Vollständigkeit halber habe ich nach der Initiative von OP eine weitere Iterator-Klasse implementiert: die Referenz .
Eine Referenz (\ 1 \ 2 etc.) nimmt die aktuelle Übereinstimmung einer früheren Erfassungsgruppe auf (d. h. alles in Klammern). Seine Implementierung ist sehr ähnlich zu Literal , da es genau eine Übereinstimmung hat.
%Vor% Der Konstruktor erhält einen Iterator, der das referenzierte Untermuster darstellt. Nehmen wir (foo|bar)([xy]) als Beispiel (ergibt fooxxfoo, fooyyfoo, barxxbar, baryybar ):
Erfassungsgruppen werden beim Aufbau der Baumstruktur der Iteratorklassen angegeben. Ich mache das immer noch manuell, aber irgendwann soll das automatisiert werden. Das ist nur eine Frage des Zuordnens Ihres Syntaxbaums zu einer ähnlichen Baumstruktur von Iteratorklassen.
EDIT 2: Hier ist eine relativ einfache rekursive Funktion, die einen Parse-Baum konvertiert, der von ret.js erzeugt wird zu einem Iterator.
%Vor%Verwendung:
%Vor%Ich stelle alle Komponenten in dieser Demo zusammen: Ссылка
Hinweis: Viele Regex-Syntax-Konstrukte werden nicht unterstützt (Anker, Look-Ahead, Look-Behind, Rekursion), aber ich denke, es ist schon ziemlich gleichwertig mit invRegex.py.
Hier ist eine Version, die für jeden Teil der Eingabe eine Funktion erstellt und alle zusammensetzt, um eine Funktion zu erzeugen, die jedes Regex-Ergebnis erzeugt und in dieses Argument eingibt:
%Vor%Geändert, um von einem Parse-Baum abzuarbeiten (kopierte einen kleinen Code von hier ):
%Vor%Wenn Sie mit einer weniger funktional, mehr C-esque Lösung in Ordnung sind:
%Vor%Es klingt, als ob Sie nach Lazy Cartesian Product fragen: Sie wollen das kartesische Produkt, aber wollen Sie nicht alle vorher berechnen (und konsumieren) all diese Erinnerung). Anders gesagt, Sie möchten das kartesische Produkt durchlaufen.
Wenn das stimmt, haben Sie diese Javascript-Implementierung der X (n) -Formel ausgecheckt? Damit können Sie entweder über sie in natürlicher Reihenfolge "& lt; & lt; 0,0,0 & gt ;, & lt; 0,0,1 & gt;", & lt; 0,1,0 & gt ;, ... & gt; oder wähle eine beliebige Position aus, um sie zu berechnen.
Es scheint so, als könnten Sie es einfach tun:
%Vor%Sicher muss ich etwas verpassen ...? Generatoren sind einfach übertrieben mit der Formel X (n).
Update
In einen JSFiddle habe ich eine instrumentierte Version des lazyProduct codes platziert , ein Beispiel-Tokens-Array von Arrays und ein Aufruf von lazyProduct mit diesen tokens .
Wenn Sie den Code ohne Änderung ausführen, sehen Sie, dass er die Ausgabe 0@a usw. aus dem Beispiel tokens -Array generiert. Ich denke, der Link erklärt die Logik ziemlich gut, aber zusammenfassend ... Wenn Sie die Instrumentierung in lazyProduct auskommentieren, werden Sie feststellen, dass es zwei Schlüsselvariablen gibt: lens und p . lens ist eine Vorberechnung der Länge jedes übergebenen Arrays (in dem Array von Arrays). p ist ein Stack, der den aktuellen Pfad bis zu dem Ort enthält, an dem Sie sich befinden (z. B. Wenn Sie "1. Array 3. Index, 2. Array 2. Index und 3. Array 1. Index" p repräsentiert das, und dies ist, was in Ihre Callback-Funktion übergeben wird.
Meine Callback-Funktion führt nur einen Join für die Argumente durch (für Ihr OP-Beispiel), aber wieder sind dies nur die entsprechenden Werte in p, die dem ursprünglichen Array von Arrays zugeordnet sind.
Wenn Sie dies weiter profilieren, sehen Sie, dass der Footprint, der zum Erstellen des kartesischen Produkts benötigt wird, auf das beschränkt ist, was Sie zum Aufrufen Ihrer Callback-Funktion benötigen. Probieren Sie es auf einem Ihrer Worst-Case-Tokens aus.
Update 2
Ich habe etwa 75% eines Ansatzes codiert, der auf kartesischen Produkten basiert. Meine API hat einen ret.js-Parse-Baum genommen, diesen in RPN konvertiert und dann Mengen von Sätzen erzeugt, die in einen X (n) -Rechner übertragen wurden. Unter Verwendung von @ruud Beispiel von ([ab]{2}){1,2}|[cd](f|ef{0,2}e) würde dies erzeugt werden:
Die kniffligen Teile waren verschachtelte Optionen (Buggy) und umgekehrte Zeichenklassen & amp; Rückverweise (nicht unterstützt).
Dieser Ansatz wurde spröde, und die Iterator-Lösung ist wirklich überlegen. Konvertieren von Ihrem Parse-Baum in das sollte ziemlich einfach sein. Danke für das interessante Problem!
Hier gibt es bereits viele gute Antworten, aber ich wollte, dass der Generator funktioniert, was nicht für Sie war. Es scheint, dass Sie das versucht haben:
%Vor%Ausgabe:
%Vor%Sie können dies für ein kartesisches Produkt verwenden, das beim Regex-Abgleich benötigt wird.
Ich möchte nur teilen, was ich herausgefunden habe, mit Generatoren und basierend auf invRegex.py :
Ich habe immer noch nicht herausgefunden, wie man einfangende Gruppen / Referenzen implementiert und die Werte, die im REPETITION -Token-Typ erzielt werden, werden noch nicht in lexikographischer Reihenfolge erzeugt, aber ansonsten funktioniert es.
Tags und Links python javascript node.js generator iterator