Wie man einen Dolmetscher von Grund auf neu schreibt

Manche sagen, dass „alles auf Einsen und Nullen hinausläuft“ – aber verstehen wir wirklich, wie unsere Programme in diese Bits übersetzt werden?

Compiler und Interpreter nehmen beide einen rohen String, der ein Programm darstellt, parsen ihn und machen daraus einen Sinn. Obwohl Interpreter die einfacheren der beiden sind, wird es aufschlussreich sein, selbst einen sehr einfachen Interpreter zu schreiben (der nur Addition und Multiplikation durchführt). Wir konzentrieren uns auf das, was Compiler und Interpreter gemeinsam haben: Lexing und Parsen der Eingabe.

Die Dos and Don'ts beim Schreiben Ihres eigenen Dolmetschers

Leser fragen sich vielleicht, was an einer Regex falsch ist? Reguläre Ausdrücke sind leistungsfähig, aber Quellcode-Grammatiken sind nicht einfach genug, um von ihnen geparst zu werden. Beides sind keine domänenspezifischen Sprachen (DSLs), und ein Client benötigt möglicherweise beispielsweise eine benutzerdefinierte DSL für Autorisierungsausdrücke. Aber auch ohne diese Fähigkeit direkt anzuwenden, macht es das Schreiben eines Interpreters viel einfacher, den Aufwand zu schätzen, der hinter vielen Programmiersprachen, Dateiformaten und DSLs steckt.

Das korrekte Schreiben von Parsern von Hand kann mit all den Grenzfällen eine Herausforderung darstellen. Aus diesem Grund gibt es beliebte Tools wie ANTLR, die Parser für viele gängige Programmiersprachen generieren können. Es gibt auch Bibliotheken namens Parser-Kombinatoren , die es Entwicklern ermöglichen, Parser direkt in ihren bevorzugten Programmiersprachen zu schreiben. Beispiele sind FastParse für Scala und Parsec für Python.

Wir empfehlen Lesern im beruflichen Kontext, solche Tools und Bibliotheken zu verwenden, um das Rad nicht neu erfinden zu müssen. Dennoch hilft das Verständnis der Herausforderungen und Möglichkeiten, einen Interpreter von Grund auf neu zu schreiben, Entwicklern dabei, solche Lösungen effektiver zu nutzen.

Überblick über die Interpreter-Komponenten

Ein Dolmetscher ist ein komplexes Programm, daher gibt es mehrere Phasen:

1. Ein Lexer ist der Teil eines Interpreters, der eine Folge von Zeichen (Klartext) in eine Folge von Tokens umwandelt.
2. Ein Parser wiederum nimmt eine Folge von Tokens und erzeugt einen abstrakten Syntaxbaum (AST) einer Sprache. Die Regeln, nach denen ein Parser arbeitet, werden normalerweise durch eine formale Grammatik spezifiziert.
3. Ein Interpreter ist ein Programm, das den AST der Quelle eines Programms spontan interpretiert (ohne ihn vorher zu kompilieren).

Wir werden hier keinen spezifischen, integrierten Interpreter bauen. Stattdessen untersuchen wir jeden dieser Teile und ihre gemeinsamen Probleme mit separaten Beispielen. Am Ende sieht der Benutzercode so aus:

 val input = "2 * 7 + 5" val tokens = Lexer(input).lex() val ast = Parser(tokens).parse() val res = Interpreter(ast).interpret() println(s"Result is: $res")

Nach den drei Phasen erwarten wir, dass dieser Code einen endgültigen Wert berechnet und Result is: 19 . Dieses Tutorial verwendet Scala, weil es:

• Sehr prägnant, passt viel Code in einen Bildschirm.
• Ausdrucksorientiert, ohne Notwendigkeit für nicht initialisierte/Null-Variablen.
• Geben Sie sicher ein, mit einer leistungsstarken Sammlungsbibliothek, Aufzählungen und Fallklassen.

Insbesondere ist der Code hier in Scala3-Syntax mit optionalen geschweiften Klammern geschrieben (eine Python-ähnliche, auf Einrückungen basierende Syntax). Aber keiner der Ansätze ist Scala-spezifisch , und Scala ist vielen anderen Sprachen ähnlich: Leser werden es einfach finden, diese Codebeispiele in andere Sprachen zu konvertieren. Abgesehen davon können die Beispiele online mit Scastie ausgeführt werden.

