Schreiben eines Compilers in seiner eigenen Sprache

StackOverflow https://stackoverflow.com/questions/193560

Frage

Intuitiv würde es scheint, dass ein Compiler für Sprache Foo kann nicht selbst in Foo geschrieben werden. Genauer gesagt, kann die zuerst Compiler für Sprache Foo nicht in Foo geschrieben werden kann, aber jeder nachfolgender Compiler für Foo geschrieben werden.

Aber ist das wirklich wahr? Ich habe einige sehr vage Erinnerung an über eine Sprache zu lesen, deren erste Compiler wurde in „selbst“ geschrieben. Ist dies möglich, und wenn ja, wie?

War es hilfreich?

Lösung

Dies wird als "Bootstrapping" genannt. Sie müssen zunächst einen Compiler (oder Interpreter) für Ihre Sprache in einer anderen Sprache (in der Regel Java oder C) bauen. Sobald dies geschehen ist, können Sie eine neue Version des Compilers in Sprache Foo schreiben. Sie verwenden den ersten Bootstrap-Compiler den Compiler, zu kompilieren und dann diese kompiliert Compiler verwenden alles andere (einschließlich zukünftige Versionen von sich selbst) zu kompilieren.

Die meisten Sprachen sind in der Tat auf diese Weise geschaffen, zum Teil, weil die Sprache Designer wie die Sprache zu verwenden, sie schaffen, und auch, weil eine nicht-triviale Compiler oft als nützlicher Maßstab dient, wie „vollständig“ kann die Sprache.

Ein Beispiel hierfür wäre Scala. Sein erster Compiler wurde in Pizza, eine experimentellen Sprache, die von Martin Odersky erstellt. Ab Version 2.0 wurde der Compiler vollständig in Scala neu geschrieben. Von diesem Punkt an, könnte der alte Pizza Compiler vollständig verworfen werden, aufgrund der Tatsache, dass der neue Scala-Compiler selbst verwendet werden könnte für zukünftige Iterationen zu kompilieren.

Andere Tipps

Ich erinnere mich hören Software Engineering Radio Podcast wobei Dick Gabriel sprach über die Original-Lisp-Interpreter Bootstrapping durch eine nackte Knochen-Version in LISP Schreiben auf Papier und Hand es in Maschinencode Montage. Von da an wurde der Rest der LISP-Funktionen geschrieben in und mit LISP interpretiert.

eine Neugier auf die vorherigen Antworten Hinzufügen.

Hier ist ein Zitat aus dem Linux From Scratch Handbuch, in dem Schritt, wo man beginnt mit dem Bau der GCC-Compiler von der Quelle. (Linux From Scratch ist ein Weg, um Linux zu installieren, die von der Installation einer Verteilung radikal anders ist, dass Sie kompilieren müssen wirklich alle einziges binäres des Zielsystems.) 

make bootstrap
     

Das ‚Bootstrap‘ Ziel kompiliert GCC nicht einfach nur, sondern kompiliert gleich mehrmals. Es nutzt die kompilierte Programme in einem ersten       um sich selbst ein zweites Mal zu kompilieren, und dann wieder ein drittes Mal. Es vergleicht dann diese zweiten und dritten       kompiliert, um sicherzustellen, dass es sich einwandfrei wiedergeben kann. Dies bedeutet auch, dass es korrekt kompiliert wurde.

Diese Verwendung des ‚Bootstrap‘ Ziel wird durch die Tatsache motiviert, dass der Compiler verwendet man das Zielsystem des Werkzeugkette aufbauen kann die gleiche Version des Ziel Compiler nicht haben. Indem man in dieser Art und Weise ist sicher, ein Compiler in dem Zielsystem zu erhalten, das selbst zusammenstellen kann.

Wenn Sie Ihren ersten Compiler für C schreiben, können Sie es in einer anderen Sprache zu schreiben. Nun haben Sie einen Compiler für C in, sagen wir, Assembler. Schließlich werden Sie an den Ort kommen, wo Sie Strings analysieren müssen, und zwar Escape-Sequenzen. Sie schreiben Code \n auf das Zeichen mit dem Dezimal-Code 10 (und \r bis 13, usw.).

konvertieren

Danach Compiler fertig ist, werden Sie es in C neu zu implementieren starten Dieser Prozess wird als „ Bootstrapping “.

Der String-Parsing-Code wird werden: 

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

Wenn diese kompiliert, haben Sie eine binäre die ‚\ n‘ versteht. Das heißt, Sie können den Quellcode ändern: 

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

Also, wo ist die Information, dass '\ n' ist der Code für 13? Es ist in der binären! Es ist wie DNA: Mit dieser binären C-Quellcode kompilieren wird diese Informationen erben. Wenn der Compiler selbst kompiliert, wird es dieses Wissen an ihre Nachkommen weitergeben. Von diesem Zeitpunkt an gibt es keine Möglichkeit, von der Quelle allein zu sehen, was der Compiler tun wird.

Wenn Sie einen Virus in der Quelle für einige Programm ausblenden möchten, können Sie es dies tun: Holen Sie die Quelle eines Compilers, um die Funktion finden, die Funktionen kompiliert und ersetzen Sie es mit dieser: 

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

Die interessanten Teile A und B sind A ist der Quellcode für compileFunction das Virus einschließlich, wahrscheinlich in irgendeiner Weise verschlüsselt, so dass es von der Suche des resultierenden binären nicht offensichtlich ist. Dies stellt sicher, dass mit sich selbst Compiler kompiliert wird die Virusinjektion Code erhalten.

