Wie man einen sehr einfachen Compiler schreibt

214

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 :-)

Googlebot
quelle
Haben Sie Lex / Flex und Yacc / Bison ausprobiert?
Mouviciel
15
@mouviciel: Das ist kein guter Weg, um zu lernen, wie man einen Compiler erstellt. Diese Tools erledigen einen erheblichen Teil der Arbeit für Sie, so dass Sie es nie wirklich tun und lernen, wie es gemacht wird.
Mason Wheeler
11
Interessanterweise gibt der erste Ihrer Links 404 aus, während der zweite jetzt als Duplikat dieser Frage markiert ist .
Ruslan

Antworten:

326

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.

9000
quelle
45
Dies ist eine der besten Antworten, die ich bisher gesehen habe.
Gahooa
11
Ich denke, Sie haben einen Teil der Frage verpasst ... Das OP wollte einen sehr einfachen Compiler schreiben . Ich denke, Sie gehen hier über das Wesentliche hinaus.
Marco-Fiset
22
@ marco-fiset , im Gegenteil, ich denke, es ist eine hervorragende Antwort, die dem OP sagt, wie man einen sehr einfachen Compiler macht, während die Fallen aufgezeigt werden, um fortgeschrittenere Phasen zu vermeiden und zu definieren.
SMCI
6
Dies ist eine der besten Antworten, die ich jemals im gesamten Stack Exchange-Universum gesehen habe. Ein dickes Lob!
Andre Terra
3
Möglicherweise lohnt es sich, eine "Hallo Welt" aus einem Programm heraus zu sehen, das Ihr Compiler erstellt hat. - INDEED
Slier
27

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.

John R. Strohm
quelle
1
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 über die Interna hier .
Tcrosley
1
PASCAL wurde speziell für das Zusammenstellen und Verknüpfen in einem Durchgang entwickelt. Wirths Compiler-Buch erwähnt Multipass-Compiler und fügt hinzu, dass er von einem PL / I-Compiler wusste, der 70 (ja, siebzig) Durchgänge benötigte.
John R. Strohm
Die obligatorische Erklärung vor der Verwendung geht auf ALGOL zurück. Tony Hoare wurde vom ALGOL-Komitee an die Ohren geheftet, als er vorschlug, Standardtypregeln hinzuzufügen, ähnlich wie es bei FORTRAN der Fall war. Sie wussten bereits, welche Probleme dies verursachen könnte, und Tippfehler in Namen und Standardregeln führten zu interessanten Fehlern.
John R. Strohm
1
Hier ist eine aktuellere und fertigere Version des Buches vom Originalautor selbst: stack.nl/~marcov/compiler.pdf Bitte bearbeiten Sie Ihre Antwort und fügen Sie diese hinzu :)
Sonett
16

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.

Weltingenieur
quelle
7
Aber dann, wenn Sie Ihren BF-Compiler fertig haben, müssen Sie Ihren Code darin schreiben :(
500 - Internal Server Error
@ 500-InternalServerError verwendet die C-Teilmengenmethode
World Engineer
12

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.

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

Viel Glück!

Aniket Inge
quelle
7
Ich denke, dass die Ausrichtung auf LLVM und nicht auf echten Maschinencode der beste Weg ist, den es heute gibt.
9000
Ich stimme zu, ich verfolge LLVM schon seit einiger Zeit und ich sollte sagen, es war eines der besten Dinge, die ich seit Jahren in Bezug auf die Programmiereranstrengungen gesehen habe, die nötig waren, um es in Angriff zu nehmen!
Aniket Inge
2
Was ist mit MIPS und verwenden Sie Spim , um es auszuführen? Oder MIX ?
@MichaelT Ich habe MIPS nicht verwendet, aber ich bin sicher, dass es gut sein wird.
Aniket Inge
@PrototypeStark RISC-Befehlssatz, ein heute noch verwendeter Prozessor aus der realen Welt (verständlicherweise kann er in eingebettete Systeme übersetzt werden). Die vollständige Anweisungsliste finden Sie auf Wikipedia . Im Internet gibt es viele Beispiele und es wird in vielen akademischen Klassen als Ziel für die Programmierung von Maschinensprachen verwendet. Es gibt ein bisschen Aktivität auf SO .
10

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.

Beschädigen
quelle
Der 7. Punkt ist, was OP fragt.
Florian Margaine
7
1-5 sind irrelevant und verdienen keine so große Aufmerksamkeit. 6 ist der interessanteste Teil. Unglücklicherweise folgen die meisten Bücher nach dem berüchtigten Drachenbuch dem gleichen Muster und widmen dem Parsen und der Überlassung von Code-Transformationen zu viel Aufmerksamkeit.
SK-logic