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

24

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.

Telastyn
quelle
5
ein Erbe alter (1977) Prinzipien des Compiler-Designs ? Vor 40 Jahren war Codierstil viel anders
gnat
7
Wie würden Sie die Übergänge der DFA-Staaten umsetzen? Und was ist das mit Terminals und Nicht-Terminals? "Nicht-Terminals" bezieht sich normalerweise auf Produktionsregeln in der Grammatik, die nach einer lexikalischen Analyse kommen würden .
10
Diese Tabellen sollen für den Menschen nicht lesbar sein, sie sollen vom Compiler verwendet werden können und sehr schnell ausgeführt werden. Es ist einfach, in der Eingabe um einen Tisch herumzuspringen (z. B. um die linke Rekursion zu erfassen, obwohl in der Praxis die meisten Sprachen so aufgebaut sind, dass dies vermieden wird).
5
Wenn ein Teil Ihrer Verärgerung darauf zurückzuführen ist, dass Sie nicht wissen, wie Sie einen besseren Job machen können und nicht in der Lage sind, Feedback oder Wertschätzung für einen von Ihnen bevorzugten Ansatz zu erhalten - so wie Jahrzehnte in der Industrie uns dazu bringen, Feedback und manchmal Wertschätzung zu erwarten - vielleicht Sie sollten Ihre bessere Implementierung schreiben und an CodeReview.SE senden, um einige davon für Ihre eigene Sicherheit zu erhalten.
Jimmy Hoffa
7
Die einfache Antwort ist, dass der Lexer normalerweise als endliche Zustandsmaschine implementiert und automatisch aus der Grammatik generiert wird - und eine Zustandstabelle am einfachsten und kompaktesten als Tabelle dargestellt wird. Wie beim Objektcode ist die Tatsache, dass es für Menschen nicht einfach ist, damit zu arbeiten, irrelevant, weil Menschen nicht damit arbeiten. Sie ändern die Quelle und generieren eine neue Instanz.
Keshlam

Antworten:

16

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.

Kevin Cline
quelle
4
Ich bin nicht sicher, ob ich diesen Großhandel vorschlage. Reguläre Ausdrücke behandeln beliebige (reguläre) Sprachen. Gibt es keine besseren Ansätze für die Arbeit mit bestimmten Sprachen? Das Buch geht auf prädiktive Ansätze ein, ignoriert sie jedoch in Beispielen. Nachdem ich vor C # Jahren einen naiven Analysator gemacht hatte, fiel es mir auch nicht schwer, ihn zu warten. Ineffizient? Sicher, aber angesichts meiner damaligen Fähigkeiten nicht so schlimm.
Telastyn
1
@Telastyn: Es ist fast unmöglich, schneller zu sein als ein tabellengesteuerter DFA: Nächstes Zeichen abrufen, nächsten Status in der Übergangstabelle suchen, Status ändern. Wenn der neue Status terminal ist, geben Sie einen Token aus. In C # oder Java ist jeder Ansatz, bei dem temporäre Zeichenfolgen erstellt werden, langsamer.
Kevin Cline
@ Kevincline - sicher, aber in meinem Beispiel gibt es keine temporären Zeichenfolgen. Sogar in C wäre es nur ein Index oder ein Zeiger, der durch die Zeichenkette tritt.
Telastyn
6
@ JimmyHoffa: Ja, Leistung ist definitiv in Compilern relevant. Compiler sind schnell, weil sie auf die Hölle und zurück optimiert wurden. Keine Mikrooptimierungen, sie erledigen nur keine unnötigen Arbeiten wie das Erstellen und Verwerfen nicht benötigter temporärer Objekte. Nach meiner Erfahrung erledigt der meiste kommerzielle Textverarbeitungscode ein Zehntel der Arbeit eines modernen Compilers und benötigt dafür das Zehnfache. Die Leistung ist enorm, wenn Sie ein Gigabyte Text verarbeiten.
Kevin Cline
1
@Telastyn, welchen "besseren Ansatz" hast du dir vorgestellt und wie würdest du erwarten, dass er "besser" ist? Angesichts der Tatsache, dass wir bereits gut getestete Lexing-Tools haben, die sehr schnelle Parser erzeugen (wie andere bereits sagten, sind tabellengetriebene DFAs sehr schnell), ist es sinnvoll, sie zu verwenden. Warum sollten wir einen neuen speziellen Ansatz für eine bestimmte Sprache erfinden wollen, wenn wir nur eine Lex-Grammatik schreiben könnten? Die Lex-Grammatik ist leichter zu pflegen und der resultierende Parser ist mit größerer Wahrscheinlichkeit korrekt (wenn man bedenkt, wie gut Lex und ähnliche Tools getestet wurden).
DW
7

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.

bA
quelle
7

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.

Ben Jackson
quelle
5

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.

Ein Programmierer
quelle
2

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

Robert Baron
quelle
0

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?

Greenoldman
quelle