Regulären Ausdruck in Automaten umwandeln. Performanceprobleme

[Gast]

Hallo,

ich schreibe einen Lexergenerator. Nur zu Übungszwecken und zum Spaß.

Bisher funktioniert es soweit:
Aus einem elementaren Regulären Ausdruck (Alternativen, Konkatenation, Kleene-Stern, Klammerung und Symbole) wird mit einem rekursiv absteigenden Parser ein Syntaxbaum generiert. Anschließend wird der Syntaxbaum traversiert und es wird ein NEA (Nichtdeterministischer Endlicher Automat) generiert. Zum effizienten Erkennen der Lexeme (weil man beim Lexen sonst Potenzmengen "on-the-fly" generieren müsste) wird der NEA in einen DEA umgewandelt und zwar mittels Potenzmengenkonstruktion. Und genau da gibt es wegen der exponentiellen Laufzeit Probleme.

Etwa beim Ausdruck (a|b|c...|z|A|B|C...|Z)* für Bezeichner. (entspricht [a-zA-Z]* und ist nur der halbe Weg weil eigentlich [a-zA-Z]+ notwendig wäre, aber dann würde es Stunden dauern). Die NEA->DEA Konvertierung dauert schon dabei geschlagene 12 Minuten.

Das ist natürlich inakzeptabel und ich frage mich wie man das optimieren könnte.

Wichtig ist vielleicht wie der NEA aus dem Regulären Ausdruck generiert wird: Gemäß dem Drachenbuch mit dem McNaughton-Yamada-Thompson-Algorithmus. Der Algorithmus basiert auf induktiven Regeln. So wird für jedes Terminalsymbol ein elementarer Automat erstellt mit zwei Zuständen und nur einer Kante gemäß dem zu erkennenden Symbol. Die Konkatenation wird durch Verkettung der beiden Eingabeautomaten mit einem Epsilon-Übergang realisiert u.s.w.

Bei obigem Ausdruck mit massiver Veroderung entsteht ein derart großer NEA, dass die Potenzmengenkonstruktion einbricht.

Meine erste Idee war es, die interne Repräsentation der Übergänge in der Klasse der NEA-Zustände abzuändern. Bisher kennt jeder Zustand seine Nachfolger:

Dictionary<symbol, HashSet<NFAState>>

Das ist jetzt C# aber die Idee sollte klar sein. Ein Eingabesymbol wird auf eine Menge von Nachfolgezuständen gemappt. "symbol" ist ein struct, das eigentlich nur ein char wegkapselt und zusätzlich ein epsilon repräsentieren kann. Eben für die epsilon-Übergänge.

Wahrscheinlich sollte ich das nun abändern in etwas wie:

Dictionary<HashSet<symbol>, HashSet<NFAState>>

Damit könnten mehrere gleiche Kantenübergänge repräsentiert werden. So wäre nur ein einziger Übergang für [a-zA-Z] notwendig.

Ich bin mir nur unsicher ob das die richtige Vorgehensweise ist, v.a. weil damit viel bisher geschriebener Code geändert werden müsste und ich mir nicht ganz im Klaren darüber bin wie die Algorithmen dann zu implementieren sind.

Meinungen? Ideen? Links oder Hinweise?
Alles willkommen.

Danke fürs Lesen.

[CStoll]

Bei der Potenzmengen-Umwandlung entstehen schon prinzipbedingt recht große Automaten. Allerdings mußt du auch nicht pauschal alle Zustands-Kombinationen in den erzeugten Automaten reinpacken, sondern nur die, die auch aus dem Startzustand aus erreichbar sind. Und anschließend hast du immer noch die Möglichkeit, den entstandenen DFA zu minimieren.

[Gast]

CStoll schrieb:

Allerdings mußt du auch nicht pauschal alle Zustands-Kombinationen in den erzeugten Automaten reinpacken, sondern nur die, die auch aus dem Startzustand aus erreichbar sind.

Verstehe ich nicht ganz. Kannst Du das erläutern?
EDIT: Falls Du damit meinst, dass ich im Vorfeld alle Teilmengen generiere und speichere: Natürlich nicht.

CStoll schrieb:

Und anschließend hast du immer noch die Möglichkeit, den entstandenen DFA zu minimieren.

Das ist mir bekannt und spielt momentan keine Rolle. Zeitfressend ist die NEA->DEA-Umwandlung

[Gast]

CStoll schrieb:

Bei der Potenzmengen-Umwandlung entstehen schon prinzipbedingt recht große Automaten.

Genau dem möchte ich ja entgegen wirken durch Zusammenfassung von äquivalenten Übergängen und Zuständen. Nur weiß ich eben nicht ob das funktioniert.

