Gibt es echte Lexer, die NFAs direkt verwenden, anstatt sie zuerst in DFAs umzuwandeln?

7

Ich nehme an der Coursera-Klasse für Compiler teil und in der Lektion über Lexer wird angedeutet, dass es einen Zeit-Raum-Kompromiss zwischen der Verwendung eines nicht deterministischen endlichen Automaten (NFA) und eines deterministischen endlichen Automaten (DFA) zum Parsen regulärer Ausdrücke gibt. Wenn ich das richtig verstehe, besteht der Kompromiss darin, dass ein NFA kleiner ist, das Durchlaufen jedoch zeitaufwändiger ist, da alle möglichen Zustände gleichzeitig betrachtet werden müssen und daher meistens in einen DFA umgewandelt werden. Gibt es Lexer, die im "echten" Leben NFAs anstelle von DFAs verwenden, dh einen Compiler, der in der Produktion verwendet wird und nicht nur ein Proof of Concept ist?

Lucas
quelle
Anstelle von "... müssen alle möglichen Zustände berücksichtigt werden ..." heißt es, dass "... alle möglichen Übergänge berücksichtigt werden müssen ...". Dies ist exponentiell schwieriger und kann schnell größer werden als die Gesamtzahl der Staaten.
Paresh
Ich bin mir zwar nicht sicher, aber würde die Art und Weise, wie PROLOG per se analysiert, Ihren Anforderungen nicht entsprechen.
Guy Coder

Antworten:

4

Ich sehe nur zwei Anwendungen der Verwendung eines NFA (oder vielmehr seines Leistungsautomaten ohne Aufschreiben) anstelle eines minimierten DFA:

  1. Homoikonische Sprachen , in denen Sie Ihren Lexer möglicherweise häufig ändern möchten
  2. Seltsame Syntax, die Ihren DFA in die Luft jagen kann

    identifier := [a-z][a-z0-9_]*
    indices := [0-9_]{1,256} //up to 256 times
    var := identifier "_" indices | identifier
    

    Wenn Sie die letzte Regel als Vorrang nehmen, muss Ihr Lexer prüfen, ob ein Bezeichner "_" in den letzten 256 Symbolen enthält, und in diesem Fall verkürzen.

frafl
quelle
1
Wenn mir ein Sadist die zweite Sprache geben würde, würde ich das außerhalb des strengen FA behandeln. Beispielsweise erkennen C-Compiler normalerweise das /*Starten eines Kommentars und springen zum Abgleich */im C-Code. Außerdem wäre eine Sprache, die das enthält, für Menschen so gut wie unmöglich zu lesen.
vonbrand
Dies sollte kein natürliches Beispiel sein, andererseits ist es nicht so schwer zu lesen, wenn es nicht stark missbraucht wird und auch in C ein starker Missbrauch der Syntax möglich ist. Dies wie Kommentare in C (Modusschalter) zu behandeln ist nicht so einfach, da es vom Ende einer möglichen Kennung abhängt. (+1 für den "Sadisten").
Frafl
4

Kompilierte lexikalische Analysatoren kompilieren die NFA zu einem DFA.

Gut interpretierte Matcher für reguläre Ausdrücke verwenden dagegen den Thompson-Algorithmus, der die NFA mit Memoisierung simuliert. Dies entspricht dem Kompilieren des NFA zu einem DFA, aber Sie erstellen DFA-Zustände nur bei Bedarf, wenn sie benötigt werden. Bei jedem Schritt besteht Ihr deterministischer Zustand aus einer Reihe von NFA-Zuständen. Wenn Sie dann das nächste Eingabezeichen erhalten, wechseln Sie zu einer neuen Reihe von NFA-Zuständen. Sie speichern zuvor gesehene Zustände und ihre Ausgabeübergänge in einer Hash-Tabelle. Die Hash-Tabelle wird geleert, wenn sie voll ist, sie wächst nicht ohne Bindung.

Der Grund, warum Sie dies auf diese Weise tun, ist, dass die Konvertierung des NFA in DFA in der Größe des regulären Ausdrucks exponentiell dauern kann. Dies möchten Sie sicherlich nicht tun, wenn Sie den regulären Ausdruck nur einmal auswerten.

RE2 ist ein Beispiel für eine Regex-Engine, die (im Wesentlichen) den Thompson-Algorithmus verwendet. Ich kann die brillanten Blog-Beiträge des RE2-Autors Russ Cox nur empfehlen, wenn Sie mehr erfahren möchten (einschließlich vieler historischer Informationen und experimenteller Vergleiche vieler verschiedener Ansätze zur Regex-Suche).