Schließlich haben die Abschnitte Lexer, Parser und Interpreter unterschiedliche Beispielgrammatiken . Wie das entsprechende GitHub-Repo zeigt, ändern sich die Abhängigkeiten in späteren Beispielen geringfügig, um diese Grammatiken zu implementieren, aber die Gesamtkonzepte bleiben gleich.

Interpreter Komponente 1: Einen Lexer schreiben

Nehmen wir an, wir wollen diesen String lexieren: "123 + 45 true * false1" . Es enthält verschiedene Arten von Token:

• Ganzzahlige Literale
• A + -Operator
• Ein * -Operator
• Ein true Wort
• Ein Bezeichner, false1

Leerzeichen zwischen Token werden in diesem Beispiel übersprungen.

In diesem Stadium müssen Ausdrücke keinen Sinn ergeben; Der Lexer konvertiert einfach die Eingabezeichenfolge in eine Liste von Tokens. (Die Aufgabe, Token zu verstehen, wird dem Parser überlassen.)

Wir verwenden diesen Code, um ein Token darzustellen:

 case class Token( tpe: Token.Type, text: String, startPos: Int ) object Token: enum Type: case Num case Plus case Times case Identifier case True case False case EOF

Jedes Token hat einen Typ, eine Textdarstellung und eine Position in der ursprünglichen Eingabe. Die Position kann Endbenutzern des Lexers beim Debuggen helfen.

Das EOF Token ist ein spezielles Token, das das Ende der Eingabe markiert. Es existiert nicht im Quelltext; Wir verwenden es nur, um die Parser-Phase zu vereinfachen.

Dies wird die Ausgabe unseres Lexers sein:

 Lexing input: 123 + 45 true * false1 Tokens: List( Token(tpe = Num, text = "123", tokenStartPos = 0), Token(tpe = Plus, text = "+", tokenStartPos = 4), Token(tpe = Num, text = "45", tokenStartPos = 6), Token(tpe = True, text = "true", tokenStartPos = 9), Token(tpe = Times, text = "*", tokenStartPos = 14), Token(tpe = Identifier, text = "false1", tokenStartPos = 16), Token(tpe = EOF, text = "<EOF>", tokenStartPos = 22) )

Betrachten wir die Implementierung:

 class Lexer(input: String): def lex(): List[Token] = val tokens = mutable.ArrayBuffer.empty[Token] var currentPos = 0 while currentPos < input.length do val tokenStartPos = currentPos val lookahead = input(currentPos) if lookahead.isWhitespace then currentPos += 1 // ignore whitespace else if lookahead == '+' then currentPos += 1 tokens += Token(Type.Plus, lookahead.toString, tokenStartPos) else if lookahead == '*' then currentPos += 1 tokens += Token(Type.Times, lookahead.toString, tokenStartPos) else if lookahead.isDigit then var text = "" while currentPos < input.length && input(currentPos).isDigit do text += input(currentPos) currentPos += 1 tokens += Token(Type.Num, text, tokenStartPos) else if lookahead.isLetter then // first must be letter var text = "" while currentPos < input.length && input(currentPos).isLetterOrDigit do text += input(currentPos) currentPos += 1 val tpe = text match case "true" => Type.True // special casing literals case "false" => Type.False case _ => Type.Identifier tokens += Token(tpe, text, tokenStartPos) else error(s"Unknown character '$lookahead' at position $currentPos") tokens += Token(Type.EOF, "<EOF>", currentPos) // special end marker tokens.toList

Wir beginnen mit einer leeren Liste von Tokens, gehen dann die Zeichenfolge durch und fügen Tokens hinzu, sobald sie kommen.

Wir verwenden das Lookahead -Zeichen, um den Typ des nächsten Tokens zu bestimmen . Beachten Sie, dass das Lookahead-Zeichen nicht immer das am weitesten voraus liegende Zeichen ist, das untersucht wird. Basierend auf dem Lookahead wissen wir, wie das Token aussieht, und verwenden currentPos , um alle erwarteten Zeichen im aktuellen Token zu scannen, und fügen das Token dann der Liste hinzu:

