Warum sollte ein Lexer als 2D-Array und als Riesen-Switch implementiert werden?

Ich arbeite langsam daran, mein Studium zu beenden, und dieses Semester ist Compilers 101. Wir verwenden das Drachenbuch . Kurz in den Kurs und wir sprechen über die lexikalische Analyse und wie sie über deterministische endliche Automaten (im Folgenden DFA) implementiert werden kann. Richten Sie Ihre verschiedenen Lexer-Zustände ein, definieren Sie Übergänge zwischen ihnen usw.

Sowohl der Professor als auch das Buch schlagen jedoch vor, sie über Übergangstabellen zu implementieren, die sich auf ein riesiges 2D-Array belaufen (die verschiedenen Nicht-Terminal-Zustände als eine Dimension und die möglichen Eingabesymbole als die andere) und eine switch-Anweisung, um alle Terminals zu behandeln sowie Versand an die Übergangstabellen, wenn sie sich in einem nicht terminalen Zustand befinden.

Die Theorie ist in Ordnung und gut, aber als jemand, der jahrzehntelang Code geschrieben hat, ist die Implementierung abscheulich. Es ist nicht testbar, es ist nicht wartbar, es ist nicht lesbar, und es ist eineinhalb Schmerz, durch die man debuggen muss. Schlimmer noch, ich kann nicht erkennen, wie praktisch es wäre, wenn die Sprache UTF-fähig wäre. Etwa eine Million Übergangstabelleneinträge pro nicht-terminalem Zustand zu haben, wird in Eile unübersichtlich.

Also, was ist der Deal? Warum heißt es in dem endgültigen Buch zu diesem Thema so?

Ist der Aufwand für Funktionsaufrufe wirklich so hoch? Funktioniert das gut oder ist es notwendig, wenn die Grammatik nicht im Voraus bekannt ist (reguläre Ausdrücke?)? Oder vielleicht etwas, das alle Fälle behandelt, auch wenn spezifischere Lösungen für spezifischere Grammatiken besser funktionieren?

( Hinweis: Mögliches Duplikat " Warum einen OO-Ansatz anstelle einer riesigen switch-Anweisung verwenden? " ist nahe liegend, aber OO interessiert mich nicht. Ein funktionaler Ansatz oder ein noch vernünftigerer imperativer Ansatz mit eigenständigen Funktionen wäre in Ordnung.)

Betrachten Sie zum Beispiel eine Sprache, die nur Bezeichner enthält, und diese Bezeichner sind [a-zA-Z]+. In der DFA-Implementierung erhalten Sie Folgendes:

private enum State
{
    Error = -1,
    Start = 0,
    IdentifierInProgress = 1,
    IdentifierDone = 2
}

private static State[][] transition = new State[][]{
    ///* Start */                  new State[]{ State.Error, State.Error (repeat until 'A'), State.IdentifierInProgress, ...
    ///* IdentifierInProgress */   new State[]{ State.IdentifierDone, State.IdentifierDone (repeat until 'A'), State.IdentifierInProgress, ...
    ///* etc. */
};

public static string NextToken(string input, int startIndex)
{
    State currentState = State.Start;
    int currentIndex = startIndex;
    while (currentIndex < input.Length)
    {
        switch (currentState)
        {
            case State.Error:
                // Whatever, example
                throw new NotImplementedException();
            case State.IdentifierDone:
                return input.Substring(startIndex, currentIndex - startIndex);
            default:
                currentState = transition[(int)currentState][input[currentIndex]];
                currentIndex++;
                break;
        }
    }

    return String.Empty;
}

(obwohl etwas, das das Dateiende korrekt handhaben würde)

Im Vergleich zu dem, was ich erwarten würde:

public static string NextToken(string input, int startIndex)
{
    int currentIndex = startIndex;
    while (currentIndex < startIndex && IsLetter(input[currentIndex]))
    {
        currentIndex++;
    }

    return input.Substring(startIndex, currentIndex - startIndex);
}

public static bool IsLetter(char c)
{
    return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}

Wenn der Code NextTokenin seiner eigenen Funktion überarbeitet wurde, haben Sie vom Start des DFA an mehrere Ziele.

In der Praxis werden diese Tabellen aus regulären Ausdrücken generiert, die die Token der Sprache definieren:

number := [digit][digit|underscore]+
reserved_word := 'if' | 'then' | 'else' | 'for' | 'while' | ...
identifier := [letter][letter|digit|underscore]*
assignment_operator := '=' | '+=' | '-=' | '*=' | '/=' 
addition_operator := '+' | '-' 
multiplication_operator := '*' | '/' | '%'
...

Seit 1975, als Lex geschrieben wurde, haben wir Dienstprogramme zur Erstellung von Lexikalanalysatoren .

Sie schlagen grundsätzlich vor, reguläre Ausdrücke durch prozeduralen Code zu ersetzen. Dies erweitert ein paar Zeichen in einem regulären Ausdruck in mehrere Codezeilen. Handgeschriebener Verfahrenscode für die lexikalische Analyse von mäßig interessanten Sprachen ist in der Regel ineffizient und schwierig zu pflegen.

