Wie man einen sehr einfachen Compiler schreibt

Fortgeschrittene Compiler gcckompilieren Codes gerne in maschinenlesbare Dateien entsprechend der Sprache, in der der Code geschrieben wurde (z. B. C, C ++ usw.). Tatsächlich interpretieren sie die Bedeutung jedes Codes entsprechend der Bibliothek und den Funktionen der entsprechenden Sprachen. Korrigiere mich, wenn ich falsch liege.

Ich möchte Compiler besser verstehen, indem ich einen sehr einfachen Compiler (wahrscheinlich in C) schreibe, um eine statische Datei (z. B. Hello World in einer Textdatei) zu kompilieren. Ich habe einige Tutorials und Bücher ausprobiert, aber alle sind für praktische Fälle gedacht. Sie beschäftigen sich mit der Zusammenstellung dynamischer Codes mit Bedeutungen, die mit der entsprechenden Sprache verbunden sind.

Wie kann ich einen einfachen Compiler schreiben, um einen statischen Text in eine maschinenlesbare Datei zu konvertieren?

Der nächste Schritt besteht darin, Variablen in den Compiler einzufügen. Stellen Sie sich vor, wir möchten einen Compiler schreiben, der nur einige Funktionen einer Sprache kompiliert.

Das Einführen von praktischen Tutorials und Ressourcen wird sehr geschätzt :-)

Intro

Ein typischer Compiler führt die folgenden Schritte aus:

• Parsing: 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: Syntaktisch korrekte Aussagen aussortieren, die keinen Sinn ergeben, z. B. nicht erreichbarer Code oder doppelte Deklarationen.
• Äquivalente Transformationen und Optimierung auf hoher Ebene: Die AST wird transformiert, um eine effizientere Berechnung mit derselben Semantik darzustellen. Dies beinhaltet zB die frühe Berechnung von allgemeinen Unterausdrücken und konstanten Ausdrücken, die Beseitigung übermäßiger lokaler Zuordnungen (siehe auch SSA ) usw.
• Codegenerierung: Der AST wird mit Sprüngen, Registerzuweisung und dergleichen in linearen Low-Level-Code umgewandelt. Einige Funktionsaufrufe können zu diesem Zeitpunkt eingebunden werden, einige Schleifen können nicht eingebunden werden usw.
• Gucklochoptimierung: Der Code auf niedriger Ebene wird auf einfache lokale Ineffizienzen gescannt, die beseitigt werden.

Die meisten modernen Compiler (zum Beispiel gcc und clang) wiederholen die letzten beiden Schritte noch einmal. Sie verwenden eine einfache, aber plattformunabhängige Sprache für die anfängliche Codegenerierung. Diese Sprache wird dann in plattformspezifischen Code (x86, ARM usw.) konvertiert, der auf plattformoptimierte Weise ungefähr dasselbe tut. Dies umfasst z. B. die Verwendung von Vektoranweisungen, wenn möglich, eine Neuordnung von Anweisungen, 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 von der VM zum Zeitpunkt des Ladens vollständig dynamisch erfolgen.

Denken Sie an die Grundlagen

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

Dieser klassische Ablauf gilt für alle Softwareentwicklungen, ist aber wiederholbar.

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

Lies die Bücher!

Lies das Drachenbuch von Aho und Ullman. Dies ist klassisch und gilt auch heute noch.

Gelobt wird auch das moderne Compiler-Design .

Wenn Ihnen das gerade zu schwer fällt, lesen Sie zuerst einige Intros zum Parsen. In der Regel enthalten Analysebibliotheken Intros und Beispiele.

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

Definieren Sie Ihre Sprache gut

Verwenden Sie eine beliebige Notation, aber stellen Sie sicher, dass Sie eine vollständige und konsistente Beschreibung Ihrer Sprache haben. Dies umfasst sowohl die Syntax als auch die 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 für Sie einfachen Sprache zu schreiben. Verwenden Sie einfache Algorithmen, die Sie gut verstehen. Die erste Version muss nicht schnell, effizient oder vollständig sein. Es muss nur korrekt genug und leicht 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 durch Testfälle abgedeckt sein; effektiv wird es von ihnen definiert . Machen Sie sich mit Ihrem bevorzugten Test-Framework vertraut. Schreibe Tests vom ersten Tag an. Konzentrieren Sie sich auf "positive" Tests, die den richtigen Code akzeptieren, anstatt den falschen Code zu erkennen.

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

Erstellen Sie einen guten Parser

Parser-Generatoren gibt es viele . Wählen Sie aus, was Sie wollen. Sie können auch Ihre eigenen Parser von Grund auf neu schreiben, aber es nur wert, wenn Syntax Ihrer Sprache ist tot einfach.

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 abzulegen und sie 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 Prüfer erkennt solche Fehler, wenn er den Baum betrachtet.

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

