Bootstrapping erfordert weiterhin Unterstützung von außen

Question

Ich habe von der Idee gehört, eine Sprache zu booten, also einen Compiler/Interpreter für die Sprache selbst zu schreiben.Ich fragte mich, wie das bewerkstelligt werden könnte, schaute mich ein wenig um und sah, wie jemand sagte, dass es nur durch eines von beiden möglich sei

• Schreiben eines ersten Compilers in einer anderen Sprache.
• Manuelles Codieren eines ersten Compilers in Assembly, was wie ein Sonderfall des ersten aussieht

Für mich scheint beides nicht der Fall zu sein Bootstrapping eine Sprache in dem Sinne, dass beide Unterstützung von außen benötigen.Gibt es eine Möglichkeit, einen Compiler tatsächlich in seiner eigenen Sprache zu schreiben?

Answer 1

Gibt es eine Möglichkeit, einen Compiler tatsächlich in seiner eigenen Sprache zu schreiben?

Du haben Sie benötigen eine vorhandene Sprache, in der Sie Ihren neuen Compiler schreiben können.Wenn Sie beispielsweise einen neuen C++-Compiler schreiben würden, würden Sie ihn einfach in C++ schreiben und ihn zunächst mit einem vorhandenen Compiler kompilieren.Wenn Sie andererseits einen Compiler für eine neue Sprache erstellen würden, nennen wir ihn Yazzleof, müssten Sie den neuen Compiler zuerst in einer anderen Sprache schreiben.Im Allgemeinen wäre dies eine andere Programmiersprache, aber das muss nicht sein.Dabei kann es sich um Assemblercode oder, falls erforderlich, um Maschinencode handeln.

Wenn du war Wenn Sie einen Compiler für Yazzleof booten, würden Sie im Allgemeinen zunächst keinen Compiler für die gesamte Sprache schreiben.Stattdessen würden Sie einen Compiler für Yazzle-lite schreiben, die kleinstmögliche Teilmenge des Yazzleof (naja, a ziemlich klein zumindest eine Teilmenge).Dann würden Sie in Yazzle-lite einen Compiler für die gesamte Sprache schreiben.(Natürlich kann dies iterativ statt in einem Sprung erfolgen.) Da Yazzle-lite eine echte Teilmenge von Yazzleof ist, verfügen Sie jetzt über einen Compiler, der sich selbst kompilieren kann.

Da ist ein Wirklich Guter Artikel über das Bootstrapping eines Compilers von der niedrigstmöglichen Ebene (die auf einer modernen Maschine im Grunde ein Hex-Editor ist), mit dem Titel Bootstrapping eines einfachen Compilers aus dem Nichts.Es ist zu finden unter https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html.

Answer 2

Die Erklärung, die Sie gelesen haben, ist korrekt.Es gibt eine Diskussion darüber in Compiler:Prinzipien, Techniken und Werkzeuge (das Drachenbuch):

• Schreiben Sie einen Compiler C1 für Sprache X in Sprache Y
• Verwenden Sie den Compiler C1, um den Compiler C2 für Sprache X in Sprache X zu schreiben
• Jetzt ist C2 eine vollständig selbsthostende Umgebung.

Answer 3

Ein superinteressantes Diskussion darüber ist im Unix-Mitschöpfer Ken Thompson'S Turing-Preis Vorlesung.

Er beginnt mit:

Was ich nun beschreiben möchte, ist eines von vielen „Henne-Ei“-Problemen, die auftreten, wenn Compiler in ihrer eigenen Sprache geschrieben werden.Zur Vereinfachung verwende ich ein konkretes Beispiel aus dem C-Compiler.

und zeigt weiter, wie er eine Version des Unix-C-Compilers geschrieben hat, die es ihm immer ermöglicht, sich ohne Passwort anzumelden, da der C-Compiler das Anmeldeprogramm erkennt und speziellen Code hinzufügt.

Das zweite Muster richtet sich an den C-Compiler.Der Ersatzcode ist ein sich selbst reproduzierendes Programm der Stufe I, das beide Trojaner in den Compiler einfügt.Dies erfordert eine Lernphase wie im Beispiel der Stufe II.Zuerst kompilieren wir die geänderte Quelle mit dem normalen C-Compiler, um eine fehlerhafte Binärdatei zu erstellen.Wir installieren diese Binärdatei als offizielles C.Wir können jetzt die Fehler aus der Quelle des Compilers entfernen und die neue Binärdatei fügt die Fehler bei jeder Kompilierung wieder ein.Natürlich bleibt der Login-Befehl fehlerhaft und es gibt nirgendwo eine Spur in der Quelle.

Answer 4

Ich habe davon gehört, dass man einen äußerst eingeschränkten Compiler in einer anderen Sprache schreibt und diesen dann verwendet, um eine kompliziertere Version zu kompilieren, die in der neuen Sprache geschrieben ist.Diese zweite Version kann dann zum Kompilieren selbst und der nächsten Version verwendet werden.Bei jeder Kompilierung wird die letzte Version verwendet.

Dies ist die Definition von Bootstrapping:

