Compiler-Programmierung: Was sind die wichtigsten Bestandteile?

Question

Ich bin daran interessiert, einen sehr minimalistischen Compiler zu schreiben.

Ich möchte ein kleines Stück Software (in C/C++) schreiben, das die folgenden Kriterien erfüllt:

• Ausgabe im ELF-Format (*nix)
• Eingabe ist eine einzelne Textdatei
• C-ähnliche Grammatik und Syntax
• kein Linker
• kein Präprozessor
• sehr klein (max. 1-2 KLOC)

Sprachliche Merkmale:

• native Datentypen: char, int und Floats
• Arrays (für alle nativen Datentypen)
• Variablen
• Kontrollstrukturen (if-else)
• Funktionen
• Schleifen (wäre schön)
• einfache Algebra (div, add, sub, mul, boolesche Ausdrücke, bit-shift, usw.)
• inline asm (für Systemaufrufe)

Kann mir jemand sagen, wie ich anfangen soll? Ich weiß nicht, aus welchen Teilen ein Compiler besteht (zumindest nicht in dem Sinne, dass ich einfach von der Stange anfangen könnte) und wie man sie programmiert. Ich danke Ihnen für Ihre Ideen.

Answer 1

Bei all dem, was Sie zu erreichen hoffen, dürfte die größte Herausforderung die Anforderung "sehr klein (max. 1-2 KLOC)" sein. Ich denke, dass allein Ihre erste Anforderung (Erzeugung von ELF-Ausgaben) weit über tausend Zeilen Code erfordern könnte.

Eine Möglichkeit zur Vereinfachung des Problems, zumindest für den Anfang, besteht darin, Code in Assemblertext zu erzeugen, den Sie dann in einen vorhandenen Assembler ( nasm wäre eine gute Wahl). Der Assembler würde sich um die Generierung des eigentlichen Maschinencodes kümmern, ebenso wie um den gesamten ELF-spezifischen Code, der erforderlich ist, um ein tatsächlich lauffähiges Programm zu erstellen. Dann beschränkt sich Ihre Aufgabe auf das Parsen der Sprache und die Generierung des Assemblercodes. Wenn Ihr Projekt so weit ausgereift ist, dass Sie die Abhängigkeit von einem Assembler aufheben wollen, können Sie diesen Teil selbst neu schreiben und jederzeit einfügen.

Wenn ich an Ihrer Stelle wäre, würde ich mit einem Assembler beginnen und die Teile darauf aufbauen. Der einfachste "Compiler" könnte eine Sprache mit nur wenigen sehr einfachen möglichen Anweisungen verwenden:

print "hello"
a = 5
print a

und übersetzen das in Assemblersprache. Sobald das funktioniert, kann man einen Lexer, einen Parser, einen abstrakten Syntaxbaum und einen Codegenerator erstellen, also die meisten Teile, die man für eine moderne blockstrukturierte Sprache braucht.

Viel Glück!

Answer 2

Zunächst müssen Sie entscheiden, ob Sie einen Compiler oder einen Interpreter erstellen wollen. Ein Compiler übersetzt Ihren Code in etwas, das entweder direkt auf der Hardware oder in einem Interpreter ausgeführt werden kann oder in eine andere Sprache kompiliert wird, die dann auf irgendeine Weise interpretiert wird. Beide Arten von Sprachen sind turing-vollständig, haben also die gleichen Ausdrucksmöglichkeiten. Ich würde vorschlagen, dass Sie einen Compiler erstellen, der Ihren Code entweder in .net- oder Java-Bytecode kompiliert, da Sie damit einen sehr optimierten Interpreter sowie viele Standardbibliotheken zur Verfügung haben.

Sobald Sie Ihre Entscheidung getroffen haben, sind einige allgemeine Schritte zu beachten

1. Definition der Sprache Erstens müssen Sie festlegen, wie Ihre Sprache syntaktisch aussehen soll.

2. Lexer Der zweite Schritt besteht darin, die Schlüsselwörter Ihres Codes, die so genannten Token, zu erstellen. Dabei handelt es sich um sehr einfache Elemente wie Zahlen, Additionszeichen und Zeichenketten.

3. Parsing Der nächste Schritt besteht darin, eine Grammatik zu erstellen, die Ihrer Liste von Token entspricht. Sie können Ihre Grammatik z.B. mit einer kontextfreien Grammatik definieren. Eine Reihe von Tools kann mit einer dieser Grammatiken gefüttert werden und erstellt den Parser für Sie. Normalerweise werden die geparsten Token in einem Parse-Baum organisiert. Ein Parse-Baum ist die Darstellung Ihrer Grammatik als eine Datenstruktur, in der Sie sich bewegen können.

4. Kompilieren oder Interpretieren Der letzte Schritt besteht darin, Ihren Parse-Baum mit einer Logik zu versehen. Eine einfache Möglichkeit, einen eigenen Interpreter zu erstellen, besteht darin, für jeden Knotentyp in Ihrem Baum eine Logik zu erstellen und den Baum entweder von unten nach oben oder von oben nach unten zu durchlaufen. Wenn Sie in eine andere Sprache kompilieren wollen, können Sie stattdessen die Logik für die Übersetzung des Codes in die Knoten einfügen.

Wikipedia ist großartig, um mehr zu erfahren, vielleicht möchten Sie damit beginnen aquí .

Als praxisnahe Lektüre würde ich "Programming language processors in JAVA" von David A Watt & Deryck F Brown empfehlen. Ich habe dieses Buch in meinem Compiler-Kurs verwendet, und das Lernen anhand von Beispielen ist in diesem Bereich großartig.

Answer 3

Dies sind die absolut wesentlichen Teile:

• Scanner: Dieser zerlegt die Eingabedatei in Token
• Parser: Dieser konstruiert einen abstrakten Syntaxbaum (AST) aus den vom Scanner identifizierten Token.
• Code-Erstellung: Dies erzeugt die Ausgabe aus dem AST.

Das werden Sie wahrscheinlich auch wollen:

• Fehlerbehandlung: Hier wird dem Parser mitgeteilt, was er tun soll, wenn er auf ein unerwartetes Token stößt
• Optimierung: Dadurch kann der Compiler einen effizienteren Maschinencode erzeugen

Edit: Haben Sie die Sprache bereits entworfen? Wenn nicht, sollten Sie sich auch mit dem Sprachdesign befassen.

Answer 4

Unverzichtbar ist vor allem ein Buch über das Schreiben von Compilern. Viele Leute werden Ihnen empfehlen, das "Dragon Book" von Aho et al. zu lesen, aber das beste Buch, das ich über Compiler gelesen habe, ist "Brinch Hansen on Pascal Compilers". Ich vermute, dass es vergriffen ist (Amazon ist Ihr Freund), aber es führt Sie durch alle Schritte des Entwurfs und der Erstellung eines Compilers unter Verwendung des rekursiven Abstiegs, der für Compiler-Neulinge am einfachsten zu verstehen ist.

Obwohl das Buch Pascal als Implementierungs- und Zielsprache verwendet, gelten die vorgestellten Lektionen und Techniken gleichermaßen für alle anderen Sprachen.

Answer 5

Ich weiß nicht, was Sie sich davon erhoffen, aber wenn es darum geht, etwas zu lernen, und das Betrachten von bestehendem Code für Sie funktioniert, gibt es immer tcc .