Wie schreibe ich einen sehr einfachen Compiler?

Intro

Ein typischer Compiler führt die folgenden Schritte aus:

• Analyse: Der Quelltext wird in einen abstrakten Syntaxbaum (AST) konvertiert.
• Auflösung von Verweisen auf andere Module (C verschiebt diesen Schritt bis zur Verknüpfung).
• Semantische Validierung: Aussortieren syntaktisch korrekter Aussagen, die keinen Sinn ergeben, z. nicht erreichbarer Code oder doppelte Deklarationen.
• Äquivalente Transformationen und Optimierung auf hoher Ebene: Das AST wird transformiert, um eine effizientere Berechnung mit derselben Semantik darzustellen. Dazu gehört beispielsweise die frühzeitige Berechnung gemeinsamer Unterausdrücke und konstanter Ausdrücke, wodurch übermäßige lokale Zuweisungen vermieden werden (siehe auch SSA ) usw.
• Codegenerierung: Das AST wird in linearen Low-Level-Code mit Sprüngen, Registerzuordnung und dergleichen umgewandelt. Einige Funktionsaufrufe können zu diesem Zeitpunkt eingefügt werden, einige Schleifen werden abgewickelt usw.
• Gucklochoptimierung: Der Low-Level-Code wird auf einfache lokale Ineffizienzen überprüft, die beseitigt werden.

Die meisten modernen Compiler (z. B. gcc und clang) wiederholen die letzten beiden Schritte noch einmal. Sie verwenden eine mittlere, aber plattformunabhängige Sprache für die anfängliche Codegenerierung. Diese Sprache wird dann in plattformspezifischen Code (x86, ARM usw.) konvertiert, wobei auf plattformoptimierte Weise ungefähr dasselbe getan wird. Dies schließt z.B. die Verwendung von Vektorbefehlen, wenn möglich, die Neuordnung von Befehlen, um die Effizienz der Verzweigungsvorhersage zu erhöhen, und so weiter.

Danach ist der Objektcode zum Verknüpfen bereit. Die meisten Native-Code-Compiler wissen, wie man einen Linker aufruft, um eine ausführbare Datei zu erstellen, aber es ist an sich kein Kompilierungsschritt. In Sprachen wie Java und C # kann die Verknüpfung vollständig dynamisch sein, was durch die VM beim Laden) erfolgt.

Denken Sie an die Grundlagen

• Bring es zum Laufen
• Mach es schön
• Machen Sie es effizient

Diese klassische Sequenz gilt für die gesamte Softwareentwicklung, muss jedoch wiederholt werden.

Konzentrieren Sie sich auf den ersten Schritt der Sequenz. Erstellen Sie die einfachste Sache, die möglicherweise funktionieren könnte.

Lies die Bücher!

Lesen Sie das Drachenbuch von Aho und Ullman. Dies ist klassisch und gilt bis heute.

Modern Compiler Design wird ebenfalls gelobt.

Wenn Ihnen dieses Zeug momentan zu schwer fällt, lesen Sie zuerst einige Intros zum Parsen. Normalerweise enthalten Parsing-Bibliotheken Intros und Beispiele.

Stellen Sie sicher, dass Sie mit Grafiken, insbesondere Bäumen, vertraut sind. Diese Dinge sind die Dinge, aus denen Programme auf der logischen Ebene gemacht sind.

Definieren Sie Ihre Sprache gut

Verwenden Sie die gewünschte Notation, stellen Sie jedoch sicher, dass Sie eine vollständige und konsistente Beschreibung Ihrer Sprache haben. Dies umfasst sowohl Syntax als auch Semantik.

Es ist höchste Zeit, Codeausschnitte in Ihrer neuen Sprache als Testfälle für den zukünftigen Compiler zu schreiben.

Verwenden Sie Ihre Lieblingssprache

Es ist völlig in Ordnung, einen Compiler in Python oder Ruby oder in einer anderen Sprache, die für Sie einfach ist) zu schreiben. Verwenden Sie einfache Algorithmen, die Sie gut verstehen. Die erste Version hat keine Um schnell, effizient oder vollständig zu sein, muss es nur korrekt genug und einfach zu ändern sein.

Es ist auch in Ordnung, bei Bedarf verschiedene Stufen eines Compilers in verschiedenen Sprachen zu schreiben.