Ich kann auch die E-Mail-Kette " Warum GNU grep schnell ist " nur empfehlen . Lektion 1 lautet: Der häufigste Fall für die Regex-Suche ist die einfache Zeichenfolgensuche.

Wanderlogik
quelle
3

Ich wäre überrascht, wenn sie es tun würden. Die Erstellung des Lexers erfolgt einmal (hoffentlich), das Ergebnis wird millionenfach verwendet (denken Sie nur daran, wie viele Token sich in Ihrer mittelgroßen Quelldatei befinden). Wenn es also keine sehr ungewöhnlichen Umstände gibt, lohnt es sich, den Lexer so schnell (und andere ressourcenschonend) wie möglich zu machen, dh einen minimalen DFA anzustreben.

vonbrand
quelle
1
Der minimale DFA kann sehr wohl exponentiell groß sein; Wenn es zu groß ist, ist das Erkunden der NFA möglicherweise sinnvoller als das Speichern des DFA. Trotzdem weiß ich nicht, dass irgendein System dies berücksichtigt.
Raphael
0

Im streng formalen Sinne nein. Nichtdeterminismus im theoretischen / mathematischen Sinne ermöglicht es einer Maschine, einen Berechnungspfad basierend darauf zu wählen, ob er schließlich zu einem akzeptierenden Zustand führt oder nicht, ohne in der Eingabe weiter nach vorne zu schauen . In diesem strengen Sinne handelt es sich also um eine Eigenschaft, die nur für theoretische Untersuchungen geeignet ist, und es gibt keine echte nicht deterministische Maschine. Insbesondere in diesem Fall können Sie keine NFA erstellen, es sei denn, Sie können in die Zukunft sehen In diesem Fall ist das Erstellen eines Compilers mit diesem Talent eine Verschwendung! ;).

Nichtdeterministisch und Nichtdeterminismus werden jedoch häufig in einem schwächeren, verschwommen definierten Sinne verwendet. Manchmal kann es randomisiert / probabilistisch bedeuten - der Algorithmus wirft eine Münze, in einer formalen Umgebung wird dies als probabilistischer / randomisierter Algorithmus untersucht und nicht als Nichtdeterminismus bezeichnet. Eine andere Verwendung ist ein Algorithmus, der bei zwei Läufen mit derselben Eingabe nicht unbedingt dieselbe Ausgabe erzeugt - er ist möglicherweise nicht zufällig, aber ein Teil seines Verhaltens ist nicht spezifiziert, sodass möglicherweise mehrere gültige Ausgaben vorliegen (ich persönlich denke dies Definition stammt aus verwirrend kommt un -determined und nicht -deterministic.

Trotzdem könnten Sie im Prinzip einen Lexer bauen, der in einem dieser schwächeren, informellen Sinne nicht deterministisch ist, aber es wäre kein NFA (das ist ein striktes formales Maschinenmodell), und ich kann mir nicht vorstellen, dass es ein Absturz sein würde heiße Idee auch - ein Lexer muss ziemlich vorhersehbar sein.

Die letzte Option besteht darin, dass Sie Nichtdeterminismus durch Backtracking oder Parallelität simulieren können. In diesem Fall verlieren Sie jedoch die offensichtliche Effizienz des Nichtdeterminismus, da Sie ihn effektiv in eine deterministische Berechnung umwandeln, sodass Sie nicht besser sind aus als mit einem DFA.

Luke Mathieson
quelle
In diesem speziellen Fall ist es durchaus möglich, alle möglichen Zustände zu verfolgen, in denen sich die NFA mit geringen Platzkosten befinden könnte, wobei im Wesentlichen ein breiter erster Durchlauf des Berechnungsbaums parallel durchgeführt wird. Keine Kristallkugel erforderlich.
vonbrand
@vonbrand, was die sinnvolle Version des Power-Sets NFA to DFA-Transformation bewirkt, also kehren wir zu einem DFA zurück.
Luke Mathieson
Das OP ist eine Umsetzungsfrage . In diesem Zusammenhang besteht der Unterschied zwischen einem DFA und einem NFA darin, dass in DFA jeder Zustand genau einen Ausgabeübergang für jedes mögliche Eingabesymbol hat. Eine NFA ist in diesem Zusammenhang eine Zustandsmaschine, bei der jeder Zustand 0, 1 oder viele Ausgangsübergänge pro Eingabesymbol haben kann und auch Übergänge zulässt . Das OP fragt, ob wir in der Praxis (deterministisch) die NFA simulieren (indem wir Sätze von Zuständen beibehalten) oder ob wir die NFA zu DFA kompilieren und dann die DFA ausführen. Ob es einen "echten" Nichtdeterminismus gibt, ist unerheblich. ϵ
Wandering Logic