Die Motivation für den jeweiligen Algorithmus liegt hauptsächlich darin, dass es sich um eine Lernübung handelt. Daher wird versucht, der Idee eines DFA möglichst nahe zu kommen und die Zustände und Übergänge im Code sehr explizit zu halten. In der Regel würde ohnehin niemand diesen Code manuell schreiben - Sie würden ein Tool verwenden, um Code aus einer Grammatik zu generieren. Und dieses Tool würde sich nicht um die Lesbarkeit des Codes kümmern, da es sich nicht um Quellcode handelt, sondern um eine Ausgabe, die auf der Definition einer Grammatik basiert.

Ihr Code ist sauberer für jemanden, der einen handgeschriebenen DFA verwaltet, aber ein wenig weiter von den gelehrten Konzepten entfernt.

Die innere Schleife von:

                currentState = transition[(int)currentState][input[currentIndex]];
                currentIndex++;
                break;

hat viele Leistungsvorteile. Darin gibt es überhaupt keine Verzweigungen, da Sie für jedes Eingabezeichen genau dasselbe tun. Die Leistung des Compilers kann vom Lexer gesteuert werden (der auf einer Skala von jedem Zeichen der Eingabe arbeiten muss). Dies traf umso mehr zu, als das Drachenbuch geschrieben wurde.

In der Praxis muss außer CS-Schülern, die Lexer studieren, niemand diese innere Schleife implementieren (oder debuggen), da sie Teil des Boilerplates ist, das mit dem Tool zum Erstellen der transitionTabelle geliefert wird.

Aus dem Gedächtnis - es ist lange her, dass ich das Buch gelesen habe, und ich bin mir ziemlich sicher, dass ich die letzte Ausgabe nicht gelesen habe. Ich kann mich sicher nicht an etwas erinnern, das wie Java aussieht - dieser Teil wurde mit geschrieben Der Code soll eine Vorlage sein, die Tabelle wird mit einem Lex-like-Lexer-Generator gefüllt. Noch aus dem Speicher, gab es einen Abschnitt über die Tabellenkomprimierung (wieder aus dem Speicher, wurde es so geschrieben, dass es auch für tabellengesteuerte Parser anwendbar war, also vielleicht weiter im Buch als das, was Sie bisher gesehen haben). In ähnlicher Weise hat das Buch, an das ich mich erinnere, einen 8-Bit-Zeichensatz angenommen, und ich würde einen Abschnitt über den Umgang mit größeren Zeichensätzen in späteren Ausgaben erwarten, wahrscheinlich als Teil der Tabellenkomprimierung. Ich habe als Antwort auf eine SO-Frage eine alternative Möglichkeit angegeben, damit umzugehen .

Ein sicherer Leistungsvorteil besteht darin, dass die Daten in einer modernen Architektur mit engen Regelkreisen gesteuert werden: Sie sind ziemlich cachefreundlich (wenn Sie die Tabellen komprimiert haben) und die Sprungvorhersage ist so perfekt wie möglich (ein Fehler am Ende des Lexems, vielleicht einer) Fehlt für den Schalter die Zuteilung zu dem Code, der vom Symbol abhängt (dies setzt voraus, dass Ihre Tabellendekomprimierung mit vorhersehbaren Sprüngen durchgeführt werden kann). Das Verschieben dieser Zustandsmaschine in reinen Code würde die Sprungvorhersage-Leistung verringern und möglicherweise den Cache-Druck erhöhen.

Nachdem Sie das Drachenbuch bereits durchgearbeitet haben, liegt der Hauptgrund für die Verwendung von tabellengesteuerten Hebeln und Parsern darin, dass Sie reguläre Ausdrücke zum Generieren des Lexers und BNF zum Generieren des Parsers verwenden können. Das Buch beschreibt auch, wie Tools wie Lex und Yacc funktionieren und wie diese Tools funktionieren. Darüber hinaus ist es wichtig, dass Sie einige praktische Beispiele durcharbeiten.

Trotz vieler Kommentare hat es nichts mit der Art des Codes zu tun, der in den 40er, 50er, 60er Jahren geschrieben wurde zu tun, damit sie funktionieren. Es hat alles mit dem grundlegenden Verständnis zu tun, wie Compiler sowohl vom theoretischen als auch vom praktischen Standpunkt aus arbeiten.

Hoffentlich lässt Ihr Lehrer Sie auch Lex und Yacc verwenden (es sei denn, es handelt sich um eine Abschlussklasse, in der Sie Lex und Yacc schreiben können).

Spät zur Party :-) Die Token werden gegen reguläre Ausdrücke abgeglichen. Da es viele davon gibt, haben Sie die Multi-Regex-Engine, die wiederum ein riesiger DFA ist.

"Schlimmer noch, ich kann nicht sehen, wie es aus der Ferne praktisch wäre, wenn die Sprache UTF-fähig wäre."

Es ist irrelevant (oder transparent). Abgesehen davon, dass UTF schöne Eigenschaften hat, überlappen sich seine Entitäten nicht einmal teilweise. Beispielsweise wird das Byte, das das Zeichen "A" (aus der ASCII-7-Tabelle) darstellt, für kein anderes UTF-Zeichen mehr verwendet.

Sie haben also einen einzelnen DFA (der aus mehreren Regexen besteht) für das gesamte Lexer. Wie kann man es besser aufschreiben als ein 2D-Array?