Wenn das Lookahead ein Leerzeichen ist, überspringen wir es. Einzelbuchstaben-Token sind trivial; wir fügen sie hinzu und erhöhen den Index. Bei Ganzzahlen müssen wir uns nur um den Index kümmern.

Jetzt kommen wir zu etwas Kompliziertem: Bezeichner versus Literale. Die Regel ist, dass wir die längstmögliche Übereinstimmung nehmen und prüfen, ob es sich um ein Literal handelt; wenn nicht, ist es eine Kennung.

Seien Sie vorsichtig im Umgang mit Operatoren wie < und <= . Dort müssen Sie ein weiteres Zeichen vorausschauen und sehen, ob es = ist, bevor Sie daraus schließen, dass es sich um einen <= -Operator handelt. Ansonsten ist es nur ein < .

Damit hat unser Lexer eine Liste von Token erstellt.

Interpreter-Komponente 2: Schreiben eines Parsers

Wir müssen unseren Token eine gewisse Struktur geben – mit einer Liste allein können wir nicht viel anfangen. Wir müssen zum Beispiel wissen:

Welche Ausdrücke sind verschachtelt? Welche Operatoren werden in welcher Reihenfolge angewendet? Welche Scoping-Regeln gelten ggf.

Eine Baumstruktur unterstützt das Verschachteln und Ordnen. Aber zuerst müssen wir einige Regeln für das Konstruieren von Bäumen definieren. Wir möchten, dass unser Parser eindeutig ist – immer dieselbe Struktur für eine bestimmte Eingabe zurückgibt.

Beachten Sie, dass der folgende Parser das vorherige Lexer-Beispiel nicht verwendet . Dieser dient zum Addieren von Zahlen, daher hat seine Grammatik nur zwei Token, '+' und NUM :

 expr -> expr '+' expr expr -> NUM

Ein Äquivalent, das ein Pipe-Zeichen ( | ) als „oder“-Symbol wie in regulären Ausdrücken verwendet, ist:

 expr -> expr '+' expr | NUM

So oder so, wir haben zwei Regeln: eine, die besagt, dass wir zwei expr s summieren können, und eine andere, die besagt, dass expr ein NUM -Token sein kann, was hier eine nicht negative ganze Zahl bedeutet.

Regeln werden normalerweise mit einer formalen Grammatik spezifiziert. Eine formale Grammatik besteht aus: Den Regeln selbst, wie oben gezeigt Einer Anfangsregel (der ersten festgelegten Regel gemäß Konvention) Zwei Arten von Symbolen, mit denen die Regeln definiert werden: Terminals: die „Buchstaben“ (und andere Zeichen) unserer Sprache— die irreduziblen Symbole, aus denen Token bestehen Nonterminals: Zwischenkonstrukte, die zum Parsen verwendet werden (dh Symbole, die ersetzt werden können)

Nur ein Nichtterminal kann auf der linken Seite einer Regel stehen; die rechte Seite kann sowohl Terminals als auch Nichtterminals haben. Im obigen Beispiel sind die Terminals '+' und NUM , und das einzige Nichtterminal ist expr . Als breiteres Beispiel haben wir in der Java-Sprache Terminals wie 'true' , '+' , Identifier und '[' , und Nonterminals wie BlockStatements , ClassBody und MethodOrFieldDecl .

Es gibt viele Möglichkeiten, wie wir diesen Parser implementieren könnten. Hier verwenden wir eine Parsing-Technik mit „rekursivem Abstieg“. Dies ist der häufigste Typ, da er am einfachsten zu verstehen und zu implementieren ist.

Ein rekursiver Abstiegsparser verwendet eine Funktion für jedes Nichtterminal in der Grammatik. Es beginnt mit der Startregel und geht von dort nach unten (daher „Abstieg“), um herauszufinden, welche Regel in jeder Funktion anzuwenden ist. Der „rekursive“ Teil ist entscheidend, weil wir Nichtterminale rekursiv verschachteln können! Regexes können das nicht: Sie können nicht einmal mit ausgeglichenen Klammern umgehen. Wir brauchen also ein leistungsfähigeres Werkzeug.

Ein Parser für die erste Regel würde etwa so aussehen (vollständiger Code):

 def expr() = expr() eat('+') expr()

