?
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.
