L'amorçage nécessite toujours un soutien extérieur

Question

J'ai entendu parler de l'idée d'amorcer un langage, c'est-à-dire d'écrire un compilateur/interpréteur pour le langage lui-même. Je me demandais comment cela pouvait être accompli et j'ai cherché un peu, et j'ai vu quelqu'un dire que cela ne pouvait être fait que par soit

• écrire un compilateur initial dans un langage différent.
• le codage à la main d'un compilateur initial en Assembleur, qui semble être un cas particulier du premier

Pour moi, aucun d'entre eux ne semble être réellement bootstrapping une langue en ce sens qu'elles nécessitent toutes deux un soutien extérieur. Existe-t-il un moyen d'écrire un compilateur dans son propre langage ?

Answer 1

Existe-t-il un moyen d'écrire réellement un compilateur dans son propre langage ?

Vous ont pour avoir un langage existant dans lequel écrire votre nouveau compilateur. Si vous écriviez un nouveau compilateur, disons C++, vous l'écririez simplement en C++ et le compileriez d'abord avec un compilateur existant. En revanche, si vous créez un compilateur pour un nouveau langage, appelons-le Yazzleof, vous devrez d'abord écrire le nouveau compilateur dans un autre langage. En général, il s'agit d'un autre langage de programmation, mais ce n'est pas une obligation. Il peut s'agir d'assembleur, ou si nécessaire, de code machine.

Si vous étaient pour amorcer un compilateur pour Yazzleof, vous n'écrirez généralement pas un compilateur pour le langage complet au départ. Au lieu de cela, vous écrirez un compilateur pour Yazzle-lite, le plus petit sous-ensemble possible de Yazzleof (enfin, un sous-ensemble de assez petit au moins). Ensuite, dans Yazzle-lite, vous écrirez un compilateur pour le langage complet. (Comme Yazzle-lite est un sous-ensemble correct de Yazzleof, vous avez maintenant un compilateur qui peut se compiler lui-même.

Il existe un vraiment bon article sur le démarrage d'un compilateur à partir du niveau le plus bas possible (qui, sur une machine moderne, est essentiellement un éditeur hexadécimal), intitulé Amorçage d'un compilateur simple à partir de rien . On peut le trouver à l'adresse suivante https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html .

Answer 2

L'explication que vous avez lue est correcte. Il y a une discussion à ce sujet dans _Compilateurs : Principes, techniques et outils_ (le livre du dragon) :

• Écrire un compilateur C1 pour le langage X en langage Y
• Utiliser le compilateur C1 pour écrire le compilateur C2 pour le langage X dans le langage X
• C2 est maintenant un environnement entièrement autonome.

Answer 3

Il existe un très bon article sur le démarrage d'un compilateur à partir du niveau le plus bas possible (qui, sur une machine moderne, est essentiellement un éditeur hexadécimal), intitulé Bootstrapping a simple compiler from nothing. Il était hébergé à l'adresse http://www.rano.org/bcompiler.html mais ce lien est mort maintenant. Si vous tombez dessus, c'est une excellente lecture. (Et si quelqu'un sait où je pourrais obtenir une copie fonctionnelle, j'apprécierais vraiment un lien).

Derek, je ne sais pas si ou où cela est encore disponible en ligne mais je l'ai copié sur shorttext.com .

Answer 4

Un super intéressant discussion de ce est dans le co-créateur d'Unix Ken Thompson 's Prix Turing conférence.

Il commence par :

Ce que je m'apprête à décrire est l'un des nombreux problèmes "de la poule et de l'œuf" qui se posent lorsque les compilateurs sont écrits dans leur propre langage. Dans cette facilité, je vais utiliser un exemple spécifique du compilateur C.

et montre comment il a écrit une version du compilateur C d'Unix qui lui permettait toujours de se connecter sans mot de passe, parce que le compilateur C reconnaissait le programme de connexion et y ajoutait un code spécial.

Le deuxième modèle vise le compilateur C. Le code de remplacement est un programme auto-reproducteur de stade I qui insère les deux chevaux de Troie dans le compilateur. Cela nécessite une phase d'apprentissage comme dans l'exemple du stade II. Tout d'abord, nous compilons la source modifiée avec le compilateur C normal pour produire un binaire bogué. Nous installons ce binaire comme le C officiel. Nous pouvons maintenant supprimer les bogues de la source du compilateur et le nouveau binaire réinsérera les bogues à chaque fois qu'il sera compilé. Bien sûr, la commande login restera boguée sans aucune trace dans les sources.

Answer 5

La méthode dont j'ai entendu parler consiste à écrire un compilateur extrêmement limité dans un autre langage, puis à l'utiliser pour compiler une version plus compliquée, écrite dans le nouveau langage. Cette deuxième version peut ensuite être utilisée pour se compiler elle-même, et la version suivante. À chaque fois qu'elle est compilée, la dernière version est utilisée.

C'est la définition de bootstrapping :

le processus par lequel un système simple active un système plus compliqué qui sert le même objectif.

EDIT : Le Article Wikipedia sur l'amorçage du compilateur couvre le concept mieux que moi.