Bereiten Sie sich darauf vor, viele Tests zu schreiben

Ihre gesamte Sprache sollte von Testfällen abgedeckt werden. effektiv wird es von ihnen definiert . Machen Sie sich mit Ihrem bevorzugten Test-Framework vertraut. Schreiben Sie Tests vom ersten Tag an. Konzentrieren Sie sich auf "positive" Tests, die korrekten Code akzeptieren, anstatt falschen Code zu erkennen.

Führen Sie alle Tests regelmäßig durch. Beheben Sie fehlerhafte Tests, bevor Sie fortfahren. Es wäre eine Schande, eine schlecht definierte Sprache zu haben, die keinen gültigen Code akzeptieren kann.

Erstellen Sie einen guten Parser

Parser-Generatoren sind viele . Wählen Sie, was Sie wollen. Sie können auch Ihren eigenen Parser von Grund auf neu schreiben, aber es lohnt sich nur, wenn die Syntax Ihrer Sprache tot einfach ist.

Der Parser sollte Syntaxfehler erkennen und melden. Schreiben Sie viele positive und negative Testfälle. Verwenden Sie den Code, den Sie beim Definieren der Sprache geschrieben haben, erneut.

Die Ausgabe Ihres Parsers ist ein abstrakter Syntaxbaum.

Wenn Ihre Sprache Module enthält, ist die Ausgabe des Parsers möglicherweise die einfachste Darstellung des von Ihnen generierten 'Objektcodes'. Es gibt viele einfache Möglichkeiten, einen Baum in eine Datei zu kopieren und ihn schnell wieder zu laden.

Erstellen Sie einen semantischen Validator

Höchstwahrscheinlich erlaubt Ihre Sprache syntaktisch korrekte Konstruktionen, die in bestimmten Kontexten möglicherweise keinen Sinn ergeben. Ein Beispiel ist eine doppelte Deklaration derselben Variablen oder die Übergabe eines Parameters eines falschen Typs. Der Validator erkennt solche Fehler beim Betrachten des Baums.

Der Validator löst auch Verweise auf andere Module auf, die in Ihrer Sprache geschrieben sind, lädt diese anderen Module und verwendet sie im Validierungsprozess. Dieser Schritt stellt beispielsweise sicher, dass die Anzahl der Parameter, die von einem anderen Modul an eine Funktion übergeben wurden, korrekt ist.

Schreiben Sie erneut viele Testfälle und führen Sie sie aus. Trivialfälle sind bei der Fehlerbehebung ebenso unverzichtbar wie intelligent und komplex.

Code generieren

Verwenden Sie die einfachsten Techniken, die Sie kennen. Oft ist es in Ordnung, ein Sprachkonstrukt (wie eine if -Anweisung) direkt in eine leicht parametrisierte Codevorlage zu übersetzen, ähnlich einer HTML-Vorlage.

Ignorieren Sie erneut die Effizienz und konzentrieren Sie sich auf die Korrektheit.

Ziel ist eine plattformunabhängige Low-Level-VM

Ich nehme an, Sie ignorieren einfache Dinge, es sei denn, Sie interessieren sich sehr für hardwarespezifische Details. Diese Details sind blutig und komplex.

Deine Optionen:

• LLVM: Ermöglicht eine effiziente Generierung von Maschinencode, normalerweise für x86 und ARM.
• CLR: zielt auf .NET ab, hauptsächlich x86/Windows-basiert; hat eine gute JIT.
• JVM: Ziele Java Welt, ziemlich plattformübergreifend, hat eine gute JIT.

Optimierung ignorieren

Optimierung ist schwer. Fast immer ist die Optimierung verfrüht. Generieren Sie ineffizienten, aber korrekten Code. Implementieren Sie die gesamte Sprache, bevor Sie versuchen, den resultierenden Code zu optimieren.

Natürlich können triviale Optimierungen eingeführt werden. Vermeiden Sie jedoch listige, haarige Dinge, bevor Ihr Compiler stabil ist.

Na und?

Wenn Ihnen all diese Dinge nicht zu einschüchternd sind, fahren Sie bitte fort! Für eine einfache Sprache kann jeder der Schritte einfacher sein, als Sie vielleicht denken.

Es könnte sich lohnen, eine "Hallo Welt" aus einem Programm zu sehen, das Ihr Compiler erstellt hat.