B ist das gleiche gilt für die Funktion, die wir mit unserem Virus ersetzt werden sollen. Zum Beispiel könnte es die Funktion „Login“ in der Quelldatei „login.c“ sein, die wahrscheinlich aus dem Linux-Kernel ist. Wir könnten es ersetzen mit einer Version, die das Passwort „joshua“ für den Root-Account zusätzlich zu dem normalen Passwort akzeptiert.

Wenn Sie das zusammenstellen und als binäres verbreiten, gibt es keine Möglichkeit, um das Virus zu finden, indem Sie an der Quelle suchen.

Die ursprüngliche Quelle der Idee: http: //cm.bell-labs .com / die / ken / trust.html

Sie können nicht einen Compiler in sich selbst schreiben, weil Sie nichts mit Ihrem Ausgangs Quellcode zu kompilieren. Es gibt zwei Ansätze, um diese zu lösen.

Die am wenigsten favorisierte ist die folgende. Sie schreiben einen minimalen Compiler in Assembler (igitt) für einen minimalen Satz von der Sprache und dann die Compiler verwenden, um zusätzliche Funktionen der Sprache umzusetzen. Bauen Sie Ihre Art und Weise, bis Sie einen Compiler mit allen Sprachfunktionen für sich selbst haben. Ein schmerzhafter Prozess, der in der Regel wird nur gemacht, wenn Sie keine andere Wahl haben.

Der bevorzugte Ansatz ist es, einen Cross-Compiler zu verwenden. ändern Sie das hintere Ende eines vorhandenen Compiler auf einer anderen Maschine Ausgabe zu erzeugen, die auf dem Zielcomputer ausgeführt wird. Dann haben Sie einen schönen vollen Compiler und arbeiten auf dem Zielcomputer. Die beliebtesten hierfür ist die C-Sprache, da es viele bestehende Compiler sind die steckbaren Backends haben, die ausgelagert werden können.

Eine wenig bekannte Tatsache ist, dass die GNU C ++ Compiler eine Implementierung hat, die nur die C Teilmenge verwendet. Der Grund, es zu sein, ist in der Regel leicht, einen C-Compiler für eine neue Zielmaschine zu finden, dass Sie die vollständige GNU C ++ Compiler es dann erstellen kann. Sie haben jetzt geschnallt selbst Boot einen C ++ Compiler auf dem Zielcomputer zu haben.

Im Allgemeinen müssen Sie eine Arbeits haben (wenn primitiver) Schnitt des Compilers ersten Arbeits - dann können Sie über die es selbst Hosting denken beginnen. Dies ist tatsächlich ein wichtiger Meilenstein in einigen langauges betrachtet.

Von dem, was ich von „mono“ erinnere, ist es wahrscheinlich, dass sie müssen ein paar Dinge Reflexion hinzufügen, um es zum Laufen zu bringen: das Mono-Team hält den Hinweis auf, dass manche Dinge einfach nicht möglich sind mit Reflection.Emit; natürlich das MS-Team könnte sie sie falsch.

Dies hat ein paar real Vorteile: es ist ein ziemlich guter Unit-Test ist, für den Anfang! Und Sie nur eine Sprache zu kümmern (das heißt, es ist möglich, ein C # Experte nicht viel C wissen könnte ++, aber jetzt kann dein den C # -Compiler beheben). Aber ich frage mich, ob es nicht eine Menge von professionellem Stolz bei der Arbeit ist hier. Sie einfach will es selbst Hosting sein

Nicht ganz einen Compiler, aber ich habe vor kurzem auf einem System gearbeitet, das selbst Hosting ist; der Code-Generator verwendet, um den Code-Generator ... also, wenn die Schemaänderungen zu erzeugen, laufe ich es einfach auf sich selbst: eine neue Version. Wenn es ein Fehler ist, gehe ich einfach wieder zu einer früheren Version und versuchen Sie es erneut. Sehr bequem und sehr einfach zu halten.

Update 1

Ich habe gerade gesehen das Video von Anders bei PDC und (ca. eine Stunde in) tut er einige viel mehr gute Gründe geben - alles über den Compiler als Dienstleistung an. Nur für das Protokoll.

Hier ist ein dump (schwieriges Thema zu suchen, auf, tatsächlich):

Dies ist auch die Idee von PyPy und Rubinius :

(Ich denke, dies auch zu Forth , aber ich don ‚t etwas über Forth wissen.)

GNAT, die GNU Ada Compiler, erfordert einen Ada-Compiler vollständig gebaut werden. Dies kann einen Schmerz sein, wenn es auf eine Plattform zu portieren, wo es keine GNAT binären leicht verfügbar.

Eigentlich sind die meisten Compiler in der Sprache geschrieben sie zusammenstellen, für die oben genannten Gründe.

Der erste Bootstrap-Compiler ist in der Regel in C, C ++ oder Assembler geschrieben.

Der Mono-Projekt C # Compiler hat „self-hosted“ für eine lange Zeit jetzt, was es bedeutet, ist, dass es in C # geschrieben wurde, selbst.

Was ich weiß, ist, dass der Compiler als reinen C-Code gestartet wurde, aber sobald die „basic“ Eigenschaften von ECMA implementiert wurden begannen sie den Compiler in C # zu schreiben.

Ich bin mir nicht bewusst, die Vorteile des Compilers in derselben Sprache zu schreiben, aber ich bin sicher, dass es zumindest mit den Merkmalen zu tun hat, die die Sprache selbst anbieten kann (C, beispielsweise nicht unterstützt Objekt orientierte Programmierung).

Sie können mehr Informationen finden hier .

Vielleicht können Sie schreiben eine BNF beschreibt BNF.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top