Die Funktion eat() prüft, ob der Lookahead mit dem erwarteten Token übereinstimmt und verschiebt dann den Lookahead-Index. Leider funktioniert das noch nicht, da wir einige Probleme mit unserer Grammatik beheben müssen.

Grammatik Mehrdeutigkeit

Das erste Problem ist die Mehrdeutigkeit unserer Grammatik, die vielleicht nicht auf den ersten Blick ersichtlich ist:

 expr -> expr '+' expr | NUM

Angesichts der Eingabe 1 + 2 + 3 könnte unser Parser wählen, ob er zuerst den linken expr oder den rechten expr im resultierenden AST berechnen möchte:

Deshalb müssen wir etwas Asymmetrie einführen:

 expr -> expr '+' NUM | NUM

Die Menge der Ausdrücke, die wir mit dieser Grammatik darstellen können, hat sich seit ihrer ersten Version nicht geändert. Erst jetzt ist eindeutig : Der Parser geht immer nach links. Genau das, was wir brauchten!

Dadurch wird unsere + -Operation left assoziative , aber dies wird deutlich, wenn wir zum Abschnitt Interpreter kommen.

Linksrekursive Regeln

Leider löst der obige Fix unser anderes Problem nicht, die linke Rekursion:

 def expr() = expr() eat('+') eat(NUM)

Wir haben hier unendliche Rekursion . Wenn wir in diese Funktion einsteigen würden, würden wir schließlich einen Stack-Overflow-Fehler erhalten. Aber Parsing-Theorie kann helfen!

Angenommen, wir haben eine Grammatik wie diese, bei der alpha eine beliebige Folge von Terminals und Nichtterminals sein könnte:

 A -> A alpha | B

Wir können diese Grammatik umschreiben als:

 A -> BA' A' -> alpha A' | epsilon

Dort ist epsilon ein leerer String – nichts, kein Token.

Nehmen wir die aktuelle Überarbeitung unserer Grammatik:

 expr -> expr '+' NUM | NUM

Nach der oben beschriebenen Methode zum Umschreiben von Parsing-Regeln, wobei alpha unsere '+' NUM Token ist, wird unsere Grammatik zu:

 expr -> NUM exprOpt exprOpt -> '+' NUM exprOpt | epsilon

Jetzt ist die Grammatik in Ordnung und wir können sie mit einem rekursiven Abstiegsparser parsen. Mal sehen, wie ein solcher Parser für diese neueste Iteration unserer Grammatik aussehen würde:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Unit = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") private def expr(): Unit = eat(Type.Num) exprOpt() private def exprOpt(): Unit = if lookahead.tpe == Type.Plus then eat(Type.Plus) eat(Type.Num) exprOpt() // else: end recursion, epsilon private def eat(tpe: Type): Unit = if lookahead.tpe != tpe then error(s"Expected: $tpe, got: ${lookahead.tpe} at position ${lookahead.startPos}") tokens = tokens.tail lookahead = tokens.head

Hier verwenden wir das EOF Token, um unseren Parser zu vereinfachen. Wir sind uns immer sicher, dass sich mindestens ein Token in unserer Liste befindet, sodass wir den Sonderfall einer leeren Liste nicht behandeln müssen.

Wenn wir zu einem Streaming-Lexer wechseln, hätten wir keine In-Memory-Liste, sondern einen Iterator, also brauchen wir eine Markierung, um zu wissen, wann wir am Ende der Eingabe angelangt sind. Wenn wir zum Ende kommen, sollte das EOF Token das letzte verbleibende Token sein.

Wenn wir den Code durchgehen, können wir sehen, dass ein Ausdruck nur eine Zahl sein kann. Wenn nichts mehr übrig ist, wäre das nächste Token kein Plus , also würden wir mit dem Parsen aufhören. Das letzte Token wäre EOF und wir wären fertig.

Wenn der Eingabestring mehr Token hat, müssten diese wie + 123 aussehen. Hier setzt die Rekursion auf exprOpt() an!

Generieren eines AST

Jetzt, da wir unseren Ausdruck erfolgreich geparst haben, ist es schwierig, irgendetwas damit zu tun, so wie es ist. Wir könnten einige Rückrufe in unseren Parser einbauen, aber das wäre sehr umständlich und unlesbar. Stattdessen geben wir einen AST zurück, einen Baum, der den Eingabeausdruck darstellt:

 case class Expr(num: Int, exprOpt: ExprOpt) enum ExprOpt: case Opt(num: Int, exprOpt: ExprOpt) case Epsilon