Schreiben Sie erneut viele Testfälle und führen Sie sie aus. Trivialfälle sind bei der Fehlersuche 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 ifAnweisung) direkt in eine leicht parametrisierte Codevorlage zu übersetzen, ähnlich einer HTML-Vorlage.

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

Greifen Sie auf eine plattformunabhängige Low-Level-VM zu

Ich nehme an, dass Sie Low-Level-Inhalte ignorieren, es sei denn, Sie sind stark an hardwarespezifischen Details interessiert. Diese Details sind blutig und komplex.

Deine Optionen:

• LLVM: Ermöglicht die effiziente Generierung von Maschinencode, normalerweise für x86 und ARM.
• CLR: zielt auf .NET ab, hauptsächlich auf x86 / Windows-Basis; hat eine gute JIT.
• JVM: zielt auf eine Java-Welt ab, ist recht vielschichtig und hat eine gute JIT.

Optimierung ignorieren

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

Selbstverständlich können triviale Optimierungen eingeführt werden. Aber vermeiden Sie schlaue, haarige Sachen, bevor Ihr Compiler stabil ist.

Na und?

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

Möglicherweise lohnt es sich, eine "Hallo Welt" aus einem Programm zu sehen, das Ihr Compiler erstellt hat.

Jack Crenshaws " Let's Build a Compiler" ist eine sehr lesenswerte Einführung und Anleitung, auch wenn sie noch nicht fertig ist.

Nicklaus Wirths Compilerbau ist ein sehr gutes Lehrbuch über die Grundlagen des einfachen Compilerbaus. Er konzentriert sich auf rekursives Absteigen von oben nach unten, was, mal ehrlich, viel einfacher ist als Lex / Yacc oder Flex / Bison. Der ursprüngliche PASCAL-Compiler, den seine Gruppe geschrieben hat, wurde auf diese Weise erstellt.

Andere Leute haben die verschiedenen Drachenbücher erwähnt.

Eigentlich würde ich damit beginnen, einen Compiler für Brainfuck zu schreiben . Es ist eine ziemlich stumpfe Sprache zum Programmieren, aber es sind nur 8 Anweisungen zu implementieren. Es ist so einfach wie möglich, und es gibt äquivalente C-Anweisungen für die beteiligten Befehle, wenn Sie die Syntax als abstoßend empfinden.

Wenn Sie wirklich nur maschinenlesbaren Code schreiben möchten, der nicht auf eine virtuelle Maschine ausgerichtet ist, müssen Sie die Intel-Handbücher lesen und verstehen

• ein. Verknüpfen und Laden von ausführbarem Code

• b. COFF- und PE-Formate (für Windows), alternativ das ELF-Format (für Linux) verstehen

• c. Verstehen von .COM-Dateiformaten (einfacher als PE)
• d. Assembler verstehen
• e. Grundlegendes zu Compilern und zur Codegenerierung in Compilern.

Viel schwieriger als gesagt. Ich empfehle Ihnen, als Ausgangspunkt Compiler und Interpreter in C ++ zu lesen (Von Ronald Mak). Alternativ ist "Einen Compiler erstellen lassen" von Crenshaw in Ordnung.

Wenn Sie dies nicht möchten, können Sie auch eine eigene VM und einen auf diese VM ausgerichteten Codegenerator schreiben.

• Ein weiterer Ausgangspunkt: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Großes Buch von Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Tipps: Lernen Sie zuerst Flex und Bison. Erstellen Sie anschließend Ihren eigenen Compiler / Ihre eigene VM.

Viel Glück!

Der DIY-Ansatz für einen einfachen Compiler könnte so aussehen (zumindest sah mein Uni-Projekt so aus):

1. Definieren Sie die Grammatik der Sprache. Kontextfrei.
2. Wenn Ihre Grammatik noch nicht LL (1) ist, tun Sie es jetzt. Beachten Sie, dass einige Regeln, die in der einfachen CF-Grammatik in Ordnung waren, sich als hässlich herausstellen können. Vielleicht ist deine Sprache zu komplex ...
3. Schreiben Sie Lexer, der den Textstrom in Token (Wörter, Zahlen, Literale) zerlegt.
4. Schreiben Sie einen rekursiven Parser von oben nach unten für Ihre Grammatik, der Eingaben akzeptiert oder ablehnt.
5. Fügen Sie Ihrem Parser die Syntaxbaumgenerierung hinzu.
6. Schreiben Sie den Maschinencode-Generator aus dem Syntaxbaum.
7. Profit & Beer, alternativ können Sie überlegen, wie Sie intelligenter Parser machen oder besseren Code generieren können.

Es sollte genügend Literatur vorhanden sein, die jeden Schritt ausführlich beschreibt.