Bootstrap (compilateur)

Soit L le langage à traiter, et X un langage disponible : on commence par écrire en X un petit compilateur de L, produisant une image dans un langage A exécutable dans le même environnement. Il suffira que ce premier compilateur traduise exactement les programmes n'utilisant qu'un sous-ensemble ${\displaystyle L_{0}}$ contenant les constructions nécessaires de L. Un tel compilateur sera noté symboliquement ${\displaystyle L_{0}{\xrightarrow[{\text{X}}]{\text{1}}}A}$.

De tels compilateurs furent longtemps développés en assembleur, un langage symbolique est souvent plus commode et plus sûr. Les premiers compilateurs peuvent être maintenant écrits en C ou dans un langage spécialisé dans l'écriture de compilateurs.

Supposons un premier compilateur noté ${\displaystyle L_{0}{\xrightarrow[{\text{X}}]{\text{1}}}A}$, écrit en X et traduisant un sous-ensemble ${\displaystyle L_{0}}$ de L dans un langage exécutable A [2]. En transcrivant son analyse de X en ${\displaystyle L_{0}}$, nous obtenons un nouveau compilateur ${\displaystyle L_{0}{\xrightarrow[{\text{Lo}}]{\text{2}}}A}$ . Compilé par le premier, il donne un nouveau ${\displaystyle L_{0}{\xrightarrow[{\text{X}}]{\text{3}}}A}$.

Soit maintenant ${\displaystyle L_{1}{\xrightarrow[{\text{Lo}}]{\text{4}}}A}$ une version étendue de (2); compilée par (1), on obtiendra de même ${\displaystyle L_{1}{\xrightarrow[{\text{X}}]{\text{5}}}A}$.

(5) se présente alors comme une extension de (1) bénéficiant des extensions introduites par (4), et ${\displaystyle L_{0}}$ peut être oublié au profit de ${\displaystyle L_{1}}$.

Avec (6) traitant en ${\displaystyle L_{1}}$ une nouvelle extension ${\displaystyle L_{2}}$, on obtiendra de même (7), rendant ${\displaystyle L_{2}}$ utilisable au lieu de ${\displaystyle L_{1}}$ et ${\displaystyle L_{0}}$...

Cette stratégie de prototypage évolutif permet d'étendre la puissance du langage effectif, d'abord réduit au strict nécessaire (par exemple, la forme itérative la plus générale), puis étendu aux constructions "de confort" (comme les formes itératives secondaires), voire à d'éventuelles extensions ; c'est ainsi que des sur-ensembles de Java sont bootstrappés.

D'une version à l'autre, les développeurs du compilateur devenant leurs propres utilisateurs, les améliorations peuvent également porter sur la qualité de la détection d'erreurs et du code engendré.

L'équipe de Niklaus Wirth tenta de réaliser le premier compilateur Pascal en Fortran, qui se révéla insuffisant. Elle fit une nouvelle tentative en utilisant Pascal comme notation algorithmique du nouveau compilateur, et traduisit à la main cette spécification détaillée. Elle obtint ainsi un compilateur de type natif pour CDC 6600, et un compilateur auto-porteur qui lui permirent une succession d'améliorations.

Supposons que l'on dispose d'un couple ${\displaystyle L{\xrightarrow[{\text{X }}]{}}A,L{\xrightarrow[{\text{L}}]{}}A}$ .

En modifiant la génération de ${\displaystyle L{\xrightarrow[{\text{L}}]{}}A}$ on obtient un ${\displaystyle L{\xrightarrow[{\text{L}}]{}}B}$; en le compilant dans le premier environnement, on obtient le nouveau compilateur ${\displaystyle L{\xrightarrow[{\text{X}}]{}}B}$.

En 1975, H.H. Nägeli écrivit un "trunk compiler" pour faciliter le portage de Pascal. C'était un compilateur de Pascal écrit en Pascal, séparant nettement les parties indépendantes des parties dépendantes de la machine-cible, comme les séquences de génération ; un commentaire détaillé pour ces dernières permettait à un compiliste de les adapter à une nouvelle machine. C'est ainsi que l'INRIA put faire en 9 hommes-mois un compilateur croisé, tournant sur CDC mais traduisant Pascal en code pour l'Iris 80 ainsi qu'un compilateur Pascal, fonctionnant pour et sur l'Iris 80. Ce dernier, écrit en Pascal, étant de ce fait facile à maintenir et à améliorer.

On parle de semi-compilation quand le compilateur produit non un code machine "natif" (propre à l'environnement visé) mais un pseudo-code (ou bytecode ) P relatif à une machine virtuelle pouvant exécuter le langage au mieux.

Le produit générique est alors un couple ${\displaystyle L{\xrightarrow[{\text{L }}]{}}P,L{\xrightarrow[{\text{P}}]{}}P}$ .

• ${\displaystyle L{\xrightarrow[{\text{P}}]{}}P}$ est exécutable dès que P l'est dans l'environnement donné ; un interprète de P est alors suffisant pour la programmation exploratoire ;
• au-delà, si on adjoint à ${\displaystyle L{\xrightarrow[{\text{P}}]{}}P}$ un générateur ${\displaystyle P{\xrightarrow[{\text{P}}]{}}Z}$, on obtient un compilateur ${\displaystyle L{\xrightarrow[{\text{P}}]{}}Z}$, et si nécessaire un compilateur ${\displaystyle L{\xrightarrow[{\text{Z}}]{}}Z}$,.

Cette technique a pu utiliser un P-code (Pascal), un M-code (Modula), un S-code (Simula), un J-code (Java) etc.

Intérêt

Cette approche peut être à la fois le support d'un compilateur multicible, ayant un analyseur et un générateur d'un pseudo-code commun P, puis autant de générateurs finaux que de machines-cible.

Elle peut être au cœur d'un atelier logiciel dont les langages partageraient le même pseudo-code P, surtout si celui-ci reste réversible.

• Auto-hébergé
• Auto-interpréteur

• NELIAC (en)
• (en) Bootstrap d'un simple compilateur à partir de zéro

• Portail de la programmation informatique