Ich arbeite gerade an einem Scanner-Generator. Der Generator funktioniert schon gut. Aber bei Verwendung von Zeichenklassen wird der Algorithmus sehr langsam.
Der Scanner-Generator erzeugt einen Scanner für UTF8-kodierte Dateien. Der gesamte Zeichenbereich (0x000000 bis 0x10ffff) sollte unterstützt werden.
Wenn ich große Zeichensätze verwende, wie etwa den Operator '.' oder die Unicode-Eigenschaft {L}, die nfa (und auch die dfa) enthält viele Zustände (& gt; 10000). Die Konvertierung von nfa nach dfa und das Erstellen des minimalen dfa dauert also sehr lange (auch wenn das minimale Ausgabe-dfa nur wenige Zustände enthält).
Hier ist meine aktuelle Implementierung des Erstellens eines Zeichensatzes in der nfa.
%Vor%Kann jemand die Funktion viel effizienter implementieren, um nur die notwendigen Zustände zu erzeugen?
BEARBEITEN:
Um genauer zu sein, brauche ich eine Funktion wie:
%Vor%Eine Hilfsfunktion zum Konvertieren eines Zeichens (int) in ein UTF8-Codierungsbyte [] ist definiert als:
%Vor%Es gibt mehrere Möglichkeiten, damit umzugehen. Sie alle laufen darauf hinaus, in den Datenstrukturen Zeichensätze gleichzeitig zu behandeln, anstatt das gesamte Alphabet jemals aufzuzählen. Es ist auch, wie Sie Scanner für Unicode in einer vernünftigen Menge an Speicher machen.
Sie haben viele Möglichkeiten, Zeichengruppen darzustellen und zu verarbeiten. Ich arbeite gerade mit einer Lösung, die eine geordnete Liste von Randbedingungen und entsprechenden Zielzuständen führt. Sie können Operationen auf diesen Listen viel schneller als Sie konnten, wenn Sie das gesamte Alphabet an jeder Kreuzung scannen mussten. Tatsächlich ist es schnell genug, dass es in Python mit akzeptabler Geschwindigkeit läuft.
Ich hatte das gleiche Problem mit meinem Scanner-Generator, daher habe ich die Idee, Intervalle durch ihre IDs zu ersetzen, was anhand des Intervallbaums bestimmt wird. Zum Beispiel kann ein..z-Bereich in dfa wie folgt dargestellt werden: 97, 98, 99, ..., 122, stattdessen stelle ich Bereiche wie [97, 122] dar, baue dann aus ihnen eine Intervall-Baumstruktur, also am Ende Sie werden als IDs dargestellt, die sich auf den Intervallbaum beziehen. Mit dem folgenden RE: a..z + enden wir mit einem solchen DFA:
%Vor%Komprimiere jetzt die Intervalle:
%Vor%Extrahiere alle Intervalle aus deinem DFA und baue einen Intervallbaum daraus:
%Vor%Ersetzen Sie die tatsächlichen Intervalle durch ihre IDs:
%Vor%In dieser Bibliothek ( Ссылка ) tue ich das, indem ich anstelle von einzelnen Zeichen eine Reihe aufeinanderfolgender Zeichen für jeden Übergang verwende . Dies wird durch alle Schritte der NFA-Konstruktion, NFA- & gt; DFA-Konvertierung, DFA-Minimierung und Optimierung durchgeführt.
Es ist ziemlich kompakt, aber es fügt Code-Komplexität zu jedem Schritt hinzu.