So schreiben Sie einen sehr einfachen Compiler:

Intro

Ein typischer Compiler führt die folgenden Schritte aus:

• Parsing: the 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 Anweisungen aussortieren das macht keinen Sinn, zB Nicht erreichbarer Code oder doppelte Deklarationen.
• Äquivalente Transformationen und Optimierung auf hoher Ebene: Der AST wird transformiert, um eine effizientere Berechnung mit derselben Semantik darzustellen. Dies schließt z.B. Frühzeitige Berechnung gängiger Unterausdrücke und konstanter Ausdrücke, Eliminierung übermäßiger lokaler Zuweisungen (siehe auch SSA ) usw.
• Codegenerierung: Der AST ist transformiert in linearen Low-Level-Code mit Sprüngen, Registerzuordnung und dergleichen. Einige Funktionsaufrufe können zu diesem Zeitpunkt eingebunden, einige Schleifen abgewickelt usw. werden.
• Gucklochoptimierung: Der Code auf niedriger Ebene 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. Dann wird diese Sprache in plattformspezifischen Code (x86, ARM usw.) konvertiert, der auf plattformoptimierte Weise ungefähr dasselbe tut. Dies schließt z.B. die Verwendung von Vektorbefehlen, wenn möglich, das Neuordnen von Befehlen, um die Effizienz der Verzweigungsvorhersage zu erhöhen usw.

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 dies ist an sich kein Kompilierungsschritt. In Sprachen wie Java und C # kann die Verknüpfung vollständig dynamisch sein und von der VM zum Ladezeitpunkt ausgeführt werden. P. >

Denken Sie an die Grundlagen

• Damit es funktioniert
• Machen Sie 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 das Einfachste, das möglicherweise funktionieren könnte.

Lesen Sie die Bücher!

Lesen Sie das Dragon Book von Aho und Ullman. Dies ist klassisch und gilt auch heute noch.

Modernes Compiler-Design wird ebenfalls gelobt.

Wenn Ihnen dieses Zeug momentan zu schwer fällt, lesen Sie zuerst einige Intros zum Parsen, normalerweise zum Parsen von Bibliotheken Fügen Sie Intros und Beispiele hinzu.

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

Definieren Sie Ihre Sprache gut

Verwenden Sie die gewünschte Notation, aber stellen Sie sicher, dass Sie eine vollständige und konsistente Beschreibung Ihrer haben Sprache. 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 einer anderen Sprache zu schreiben, die für Sie einfach ist.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, viel zu schreiben Anzahl der Tests

Ihre gesamte Sprache sollte von Testfällen abgedeckt werden, effektiv wird sie 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, wenn Sie einen Fehler erleiden würden. definierte Sprache, die keinen gültigen Code akzeptieren kann.

Erstellen Sie einen guten Parser

Es gibt viele Parser-Generatoren . Wählen Sie, was auch immer Sie möchten Sie können auch Ihren eigenen Parser von Grund auf neu schreiben, aber es lohnt sich nur, wenn die Syntax Ihrer Sprache absolut einfach ist.

Der Parser sollte Syntaxfehler erkennen und melden. Schreiben viele Testfälle, sowohl positive als auch negative ve; 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 von „Objektcode“, den Sie generieren. 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 ermöglicht Ihre Sprache syntaktisch korrekte Konstruktionen, die möglicherweise erstellt werden in bestimmten Zusammenhängen keinen Sinn. Ein Beispiel ist eine doppelte Deklaration derselben Variablen oder die Übergabe eines Parameters eines falschen Typs. Der Validator erkennt solche Fehler in der Baumstruktur.

Der Validator löst auch Verweise auf andere in Ihrer Sprache geschriebene Module auf, lädt diese anderen Module und verwendet sie im Validierungsprozess. In diesem Schritt wird beispielsweise sichergestellt, 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. Triviale Fä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 wie bei einer HTML-Vorlage.

Wieder , ignorieren Sie die Effizienz und konzentrieren Sie sich auf die Korrektheit.

Richten Sie sich an eine plattformunabhängige Low-Level-VM

Einzelheiten. Diese Details sind blutig und komplex.

Ihre Optionen:

• LLVM: Ermöglicht eine effiziente Generierung von Maschinencode, normalerweise für x86 und ARM.
• CLR : Ziele .NET, Multiplattform; hat eine gute JIT.
• JVM: Ziele Java-Welt, ziemlich plattformübergreifend, hat eine gute JIT.

Optimierung ignorieren

Die Optimierung ist schwierig. 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 ist jeder der Schritte möglicherweise einfacher als Sie vielleicht denken.

Das Anzeigen einer „Hallo Welt“ aus einem Programm, das Ihr Compiler erstellt hat, ist möglicherweise die Mühe wert.

Kommentare

• Dies ist eine der besten Antworten, die ich ‚ bisher gesehen habe.
• Ich denke, Sie einen Teil der Frage verpasst … Das OP wollte einen sehr einfachen Compiler schreiben. Ich denke, Sie gehen hier über das Wesentliche hinaus.
• @ marco-fiset , im Gegenteil, ich denke, es ist ‚ ist eine hervorragende Antwort, die dem OP sagt, wie man einen sehr einfachen Compiler erstellt, während es auf die Fallen hinweist, um fortgeschrittenere Phasen zu vermeiden und zu definieren.
• Dies ist eine der besten Antworten Ich habe jemals im gesamten Stack Exchange-Universum gesehen. Ein dickes Lob!
• Es könnte sich lohnen, eine ‚ Hallo Welt ‚ aus einem Programm zu sehen, das Ihr Compiler erstellt hat. – INDEED