Dies ähnelt unseren Regeln, die einfache Datenklassen verwenden.

Unser Parser gibt nun eine nützliche Datenstruktur zurück:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Expr = val res = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") else res private def expr(): Expr = val num = eat(Type.Num) Expr(num.text.toInt, exprOpt()) private def exprOpt(): ExprOpt = if lookahead.tpe == Type.Plus then eat(Type.Plus) val num = eat(Type.Num) ExprOpt.Opt(num.text.toInt, exprOpt()) else ExprOpt.Epsilon

Informationen zu eat() , error() und anderen Implementierungsdetails finden Sie im begleitenden GitHub-Repository.

Regeln vereinfachen

Unser ExprOpt kann noch verbessert werden:

 '+' NUM exprOpt | epsilon

Es ist schwer, das Muster zu erkennen, das es in unserer Grammatik darstellt, wenn man es nur betrachtet. Es stellt sich heraus, dass wir diese Rekursion durch ein einfacheres Konstrukt ersetzen können:

 ('+' NUM)*

Dieses Konstrukt bedeutet einfach, dass '+' NUM null oder mehrmals vorkommt.

Jetzt sieht unsere vollständige Grammatik so aus:

 expr -> NUM exprOpt* exprOpt -> '+' NUM

Und unser AST sieht schöner aus:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(num: Int)

Der resultierende Parser hat die gleiche Länge, ist aber einfacher zu verstehen und zu verwenden. Wir haben Epsilon eliminiert, was jetzt impliziert wird, indem wir mit einer leeren Struktur beginnen.

Wir brauchten hier nicht einmal die Klasse ExprOpt . Wir hätten einfach case class Expr(num: Int, exprOpts: Seq[Int]) oder im Grammatikformat NUM ('+' NUM)* setzen können. Warum haben wir es nicht getan?

Bedenken Sie, wenn wir mehrere mögliche Operatoren wie - oder * hätten, dann hätten wir eine Grammatik wie diese:

 expr -> NUM exprOpt* exprOpt -> [+-*] NUM

In diesem Fall benötigt der AST dann ExprOpt , um den Operatortyp aufzunehmen:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: String, num: Int)

Beachten Sie, dass die [+-*] Syntax in der Grammatik dasselbe bedeutet wie in regulären Ausdrücken: „eines dieser drei Zeichen“. Wir werden dies bald in Aktion sehen.

Interpreter Komponente 3: Einen Interpreter schreiben

Unser Interpreter verwendet unseren Lexer und Parser, um die AST unseres Eingabeausdrucks zu erhalten, und wertet diese AST dann auf die von uns gewünschte Weise aus. In diesem Fall haben wir es mit Zahlen zu tun, und wir wollen ihre Summe auswerten.

Bei der Implementierung unseres Interpreter-Beispiels verwenden wir diese einfache Grammatik:

 expr -> NUM exprOpt* exprOpt -> [+-] NUM

Und diese AST:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: Token.Type, num: Int)

(Wir haben behandelt, wie man einen Lexer und einen Parser für ähnliche Grammatiken implementiert, aber jeder Leser, der nicht weiterkommt, kann die Lexer- und Parser-Implementierungen für genau diese Grammatik im Repo durchsehen.)

Jetzt werden wir sehen, wie man einen Interpreter für die obige Grammatik schreibt:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = expr.num expr.exprOpts.foreach { exprOpt => if exprOpt.op == Token.Type.Plus then tmp += exprOpt.num else tmp -= exprOpt.num } tmp

Wenn wir unsere Eingabe in einen AST geparst haben, ohne auf einen Fehler zu stoßen, sind wir sicher, dass wir immer mindestens eine NUM haben werden. Dann nehmen wir die optionalen Zahlen und addieren sie zu unserem Ergebnis (oder subtrahieren sie davon).

Der eingangs erwähnte Hinweis zur Linksassoziativität von + ist nun klar: Wir beginnen mit der ganz linken Zahl und fügen weitere hinzu, von links nach rechts. Dies mag für die Addition unwichtig erscheinen, aber denken Sie an die Subtraktion: Der Ausdruck 5 - 2 - 1 wird als (5 - 2) - 1 = 3 - 1 = 2 ausgewertet und nicht als 5 - (2 - 1) = 5 - 1 = 4 !

