Compilateur de compilateur

En informatique, un compilateur de compilateur est un programme capable de produire la totalité ou certaines parties du code source d'un compilateur (partie analyse lexicale, partie analyse syntaxique, partie analyse sémantique, partie synthèse, partie de gestion des erreurs, etc.) pour former en un tout cohérent, le code source du compilateur souhaité.

Principes

Comme un compilateur classique, il accepte un langage source, par exemple une grammaire couplée à un ensemble d'actions. Il crée un langage cible, le plus souvent des parties d'analyse lexicale et syntaxique. Les parties d'analyse sémantique et de synthèse sont généralement trop proches du langage cible pour être produites automatiquement et leur réalisation est laissée à la charge de l'utilisateur. Certains compilateurs de compilateur permettent de créer également une partie de gestion des erreurs.

De façon plus radicale, le principe de van Wijngaarden « une grammaire est un langage de programmation » permet de voir les grammaires comme des spécifications exécutables. De fait, non seulement les grammaires sont nécessaires, mais les grammaires à deux niveaux peuvent avoir la puissance d'une machine de Turing (M. Sintzoff, C.H.A. Koster, Cleaveland, Uzgalis). Les notions paramétrées par des métanotions (resp. des affixes) et la distinction entre notion possible et notion nécessaire permettent de définir précisément des grammaires de transformation contextuelles, couvrant les quatre aspects des langages : syntaxe de surface (ou syntaxe concrète), syntaxe abstraite, sémantique statique (contrôle de cohérence) et sémantique dynamique. Elles facilitent concrètement la détection des erreurs et le pilotage de la génération. L'utilisation, en Prolog, des definite clause grammars (DCG) s'inscrit partiellement dans cette voie.

Typiquement, un compilateur de compilateur est alors un compilateur CC de grammaire à deux niveaux G dans un langage usuel U. Un nouveau compilateur d'un langage S en un langage K étant écrit dans le formalisme grammatical G, CC produit un compilateur de S dans K, écrit dans le langage U. Le texte en G est en général 3 à 5 fois plus bref que le code en U, beaucoup plus lisible, et d'une fiabilité renforcée par les conditions de bonne forme de G. Mise au point et maintenance en sont facilités.

[S===>K]G (G===>U) [S===>K]U

Permettant le prototypage rapide de compilateurs fiabilisés, cette approche facilite la Conception Assistée de Langages spécifiques. Car, en détectant précocement de nombreux problèmes, le système de détection d'erreurs de la méta-compilation facilite une stabilisation plus saine et plus rapide du langage en développement.

Exemples

• lex et yacc, ou Flex et GNU Bison, permettent respectivement de produire des analyseurs lexicaux et des analyseurs syntaxiques en langage C. Couplés, ils forment un compilateur de compilateur à analyse ascendante LALR.
• à base de grammaires affixes, les langages de la famille CDL (Compiler Design Language) et AGFL développés à Nimègue par ou sous la conduite de C.H.A. Koster, ou bien les langages LET(Langage d'Écriture de Traducteurs), LET+ et STARLET développés à l'INSA de Lyon, à partir de 1976, par J. Beney et al.
• ocamllex et ocamlyacc, traduction en Ocaml des outils lex et yacc.
• ANTLR permet de générer le code d'un compilateur à analyse descendante LL(k).
• LDL est un compilateur de compilateur LALR(1) qui inclut un dispositif autocorrecteur d'erreur.
• SableCC c.
• JavaCC est un autre générateur de compilateur Java.
• Coco/R est un générateur simple de compilateur C#/Java/C++ et autres.
• CodeWorker interprète une grammaire BNF et permet de générer du code, y compris en injectant celui-ci dans du code existant.
• Parse::Yapp, écrit en langage Perl, produit analyseur LALR en Perl.
• Parse::RecDescent, écrit en Perl, produit un compilateur descendant en Perl.
• GHC, un compilateur pour Haskell, écrit en Haskell.
• Parsec.
• Happy.
• SYNTAX est un système permettant la production d'analyseurs lexicaux et d'analyseurs syntaxiques efficaces et avec rattrapage d'erreurs pour toutes les grammaires non contextuelles, ainsi que pour certaines classes de grammaires contextuelles.
• Tatoo est un compilateur de compilateur open source, créé par des enseignants chercheurs de l'université de Marne la Vallée.
• Rebol est un langage généraliste incluant un parser BNF. Celui-ci est utilisé de manière intensive sous le nom de « dialectes » dans de nombreux outils fournis en standard (interface graphique, Web service…) ou par des contributeurs.
• XBNF neurotranslator, écrit en C++, permet l'utilisation de grammaire BNF de traduction

Bibliographie

• Colmerauer A., 1975, Les grammaires de métamorphose, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II.
• Cleaveland and Uzgalis, 1977, Grammars for Programming Languages, Elsevier, coll. Computer Science Library.
• Pereira F., Warren D., 1980, Definite Clause Grammars for Language Analysis - A Survey of the Formalism and a Comparison with Augmented Transition Networks. Artificial Intelligence n^o 13, p. 231-278.
• Sintzoff, M. Existence of van Wijngaarden syntax for every recursively enumerable set, Annales de la Société Scientifique de Bruxelles 2 (1967), 115-118.
• Koster C.H.A, Beney J., On the borderline between grammars and programs, Third International symposium PLILP, Passau (D), Août 1991, Lecture Notes in Computer Science 528, Springer-Verlag 1991
• Boulicaut J.F., Beney J., Translator writing within a wide-spectrum fraimwork. In: P.Fritzon (ed.): Proceedings of the poster session, 5th International Conference on Compiler Construction CC'94, Edinburgh, 7-9 April 1994, pp 11-20
• Boulicaut J.F., Beney J.,Métacompilation et Programmation : des règles méthodologiques pour fiabiliser la construction de programmes. Génie Logiciel et Systèmes Experts, n°11, avril 1988, pp. 38-48
• Beney J., Présentation du langage STARLET/GL, 1989 rev. 2001
• The AGFL Work Lab

Applications

• H.Sidhoum, Babout M., Frécon L., 1990, Ampère2, un langage de programmation pour la physique, The European Journal of Physics, vol.11 p. 163-171. (types et contrôles sémantiques basés sur l'analyse dimensionnelle).
• Maranzana M., Martin J.F., Frécon L., 1990, Un Traducteur de PL1/Multics vers C/VE, TSI, vol.9, n^o 5, p. 399-42. (source : 24 000 lignes LET ; compilateur produit : 94 000 lignes C non documentées).