Écrire un compilateur dans son propre langage

Question

Intuitivement, il semblerait qu'un compilateur de langage Foo ne peut pas lui-même être écrit en Foo. Plus précisément, le premièrement compilateur pour la langue Foo ne peut pas être écrit dans Foo, mais tout compilateur ultérieur pourrait être écrit pour Foo .

Mais est-ce vraiment vrai ? J'ai un très vague souvenir d'avoir lu quelque chose sur un langage dont le premier compilateur a été écrit en "lui-même". Est-ce possible, et si oui, comment ?

Answer 1

C'est ce qu'on appelle le "bootstrapping". Vous devez d'abord construire un compilateur (ou un interprète) pour votre langage dans un autre langage (généralement Java ou C). Une fois cela fait, vous pouvez écrire une nouvelle version du compilateur dans le langage Foo. Vous utilisez le premier compilateur d'amorçage pour compiler le compilateur, puis vous utilisez ce compilateur compilé pour compiler tout le reste (y compris les futures versions de lui-même).

La plupart des langages sont en effet créés de cette manière, en partie parce que les concepteurs de langages aiment utiliser le langage qu'ils créent, et aussi parce qu'un compilateur non trivial sert souvent de repère utile pour savoir à quel point le langage peut être "complet".

Un exemple de cela serait Scala. Son premier compilateur a été créé en Pizza, un langage expérimental de Martin Odersky. À partir de la version 2.0, le compilateur a été entièrement réécrit en Scala. À partir de ce moment-là, l'ancien compilateur Pizza pouvait être complètement abandonné, car le nouveau compilateur Scala pouvait être utilisé pour se compiler lui-même pour les itérations futures.

Answer 2

Je me souviens avoir écouté un Podcast sur le génie logiciel dans laquelle Dick Gabriel a parlé de l'amorçage de l'interpréteur LISP original en écrivant une version de base en LISP. sur papier et l'assembler manuellement en code machine. A partir de là, le reste des fonctionnalités de LISP ont été à la fois écrites et interprétées avec LISP.

Answer 3

Lorsque vous écrivez votre premier compilateur pour C, à vous de l'écrire dans une autre langue. Maintenant, vous avez un compilateur C, assembleur. Finalement, vous arriverez à l'endroit où vous avez à analyser des chaînes, plus précisément des séquences d'échappement. Vous allez écrire le code pour convertir \n pour le personnage avec le code décimal 10 (et \r - 13, etc).

Après que le compilateur est prêt, vous allez commencer à ré-écrire en C. Ce processus est appelé "l'amorçage".

La chaîne d'analyse de code sera le suivant:

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

Lors de cette compile, vous disposez d'un binaire qui comprend le '\n'. Cela signifie que vous pouvez modifier le code source:

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

Alors, où est l'information que "\n " est le code pour 13? C'est dans le binaire! C'est comme de l'ADN: la Compilation de code source C avec ce binaire hériteront de cette information. Si le compilateur compile lui-même, il va transmettre cette connaissance à sa progéniture. À partir de ce point, il n'y a pas moyen de voir à partir de la source de ce que le compilateur va faire.

Si vous voulez cacher un virus dans le source d'un programme, vous pouvez le faire comme ceci: Obtenir le code source d'un compilateur, trouver la fonction qui compile les fonctions et le remplacer par celui-ci:

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" ...
}

Les parties intéressantes sont A et B. A est le code source pour compileFunction y compris les virus, probablement cryptée, d'une certaine façon il n'est donc pas évident de la recherche sur le binaire résultant. Cela permet de s'assurer que la compilation le compilateur avec lui-même permettra de préserver le virus de l'injection de code.

B est le même pour la fonction que nous voulons remplacer notre virus. Par exemple, il pourrait être la fonction "login" dans le source du fichier "login.c" est probablement à partir du noyau Linux. On pourrait le remplacer par une version qui accepte le mot de passe "joshua" pour le compte root en plus du mot de passe.

Si vous compiler et diffuser comme un fichier binaire, il n'y aura pas moyen de trouver le virus en regardant le source.

La source d'origine de l'idée: http://cm.bell-labs.com/who/ken/trust.html

Answer 4

Ajout d'une curiosité aux réponses précédentes.

Voici une citation de la Linux From Scratch à l'étape où l'on commence à construire le compilateur GCC à partir de ses sources. (Linux From Scratch est une façon d'installer Linux qui est radicalement différente de l'installation d'une distribution, dans la mesure où vous devez compiler des fichiers vraiment très complexes. chaque binaire unique du système cible).

make bootstrap

La cible 'bootstrap' ne compile pas seulement GCC, mais le compile plusieurs fois. Elle utilise les programmes compilés dans un premier premier tour pour se compiler une deuxième fois, puis une troisième fois. Elle compare ensuite ces deuxième et troisième compilations pour s'assurer qu'il peut se reproduire sans problème. Cela implique également qu'il a été compilé correctement.

Cette utilisation de la cible "bootstrap" est motivée par le fait que le compilateur utilisé pour construire la chaîne d'outils du système cible peut ne pas avoir la même version du compilateur cible. En procédant de cette manière, on est sûr d'obtenir, dans le système cible, un compilateur qui peut se compiler lui-même.

Answer 5

Vous ne pouvez pas écrire un compilateur en soi car vous n'avez rien pour compiler votre code source de départ. Il existe deux approches pour résoudre ce problème.

Le moins favorisé est le suivant. Vous écrivez un compilateur minimal en assembleur (beurk) pour un ensemble minimal du langage, puis vous utilisez ce compilateur pour implémenter des fonctionnalités supplémentaires du langage. Vous construisez votre chemin jusqu'à ce que vous ayez un compilateur avec toutes les caractéristiques du langage pour lui-même. Un processus douloureux qui n'est généralement réalisé que lorsque vous n'avez pas d'autre choix.

La meilleure approche consiste à utiliser un compilateur croisé. Vous modifiez l'arrière-plan d'un compilateur existant sur une machine différente pour créer une sortie qui fonctionne sur la machine cible. Vous disposez alors d'un beau compilateur complet qui fonctionne sur la machine cible. Le langage C est le plus populaire pour cela, car il existe de nombreux compilateurs existants qui ont des back ends enfichables qui peuvent être échangés.

Un fait peu connu est que le compilateur GNU C++ possède une implémentation qui utilise uniquement le sous-ensemble C. La raison en est qu'il est généralement facile de trouver un compilateur C pour une nouvelle machine cible qui vous permet ensuite de construire le compilateur GNU C++ complet à partir de celui-ci. Vous vous êtes maintenant attaché à avoir un compilateur C++ sur la machine cible.