Aber wenn wir über die Interpretation von Plus- und Minus-Operatoren hinausgehen wollen, müssen wir eine weitere Regel definieren.

Vorrang

Wir wissen, wie man einen einfachen Ausdruck wie 1 + 2 + 3 analysiert, aber wenn es um 2 + 3 * 4 + 5 geht, haben wir ein kleines Problem.

Die meisten Menschen stimmen der Konvention zu, dass die Multiplikation Vorrang vor der Addition hat. Aber das weiß der Parser nicht. Wir können es nicht einfach als ((2 + 3) * 4) + 5 auswerten. Stattdessen wollen wir (2 + (3 * 4)) + 5 .

Das bedeutet, dass wir zuerst die Multiplikation auswerten müssen. Die Multiplikation muss weiter von der Wurzel des AST entfernt sein, um zu erzwingen, dass sie vor der Addition ausgewertet wird. Dazu müssen wir noch eine weitere Ebene der Indirektion einführen.

Korrigieren einer naiven Grammatik von Anfang bis Ende

Dies ist unsere ursprüngliche, linksrekursive Grammatik, die keine Vorrangregeln hat:

 expr -> expr '+' expr | expr '*' expr | NUM

Zuerst geben wir ihm Vorrangregeln und entfernen seine Mehrdeutigkeit :

 expr -> expr '+' term | term term -> term '*' NUM | NUM

Dann bekommt es nicht-links-rekursive Regeln :

 expr -> term exprOpt* exprOpt -> '+' term term -> NUM termOpt* termOpt -> '*' NUM

Das Ergebnis ist ein wunderschön ausdrucksstarkes AST:

 case class Expr(term: Term, exprOpts: Seq[ExprOpt]) case class ExprOpt(term: Term) case class Term(num: Int, termOpts: Seq[TermOpt]) case class TermOpt(num: Int)

Dies lässt uns mit einer prägnanten Interpreter-Implementierung zurück:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = eval(expr.term) expr.exprOpts.foreach { exprOpt => tmp += eval(exprOpt.term) } tmp private def eval(term: Term): Int = var tmp = term.num term.termOpts.foreach { termOpt => tmp *= termOpt.num } tmp

Wie zuvor wurden die Ideen in der erforderlichen Lexik und Grammatik früher behandelt, aber die Leser können sie bei Bedarf im Repo finden.

Nächste Schritte beim Schreiben von Dolmetschern

Wir haben dies nicht behandelt, aber die Fehlerbehandlung und -berichterstattung sind entscheidende Merkmale eines jeden Parsers. Als Entwickler wissen wir, wie frustrierend es sein kann, wenn ein Compiler verwirrende oder irreführende Fehler produziert. Es ist ein Bereich, der viele interessante Probleme zu lösen hat, wie z. B. das Ausgeben korrekter und präziser Fehlermeldungen, das Abschrecken des Benutzers nicht mit mehr Meldungen als nötig und die ordnungsgemäße Wiederherstellung nach Fehlern. Es liegt an den Entwicklern, einen Interpreter oder Compiler zu schreiben, um sicherzustellen, dass ihre zukünftigen Benutzer eine bessere Erfahrung machen.

Beim Durchgehen unserer Beispiel-Lexer, -Parser und -Interpreter haben wir nur an der Oberfläche der Theorien hinter Compilern und Interpretern gekratzt, die Themen abdecken wie:

• Bereiche und Symboltabellen
• Statische Typen
• Optimierung der Kompilierzeit
• Statische Programmanalysatoren und Linters
• Codeformatierung und hübsches Drucken
• Domänenspezifische Sprachen

Zur weiteren Lektüre empfehle ich diese Quellen:

• Sprachimplementierungsmuster von Terence Parr
• Ein kostenloses Online-Buch, Crafting Interpreters , von Bob Nystrom
• Einführung in Grammatiken und Parsing von Paul Klint
• Gute Compiler-Fehlermeldungen schreiben von Caleb Meredith
• Die Notizen aus dem Kurs „Program Translation and Compiling“ der East Carolina University