der Prozess, bei dem ein einfaches System ein komplizierteres System aktiviert, das demselben Zweck dient.

BEARBEITEN:Der Wikipedia-Artikel zum Compiler-Bootstrapping deckt das Konzept besser ab als ich.

Answer 5

Schauen Sie sich den Podcast an Software Engineering Radio Folge 61 (06.07.2007), in dem die Interna des GCC-Compilers sowie der GCC-Bootstrapping-Prozess erläutert werden.

Answer 6

Donald E.Knuth tatsächlich gebaut NETZ indem Sie den Compiler darin schreiben und ihn dann manuell in Assembly- oder Maschinencode kompilieren.

Answer 7

So wie ich es verstehe, das erste Lispeln Der Bootstrapping des Interpreters erfolgte durch manuelles Kompilieren der Konstruktorfunktionen und des Token-Readers.Der Rest des Interpreters wurde dann aus der Quelle eingelesen.

Sie können es selbst überprüfen, indem Sie das Originalpapier von McCarthy lesen. Rekursive Funktionen symbolischer Ausdrücke und ihre maschinelle Berechnung, Teil I.

Answer 8

Eine andere Alternative besteht darin, eine Bytecode-Maschine für Ihre Sprache zu erstellen (oder eine vorhandene zu verwenden, wenn deren Funktionen nicht sehr ungewöhnlich sind) und einen Compiler für Bytecode zu schreiben, entweder im Bytecode oder in der gewünschten Sprache unter Verwendung eines anderen Zwischenprodukts – z Parser-Toolkit, das den AST als XML ausgibt und dann den XML-Code mithilfe von XSLT (oder einer anderen Mustervergleichssprache und baumbasierten Darstellung) in Bytecode kompiliert.Dadurch wird die Abhängigkeit von einer anderen Sprache nicht beseitigt, es könnte jedoch bedeuten, dass ein größerer Teil der Bootstrapping-Arbeit im endgültigen System landet.

Answer 9

Es ist die Informatikversion des Henne-Ei-Paradoxons.Ich kann mir keine Möglichkeit vorstellen, den ersten Compiler nicht in Assembler oder einer anderen Sprache zu schreiben.Wenn es möglich gewesen wäre, hätte Lisp es tun können.

Eigentlich denke ich, dass Lisp fast qualifiziert ist.Kasse sein Wikipedia-Eintrag.Dem Artikel zufolge könnte die Lisp-Bewertungsfunktion auf einem implementiert werden IBM 704 im Maschinencode, wobei 1962 ein vollständiger Compiler (in Lisp selbst geschrieben) entstand MIT.

Answer 10

Jedes Beispiel für das Bootstrapping einer Sprache, das mir einfällt (C, PyPy) wurde durchgeführt, nachdem es einen funktionierenden Compiler gab.Irgendwo muss man anfangen, und die Neuimplementierung einer Sprache an sich erfordert zunächst das Schreiben eines Compilers in einer anderen Sprache.

Wie sollte es sonst funktionieren?Ich glaube nicht, dass es überhaupt konzeptionell möglich ist, etwas anderes zu machen.

Answer 11

Einige Bootstrapping-Compiler oder -Systeme behalten sowohl die Quellform als auch die Objektform in ihrem Repository:

• ocaml ist eine Sprache, die sowohl über einen Bytecode-Interpreter (d. h.ein Compiler für Ocaml-Bytecode) und ein nativer Compiler (für x86-64 oder ARM usw.)Assembler).Sein SVN-Repository enthält sowohl den Quellcode (Dateien */*.{ml,mli}) und den Bytecode (Datei boot/ocamlc) Form des Compilers.Wenn Sie es also erstellen, verwenden Sie zunächst seinen Bytecode (einer früheren Version des Compilers), um sich selbst zu kompilieren.Später kann der frisch kompilierte Bytecode vom nativen Compiler kompiliert werden.Das Ocaml-SVN-Repository enthält also beides *.ml[i] Quelldateien und die boot/ocamlc Bytecode-Datei.

• Der Rost Compiler-Downloads (mit wget, Sie benötigen also eine funktionierende Internetverbindung) eine frühere Version seiner Binärdatei, um sich selbst zu kompilieren.

• SCHMELZEN ist eine Lisp-ähnliche Sprache zum Anpassen und Erweitern GCC.Es wird von einem Bootstrapping-Übersetzer in C++-Code übersetzt.Der generierte C++-Code des Übersetzers wird verteilt, sodass das SVN-Repository beides enthält *.melt Quelldateien und melt/generated/*.cc „Objekt“-Dateien des Übersetzers.

• J.Pitrat's CAIA Das System der künstlichen Intelligenz generiert sich völlig selbst.Es ist als Sammlung von Tausenden erhältlich [A-Z]*.c generierte Dateien (auch mit einer generierten dx.h Header-Datei) mit einer Sammlung von Tausenden von _[0-9]* Datei.

• Mehrere Scheme-Compiler sind ebenfalls gebootstrappt.Scheme48, Chicken Scheme, ...