Écrire un compilateur dans sa propre langue

https://stackoverflow.com/questions/193560

10-07-2019
|

Question

Intuitivement, il semblerait qu'un compilateur du langage Foo ne puisse pas être lui-même écrit en Foo. Plus spécifiquement, le compilateur premier du langage Foo ne peut pas être écrit en Foo, mais tout compilateur ultérieur pourrait être écrit pour Foo .

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

La solution

Cela s'appelle "amorçage". Vous devez d’abord créer un compilateur (ou un interpréteur) 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 en langage Foo. Vous utilisez le premier compilateur d'amorçage pour compiler le compilateur, puis ce compilateur compilé pour tout compiler, y compris les versions futures de celui-ci.

La plupart des langues sont en effet créées de cette façon, en partie parce que les concepteurs de langages aiment utiliser le langage qu’ils créent, mais aussi parce qu’un compilateur non trivial sert souvent de repère utile pour savoir comment "compléter" la langue peut être.

Un exemple de ceci serait Scala. Son premier compilateur a été créé dans Pizza, un langage expérimental de Martin Odersky. Depuis la version 2.0, le compilateur a été complètement ré-écrit en Scala. À partir de ce moment, l’ancien compilateur Pizza pourrait être complètement jeté, car le nouveau compilateur Scala pourrait être utilisé pour se compiler lui-même pour de futures itérations.

Autres conseils

Je me souviens d'avoir écouté un Génie logiciel Podcast radio dans lequel Dick Gabriel a expliqué comment amorcer l’interprète LISP original en écrivant une version sans système d’affichage dans LISP sur papier et en l’assemblant à la main dans du code machine. À partir de ce moment, les autres fonctionnalités de LISP ont été écrites et interprétées avec LISP.

Ajouter une curiosité aux réponses précédentes.

Voici une citation du manuel Linux From Scratch , à l'étape de la création du compilateur GCC. de sa source. (Linux From Scratch est un moyen d'installer Linux radicalement différent de l'installation d'une distribution, en ce sens que vous devez compiler réellement tous les binaires du système cible).

make bootstrap
La cible 'bootstrap' ne compile pas simplement GCC, mais la compile plusieurs fois. Il utilise les programmes compilés dans une première rond pour se compiler une deuxième fois, puis une troisième fois. Il compare ensuite ces deuxième et troisième compile pour s’assurer qu’il peut se reproduire parfaitement. 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 créer la chaîne d'outils du système cible peut ne pas avoir la même version du compilateur cible. En procédant ainsi, on est sûr d’obtenir, dans le système cible, un compilateur capable de se compiler lui-même.

Lorsque vous écrivez votre premier compilateur pour C, vous l'écrivez dans un autre langage. Maintenant, vous avez un compilateur pour C dans, par exemple, l'assembleur. Finalement, vous arriverez à l'endroit où vous devez analyser des chaînes, en particulier des séquences d'échappement. Vous écrirez le code pour convertir \ n en caractère avec le code décimal 10 (et \ r en 13, etc.).

Une fois que le compilateur est prêt, vous allez commencer à le réimplémenter en C. Ce processus s'appelle " amorce ".

Le code d'analyse de chaîne deviendra:

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

Lorsque ceci est compilé, vous avez un binaire qui comprend '\ n'. Cela signifie que vous pouvez changer le code source:

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

Où se trouve l’information selon laquelle "\ n" correspond au code 13? C'est dans le binaire! C'est comme l'ADN: Compiler le code source C avec ce binaire héritera de cette information. Si le compilateur se compile lui-même, il transmettra cette connaissance à sa progéniture. À partir de ce moment, il n'y a aucun moyen de voir à partir du code source ce que le compilateur fera.

Si vous souhaitez masquer un virus dans le code source d'un programme, procédez comme suit: Obtenez le source d'un compilateur, recherchez la fonction qui compile les fonctions et remplacez-le 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 de compileFunction , y compris le virus, probablement chiffré de sorte que la recherche du fichier binaire ne semble pas évidente. Cela garantit que la compilation vers le compilateur avec lui-même préservera le code d'injection de virus.

B est identique pour la fonction que nous souhaitons remplacer par notre virus. Par exemple, il pourrait s’agir de la fonction " login " dans le fichier source " login.c " qui provient probablement du noyau Linux. Nous pourrions le remplacer par une version qui acceptera le mot de passe " joshua " pour le compte root en plus du mot de passe normal.