Jack Crenshaws Lassen Sie uns einen Compiler erstellen , obwohl er noch nicht fertig ist, ist eine hervorragend lesbare Einführung und ein Tutorial.

Nicklaus Wirths Compilerkonstruktion ist ein sehr gutes Lehrbuch über die Grundlagen der einfachen Compilerkonstruktion. Er konzentriert sich auf den rekursiven Abstieg von oben nach unten, der 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.

Kommentare

• Eines der schönen Dinge an Pascal ist, dass alles definiert oder deklariert werden muss, bevor es verwendet wird. Daher kann es in einem Durchgang kompiliert werden. Turbo Pascal 3.0 ist ein solches Beispiel, und es gibt eine Menge Dokumentation zu den Interna hier .
• PASCAL wurde speziell mit one- entwickelt. Pass-Kompilierung und Verknüpfung im Auge behalten. Das Compiler-Buch von Wirth ‚ erwähnt Multipass-Compiler und fügt hinzu, dass er von einem PL / I-Compiler wusste, der 70 (ja, siebzig) Durchgänge benötigte.
• Obligatorische Deklaration vor Gebrauch stammt von ALGOL. Tony Hoare wurde vom ALGOL-Komitee die Ohren zurückgesteckt, als er vorschlug, Standardregeln hinzuzufügen, ähnlich wie bei FORTRAN. Sie wussten bereits über die Probleme Bescheid, die dadurch entstehen könnten, da typografische Fehler in Namen und Standardregeln interessante Fehler verursachen.
• Hier ist eine aktualisierte und fertiggestellte Version des Buches des ursprünglichen Autors selbst: stack.nl/~marcov/compiler.pdf Bitte bearbeiten Sie Ihre Antwort und fügen Sie diese hinzu 🙂

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

  a. Verknüpfen und Laden von ausführbarem Code

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

• c. Verstehen von .COM-Dateiformaten (einfacher als PE)
• d. Assembler verstehen
• e. Verstehen Sie die Compiler und die Codegenerierungs-Engine in Compilern.

Viel schwieriger als gesagt. Ich empfehle Ihnen, als Ausgangspunkt Compiler und Interpreter in C ++ zu lesen (Von Ronald Mak). Alternativ ist „Lasst uns einen Compiler erstellen“ von Crenshaw in Ordnung.

Wenn Sie dies nicht möchten, können Sie auch Ihre eigene VM schreiben und einen Codegenerator für diese VM schreiben.

• Ein weiterer Ausgangspunkt: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Great Book By Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Tipps: Lernen Sie zuerst Flex und Bison. Dann erstellen Sie Ihren eigenen Compiler / Ihre eigene VM.

Viel Glück!

Kommentare

• Ich denke, LLVM als Ziel und nicht Echter Maschinencode ist ungefähr der beste Weg, der heute verfügbar ist.
• Ich stimme zu, ich verfolge LLVM seit einiger Zeit und ich sollte sagen, es war eines der besten Dinge, die ich seit Jahren in Bezug auf den Programmiereraufwand gesehen habe benötigt, um es zu zielen!
• Was ist mit MIPS und verwenden Sie spim , um es auszuführen? Oder MIX ?
• @MichaelT Ich habe MIPS nicht verwendet, bin mir aber sicher, dass es gut sein wird.
• @PrototypeStark RISC-Befehlssatz, realer Prozessor, der heute noch verwendet wird (Verständnis, dass er in eingebettete Systeme übersetzt werden kann). Der vollständige Befehlssatz befindet sich unter Wikipedia . Im Internet gibt es viele Beispiele, die in vielen akademischen Klassen als Ziel für die Programmierung von Maschinensprachen verwendet werden. Bei SO ist etwas Aktivität darauf.

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

Kommentare

• Sobald Sie Ihren BF-Compiler bereit haben, müssen Sie Ihren Code darin schreiben 🙁
• @ 500-InternalServerError Verwenden Sie die C-Teilmengenmethode

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 „t LL (1)“ ist, tun Sie dies jetzt. Beachten Sie, dass einige Regeln in normaler CF in Ordnung aussahen Die Grammatik kann sich als hässlich herausstellen. Vielleicht ist Ihre Sprache zu komplex …
3. Schreiben Sie Lexer, der den Textstrom in Token (Wörter, Zahlen, Literale) zerlegt.
4. Schreiben Sie von oben nach unten rekursiver Abstiegsparser für Ihre Grammatik, der Eingaben akzeptiert oder ablehnt.
5. Fügen Sie Ihrem Parser die Generierung von Syntaxbäumen hinzu.
6. Schreiben Sie ma Chine-Code-Generator aus dem Syntaxbaum.
7. Profitieren Sie & Bier. Alternativ können Sie darüber nachdenken, wie Sie einen intelligenteren Parser erstellen oder besseren Code generieren können.

Das sollte der Fall sein reichlich Literatur, die jeden Schritt im Detail beschreibt.

Kommentare

• Der 7. Punkt ist das, worüber OP fragt.
• 1-5 sind irrelevant und verdienen dies nicht eine enge Aufmerksamkeit. 6 ist der interessanteste Teil.Leider folgen die meisten Bücher nach dem berüchtigten Drachenbuch dem gleichen Muster, wobei zu viel Wert darauf gelegt wird, Code-Transformationen zu analysieren und aus dem Rahmen zu lassen.