it-swarm-eu.dev

Wie schreibe ich einen sehr einfachen Compiler?

Fortgeschrittene Compiler wie gcc kompilieren Codes in maschinenlesbare Dateien gemäß 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 zu kompilieren (z. B. Hello World in einer Textdatei). Ich habe einige Tutorials und Bücher ausprobiert, aber alle sind für praktische Fälle. Sie befassen sich mit dem Kompilieren 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ühren. Stellen Sie sich vor, wir möchten einen Compiler schreiben, der nur einige Funktionen einer Sprache kompiliert.

Die Einführung in praktische Tutorials und Ressourcen wird sehr geschätzt :-)

229
Googlebot

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.

335
9000

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

Nicklaus Wirths Compiler Construction ist ein sehr gutes Lehrbuch über die Grundlagen der einfachen Compiler-Konstruktion. 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.

29
John R. Strohm

Ich würde eigentlich damit beginnen, einen Compiler für Brainfuck zu schreiben. Es ist eine ziemlich stumpfe Sprache zum Programmieren, aber es müssen nur 8 Anweisungen implementiert werden. 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.

15
World Engineer

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 ELF-Format (für Linux)

  • c. Verstehen von .COM-Dateiformaten (einfacher als PE)
  • d. Versteher verstehen
  • e. Verstehen von Compilern und Codegenerierungs-Engines in Compilern.

Viel schwerer gemacht 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 Ihr eigenes VM] schreiben und einen Codegenerator schreiben, der auf diese VM ausgerichtet ist.

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

Viel Glück!

12
Aniket Inge

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 aussahen, 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 Top-Down-Parser für rekursiven Abstieg für Ihre Grammatik, der Eingaben akzeptiert oder ablehnt.
  5. Fügen Sie Ihrem Parser die Generierung von Syntaxbäumen hinzu.
  6. Schreiben Sie den Maschinencodegenerator aus dem Syntaxbaum.
  7. Profit & Beer, alternativ können Sie darüber nachdenken, wie Sie einen intelligenteren Parser erstellen oder besseren Code generieren können.

Es sollte genügend Literatur geben, die jeden Schritt im Detail beschreibt.

10
MaR