Si vous le compilez et le diffusez sous forme de fichier binaire, il sera impossible de trouver le virus en regardant la source.

Source originale de l'idée: http: //cm.bell-labs .com / who / ken / trust.html

Vous ne pouvez pas écrire un compilateur en lui-même 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 dans l'assembleur (beurk) pour un ensemble minimal du langage, puis utilisez ce compilateur pour implémenter des fonctionnalités supplémentaires du langage. Construisez votre chemin jusqu’à ce que vous ayez un compilateur avec toutes les fonctionnalités du langage. Un processus douloureux qui ne se fait généralement que lorsque vous n'avez pas d'autre choix.

L’approche recommandée consiste à utiliser un compilateur croisé. Vous modifiez le back-end d'un compilateur existant sur un autre ordinateur pour créer une sortie qui s'exécute sur l'ordinateur cible. Ensuite, vous avez un bon compilateur complet qui travaille sur la machine cible. Le langage C le plus populaire est le langage C, car il existe de nombreux compilateurs dont les extrémités sont connectables et qui peuvent être remplacées.

Un fait peu connu est que le compilateur GNU C ++ a 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, ce qui vous permet ensuite de construire le compilateur GNU C ++ complet à partir de celui-ci. Vous avez maintenant démarré vous-même avec un compilateur C ++ sur la machine cible.

En règle générale, vous devez commencer par utiliser une version fonctionnelle du compilateur (si elle est primative). Vous pourrez alors commencer à penser à l’auto-hébergement. Ceci est en fait considéré comme une étape importante dans certaines langues.

D'après ce que je me souviens de "mono", il est probable qu'ils auront besoin d'ajouter quelques éléments à la réflexion pour que cela fonctionne: l'équipe mono continue de souligner que certaines choses ne sont tout simplement pas possibles avec Reflection .Emettre ; bien sûr, l’équipe MS pourrait leur prouver le contraire.

Cela présente quelques réels avantages: c’est un assez bon test unitaire, pour commencer! Et vous n’avez qu’un seul langage qui vous préoccupe (c’est-à-dire qu’il est possible qu’un expert en C # ne connaisse pas beaucoup le C ++; mais à présent, il peut réparer le compilateur C #). Mais je me demande s’il n’ya pas beaucoup de fierté professionnelle au travail ici: ils veulent simplement que ce soit un site autonome.

Ce n’est pas vraiment un compilateur, mais j’ai récemment travaillé sur un système qui s’auto-héberge; le générateur de code est utilisé pour générer le générateur de code ... donc si le schéma change, je l'exécute simplement sur lui-même: nouvelle version. S'il y a un bogue, je reviens à une version antérieure et réessaie. Très pratique et très facile à entretenir.

Mise à jour 1

Je viens de regarder cette vidéo de Anders chez PDC, et une heure), il donne quelques raisons beaucoup plus valables - tout sur le compilateur en tant que service. Juste pour le compte rendu.

Voici un cliché (sujet difficile sur lequel chercher, en fait):

Smalltalk
C

C’est aussi l’idée de PyPy et Rubinius :

(Je pense que cela pourrait également s'appliquer à Forth , mais je ne le fais pas. Je ne sais rien de Forth.)

GNAT, le compilateur GNU Ada, nécessite que le compilateur Ada soit entièrement construit. Cela peut être pénible lorsque vous le portez sur une plate-forme où il n’existe pas de binaire GNAT disponible.

En fait, la plupart des compilateurs sont écrits dans le langage qu'ils compilent, pour les raisons indiquées ci-dessus.

Le premier compilateur d'amorçage est généralement écrit en C, C ++ ou Assembly.

Le compilateur du projet Mono C # a été "auto-hébergé". depuis longtemps, cela veut dire qu’il a été écrit en C # lui-même.

Ce que je sais, c'est que le compilateur a été démarré en tant que code C pur, mais une fois le "base" les fonctionnalités de ECMA ont été implémentées, elles ont commencé à réécrire le compilateur en C #.

Je ne connais pas les avantages de l'écriture du compilateur dans le même langage, mais je suis sûr que cela concerne au moins les fonctionnalités que le langage peut offrir (C, par exemple, ne prend pas en charge les objets. programmation orientée).

Vous pouvez trouver plus d'informations ici .

Peut-être pouvez-vous écrire un BNF décrivant BNF.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow