(Ich lerne gerade, wie man einen Compiler schreibt, also korrigiere mich bitte, wenn ich falsche Behauptungen mache)
Warum sollte jemand DFAs immer noch in Code implementieren (goto-Anweisungen, tabellengesteuerte Implementierungen), wenn sie einfach reguläre Ausdrücke verwenden können? Soweit ich weiß, nehmen lexikalische Analysatoren eine Reihe von Zeichen auf und erstellen eine Liste von Tokens, die in der Grammatikdefinition der Sprachen Terminals sind, die es ermöglichen, dass sie durch einen regulären Ausdruck beschrieben werden. Wäre es nicht einfacher, eine Reihe von Regexes zu durchlaufen, die aus der Schleife ausbrechen, wenn sie eine Übereinstimmung findet?
Sie haben absolut Recht, dass es einfacher ist, reguläre Ausdrücke zu schreiben als DFAs. Eine gute Frage ist jedoch
Wie funktionieren diese Regex-Matcher?
Die meisten sehr schnellen Implementierungen von Regex-Matchern funktionieren intern, indem sie auf einen Automatentyp (entweder einen NFA oder einen DFA mit minimalem Status) kompiliert werden. Wenn Sie einen Scanner erstellen wollten, der mit Regexes funktionierte, um zu beschreiben, welche Tokens übereinstimmen und dann alle durchgehen, könnten Sie das durchaus tun, aber intern würden sie wahrscheinlich nach DFAs kompilieren.
Es ist äußerst selten zu sehen, dass jemand tatsächlich ein DFA für Scans oder Parsing programmiert, weil es einfach so kompliziert ist. Aus diesem Grund gibt es Tools wie lex oder flex , mit denen Sie die zu vergleichenden Regexes festlegen und anschließend automatisch im Hintergrund zu DFAs kompilieren können. Auf diese Weise erhalten Sie das Beste aus beiden Welten - Sie beschreiben, was zu tun ist, indem Sie das schönere Framework für Regexes verwenden, aber Sie erhalten die Geschwindigkeit und Effizienz von DFAs hinter den Kulissen.
Ein weiteres wichtiges Detail beim Erstellen eines riesigen DFA ist, dass es möglich ist, einen einzelnen DFA zu erstellen, der mehrere parallele reguläre Ausdrücke parallel abgleicht. Dies erhöht die Effizienz, da es möglich ist, den übereinstimmenden DFA über den String so auszuführen, dass gleichzeitig nach allen möglichen Regex-Übereinstimmungen gesucht wird.
Hoffe, das hilft!
Tags und Links regex dfa compiler-construction lexical-analysis