EDIT: Durch abändern der internen Datenstruktur. Darauf läuft meine Frage hinaus.

[CStoll]

µ schrieb:

CStoll schrieb:

Allerdings mußt du auch nicht pauschal alle Zustands-Kombinationen in den erzeugten Automaten reinpacken, sondern nur die, die auch aus dem Startzustand aus erreichbar sind.

Verstehe ich nicht ganz. Kannst Du das erläutern?
EDIT: Falls Du damit meinst, dass ich im Vorfeld alle Teilmengen generiere und speichere: Natürlich nicht.

Du fängst an mit der Zustandsmenge {{S}} und fügst dann weitere Zustände für alle aus den bestehenden Zuständen erreichbaren Nachfolger hinzu.

Ansonsten könnte es auch ein Problem sein, daß du die selbe Zustandskombination bei deiner Umwandlung mehrfach erreichst - dann brauchst du natürlich nicht nochmal alle Nachfolger suchen.
Wie genau gehst du eigentlich vor bei der Umwandlung? Mein Ansatz wäre etwa so:

Menge<DFAZustand> offen = { {S} }
Menge<DFAZustand> untersucht = { }
while offen != { }
  DFAZustand suche = auswahl(offen) // Kriterien sind egal
  for each zeichen in Eingabemenge
    DFAZustand neu = nachfolger(suche,zeichen)
    if neu not in offen and neu not in untersucht
      insert(offen,neu)
  remove(offen,suche)
  insert(untersucht,suche)

[Gast]

Hallo CStoll,

vielen Dank für Deine Mühe.

Erstmal wie ich den Algorithmus implementiert habe. Ich wollte es eigentlich umfangreich kommentieren aber es deckt sich soweit ich das sehe mit deinem Pseudocode.

IEnumerable<char> InputSymbols = nfa.GetInputSymbols();

            //Die Epsilon-Hülle des Start-Zustands bilden
            NFAStateSet startStateSet = nfa.Start.EpsilonClosure();

            //Die Arbeitsmenge, "Open"-Set, initialisieren
            var openSet = new Stack<NFAStateSet>();
            openSet.Push(startStateSet);

            //Die Zustände des Potenzmengen-Automaten als Menge von NFAState-Mengen
            var multiStateSet = new HashSet<NFAStateSet>(new StateSetComparer());
            multiStateSet.Add(startStateSet);

            //Die Übergangsfunktion des Potenzmengen-Automaten
            var Delta = new Dictionary<KeyValuePair<char, NFAStateSet>, NFAStateSet>();

            while (openSet.Count > 0)
            {
                NFAStateSet workSet = openSet.Pop();

                foreach (char input in InputSymbols)
                {
                    //Menge der Zustände die vom aktuellen Zustand zu erreichen sind
                    NFAStateSet reachSet = NFAState.Move(workSet, input);

                    int mssCountBefore = multiStateSet.Count;
                    multiStateSet.Add(reachSet);
                    int mssCountAfter = multiStateSet.Count;

                    //Ist der Folgezustand neu oder wurde er schon besucht?
                    if (mssCountBefore != mssCountAfter)
                        openSet.Push(reachSet);

                    //Übergangsrelation wird erweitert. Das KeyValuePair dient nur als Ersatz für ein Tupel.
                    Delta.Add(new KeyValuePair<char, NFAStateSet>(input, workSet), reachSet);
                }
            }

Im Anschluß folgt die Konstruktion des DFA aus den hier ermittelten Daten.

Ok.
Nun möchte ich meine Ursprungsfrage und Idee noch einmal aufgreifen:
Ich denke nicht, dass sich daran etwas erheblich beschleunigen lässt.
Ich muss die Wurzel des Problems anpacken, nämlich die NFA-Konstruktion aus dem Regulären Ausdruck.

Meine Idee ist, Zustandsübergänge auf Implementierungsebene zusammen zu fassen.
Das heißt statt einer Abbildung in den NFA-Zuständen gemäß

Eingabesymbol -> Menge_von_Nachfolgezuständen

sollte es sowas sein

Menge_von_Eingabesymbolen -> Menge_von_Nachfolgezuständen

Damit ändert sich leider fast alles was die Algorithmen betrifft.

Die Intention ist, die Zutandsraumexplosion zu vermeiden. Wenn es um den Regulären Ausdruck eines Bezeichners geht, also [a-zA-Z]+ hätte man damit eben nicht mehr 52 veroderte Symbole die in entsprechend vielen NFA-Zuständen resultieren .... sondern nur zwei Zustände. Start, Ende und eine Kante die alle Symbole aus [a-zA-Z] matcht.

Funktioniert das? Ist das die übliche Vorgehensweise?
Ich kann mir sonst nicht erklären, wie Lexergeneratoren so effizient arbeiten.