Travaux de recherche effectués

Didier Parigot

7 avril 1997

Note préliminaire : j’ai conçu cet exposé de mes travaux de façon qu’il soit compréhensible par une personne compétente en informatique mais non spécialiste de mon domaine de recherche ; je prie donc le spécialiste d’excuser sa longueur qui est une conséquence de ce choix. Ce document sera certainement très utile pour les personnes qui travaillerons avec moi à l’avenir.

1 Préambule

Depuis avril 1985, j’ai travaillé dans le projet “Langages et Traducteurs” dirigé par Pierre Boullier, tout d’abord comme stagiaire de DEA, ensuite boursier INRIA (deux années) pour la préparation de ma thèse sous la direction de Martin Jourdan, puis à partit du 1^{ère} octobre 1987 comme chargé de recherche de 2^{ème} classe et enfin depuis le 1^{ère} octobre 1991 comme chargé de recherche de 1^{ère} classe dans l’axe “compilation” du projet ChLoE dirigé par Martin Jourdan. Martin et moi, nous avons travaillé sur le même sujet de recherche : les grammaires attribuées (GA).

Ce formalisme [DJ90, AM91] est une extension des grammaires non contextuelles permettant de traiter les aspects sémantiques des langages en plus de leurs aspects syntaxiques. C’est une méthode déjà ancienne (une vingtaine d’années) mais qui n’a pas encore rencontré tout le succès que ses qualités en tant que méthode de spécification pouvaient laisser prévoir. La raison la plus importante en est que ses implantations — on peut, théoriquement, construire automatiquement à partir d’une GA un programme qui réalise la fonction qu’elle spécifie — ont jusqu’ici été handicapées par un compromis plutôt décevant, entre le pouvoir d’expression et l’efficacité.

Notre action au sein du projet depuis quelques années vise à améliorer suffisamment ce compromis pour que les GA soient enfin reconnues comme un outil important. Cette action se mène sur plusieurs fronts — développement d’applications, formation, méthodologie de programmation — dont la concrétisation est la réalisation d’un système de haute performance, que nous avons nommé Fnc-2 .

1.1 Le système Fnc-2: présentation générale

Ainsi, l’essentiel de mes travaux a porté sur la réalisation concrète d’un nouveau système de traitement de GA [JPJ^{+}90, JP92], nommé Fnc-2 et conçu conjointement par Martin Jourdan et moi-même. Nous voulions intégrer dans Fnc-2 les développements les plus récents dans ce domaine sur le plan théorique (voir ci-dessus), mais aussi en faire un outil de qualité, c’est-à-dire qui soit à la fois puissant, efficace et d’utilisation aisée et souple. Au début 1990 un premier prototype a été disponible et pouvait être raisonnablement utilisé : la preuve en est qu’il est “bootstrappé” à partir de ce premier prototype. D’après les premiers résultats d’utilisation (cf. la section 4.6 comme première vraie utilisation), nous étions encore plus convaincus que notre système représentait certainement l’une des meilleures solutions (ou compromis) à notre problème de départ. Énonçons donc les qualités principales de ce système Fnc-2.

– Grande puissance d’expression: Fnc-2 accepte la plus large classe de grammaires attribuées possible qui ne mette pas en cause l’efficacité du code produit,

– Efficacité en temps et en place, aussi bien à la construction qu’à l’exécution des évaluateurs d’attributs,

– Facilité et sûreté d’emploi, mesurées à l’effort nécessaire pour l’écriture et la mise au point d’une grammaire attribuée,

– Et enfin, la souplesse d’utilisation.

1.1.1 Présentation du langage d’entrée Olga

La définition du langage Olga (Ouf! un Langage pour les Grammaires Attribuées) a comme principal objectif la facilité, la sûreté d’utilisation et la souplesse d’emploi. Cela est dû à la conjonction des deux concepts suivants :

– Le langage d’écriture de GA (la forme externe) est un langage spécialisé conçu pour cet unique objet, et non plus un langage existant, simplement augmenté de notations supplémentaires. Ce langage, nommé Olga [JPJ^{+}90, JP91, JP92] est un langage applicatif et fortement typé, deux conditions indispensables pour offrir à l’auteur de grammaires attribuées une très grande sécurité dans sa programmation. De plus, Olga inclut des concepts modernes, comme le traitement d’exception, la modularité, le filtrage de modèles, l’inférence de type et le polymorphisme^{1}. De plus, la base syntaxique des GA est une syntaxe abstraite attribuée, permettant à l’auteur de se libérer des contraintes souvent excessives de la syntaxe concrète. Cette approche a été largement inspirée des travaux de l’équipe croap sur le même sujet : le langage Metal. Pour ce faire, on a défini les deux langages suivants : Asx pour décrire une syntaxe abstraite attribuée (déclaration d’un type d’arbre), et atc pour définir la construction d’un tel arbre à l’aide d’un analyseur lexico-syntaxique classique (comme Syntax). Olga est certainement un langage très ambitieux dans ses concepts de base, mais il nous fallait un langage qui se suffise à lui-même, aussi complet que possible. En d’autres termes, ce langage ne doit en aucun cas être un langage “jouet” permettant uniquement de valider les méthodes d’évaluation introduites par le générateur d’évaluateur (cf. la section 2.2) mais un langage permettant de développer des applications en réelle grandeur.

1. Cet aspect d’Olga a été faiblement poursuivit au cours du développement de Fnc-2

– La souplesse d’emploi vient de l’indépendance totale de la spécification par rapport à son implantation, ce qui se traduit par plusieurs propriétés pour le code produit, les évaluateurs. Ils peuvent être traduits dans plusieurs langages. Notre première cible a été le langage C puisque le générateur est écrit dans ce même langage, mais d’autres traducteurs ont vu le jour au cours des développements ultérieurs. Ils peuvent être produits soit en version exhaustive, soit en version incrémentale. Ils peuvent être couplés à divers environnements, le langage Asx jouant le rôle de la déclaration des interfaces.

L’ensemble de ces spécifications nous a amené à lancer un projet ambitieux. La conception et la réalisation de ce système ne peuvent donc être vues que comme le travail d’une équipe, composée de Martin et de moi-même (pour les permanents), sans oublier les différents stagiaires (27) et thésards (5 + 1) (voir les listes des stages et thèses) qui ont, ou qui vont participer à des points particuliers du projet. À cause du caractère ambitieux de ce système, nous avons adopté au cours de sa réalisation, une démarche de construction par étapes successives. Ainsi, le système est le résultat d’une superposition de processus à finalités différentes. Il se compose essentiellement des deux parties suivantes : le générateur d’évaluateur, qui réalise la partie purement grammaire attribuée et, autour de ce dernier, un ensemble de modules (la carrosserie [JP]) qui réalisent les interfaces vis-à-vis des utilisateurs.

Pendant ma thèse (86-88), ma contribution a porté essentiellement sur le cœur du système — le générateur d’évaluateur —, principalement sur la mise en œuvre de nouvelles méthodes d’évaluation d’attributs (ou amélioration de méthodes existantes), dans le but de satisfaire nos deux premières exigences — c’est-à-dire une grande puissance d’expression et une efficacité à tous les points de vue du code produit. Au cours de la préparation de ma thèse [Par87, Par88], j’ai défini les bases théoriques de ce générateur et réalisé un premier prototype (fin 1987). Puis pendant les années 88-90, je me suis concentré sur l’ensemble des modules qui réalisent les interfaces vis-à-vis des utilisateurs pour constituer la première version du système Fnc-2 (Frond-end Olga et Traducteur vers C). Puis, à partir de ce prototype, un ensemble de travaux de recherche ont été développés lors de stages ou de thèses. J’ajouterais que l’objectif de la réalisation du système Fnc-2 (la nécessité ou les objectifs d’une réalisation lourde d’un système sont souvent mal compris) était bien de faciliter par la suite le développement de futurs travaux de recherche. Le système Fnc-2 a joué pleinement son rôle d’outil de recherche dans les années qui ont suivi la sortie du premier prototype. En effet, je pense avoir réalisé en grande partie le programme scientifique que j’avais défini lors de ma promotion en tant que chargé de recherche de 1^{ère} classe en 1991.

Comme dit précédemment, l’ensemble des travaux présentés ici sont l’œuvre d’une équipe de recherche mais malgré tout, l’implantation du système et l’organisation de sa réalisation a été presque de mon unique ressort et j’ai personnellement assuré en grande partie l’encadrement des différents stagiaires. Pour bien faire comprendre la cohérence de l’ensemble de mes travaux (encadrement de stagiaires), j’ai préféré regrouper mes activités par sujets en y ajoutant les travaux des stagiaires et thésards correspondants.

Ainsi mon activité de recherche peut donc se décomposer de la manière suivante,:

– Travaux Théoriques :

– Transformation de grammaires attribuées;

– Optimisation mémoire;

– Analyse de flot de grammaire;

– Évaluation incrémentale;

– Évaluateurs d’attributs sur machines parallèles;

– Généricité dans les Grammaires Attribuées ;

– La méta-composition des GA (composition descriptionnelle);

– Les GAs Dynamiques : Une nouvelle vision des GAs;

– Mises à jour destructives dans les GAs ;

– Relation avec la programmation fonctionnelle ; – Programmation dirigée par la structure et déforestation ;

– Évaluation indulgente (sous-classe de l’évaluation paresseuse) ;

– Sémantique dénotationnelle ;

– Transformation d’arbres attribués.

– Participation à des Projets Européens :

– Projet Esprit Cocos ;

– Projet Esprit MultiWork ;

– Opération InterSemfinancée par le greco programmation ;

– Projet Esprit Compare ;

– Implantation et Développement de Fnc-2 ; – Mise en place d’outils de développement partagé ;

– Évolution des langages de spécification de Fnc-2 ;

– Le constructeur d’arbres abstraits atc;

– Glaneur de cellules ;

– Compilation du filtrage d’arbres ;

– Le générateur de décompilateurs ppat ;

– Interface graphique pour Fnc-2 ;

– Le traducteur vers Caml ;

– Support technique et organisation d’un groupe de recherche ;

– Encadrement des stagiaires (27 stages de DEA et 5 + 1 thèses).

2 Travaux Théoriques

2.1 Rappel sur la notion de grammaire attribuée

Rappelons brièvement le principe de la méthode des grammaires attribuées. On considère une grammaire indépendante du contexte. À chacun de ses nonterminaux, on attache deux ensembles de symboles, les attributs synthétisés, qui véhiculent de l’information depuis les feuilles d’un arbre de dérivation jusqu’à la racine, et les attributs hérités, qui transportent de l’information en sens inverse. À chaque production on associe un certain nombre de règles sémantiques qui spécifient comment calculer les attributs de sortie, c’est-à-dire les attributs synthétisés du non-terminal membre gauche de la production, et les attributs hérités des non-terminaux du membre droit de la production, en fonction des attributs d’entrée de la production (les autres attributs). D’après ce rapide exposé les principales qualités de cette méthode sont les suivantes :

– Les grammaires attribuées sont une méthode de description déclarative, c’est-à-dire non-procédurale : il n’est pas spécifié comment (dans quel ordre) on calcule les attributs, mais seulement ce que l’on calcule (leur valeur).

– Elles sont une méthode structurée, induite par les productions de la grammaire ;

– Elles sont basées sur le principe de localité : tout se passe au sein de chaque production;

– Elles sont une spécification exécutable : il est possible de construire un programme, appelé évaluateur d’attributs, qui exécute la spécification d’entrée. Un évaluateur est chargé de calculer, à l’aide des règles sémantiques, un ou plusieurs attributs d’un arbre de dérivation qui représentetn la valeur sémantiques du texte source.

2.2 Présentation des travaux théoriques

J’ai volontairement pris le choix d’une présentation très informelle de mes travaux de recherche, pour les deux raisons suivantes. D’une part, mes travaux portent sur un large sous-ensemble des problèmes rencontrés en grammaires attribuées, et dont la formalisation demanderait une trop longue présentation. La deuxième raison, qui est d’une certaine manière une conséquence de ce qui précède, est que le nombre impressionnant de résultats a souvent rebuté les utilisateurs potentiels des GA. En effet, l’un des problèmes majeurs dans ce domaine est l’efficacité du programme qui exécute la spécification d’entrée (les évaluateurs d’attributs). La théorie des GA donne tout un ensemble de résultats théoriques sur ce problème, mais sans pour autant fournir une solution “idéale”. Ainsi, lors de l’application de ces résultats, c’est-à-dire de la réalisation du constructeur (générateur d’évaluateur d’attribut) qui engendre le dit programme exécutable, il s’est avéré assez difficile de trouver un bon compromis entre les différentes solutions. En effet, à chaque type de constructeur, le compromis interne à ce dernier correspond souvent pour les utilisateurs, à la compréhension d’un de nos problèmes qui n’est pas forcément d’un abord facile. Ainsi les utilisateurs ont été plutôt sensibilisés aux problèmes internes de la construction qu’aux qualités intrinsèques des GA, sans pour autant se voir proposer une solution satisfaisante.

La finalité de mes travaux a été d’essayer de remédier à cela. En effet, nous sommes convaincus que les GA, par leurs qualités propres, en particulier la facilité d’écriture, méritent une plus large diffusion. Ainsi nous sommes nous placés dans le cadre de l’utilisation pratique, sur des exemples réalistes, et non plus dans un cadre abstrait (théorique). Sous cette hypothèse, nous montrons, à travers la réalisation d’un nouveau constructeur, qu’il existe une solution satisfaisante. Ainsi les utilisateurs potentiels pourront enfin apprécier et juger des qualités de la programmation en GA, sans pour cela être obligés de supporter toute la complexité de la construction, et parfois de se plier à des contraintes éventuelles. Pour construire cette solution, nous avons étudié un vaste sousensemble de problèmes rencontrés dans la théorie des GA, réexaminé les résultats en se plaçant résolument dans notre cadre, et proposé des approches différentes ou des améliorations significatives. L’ensemble de ces travaux prend encore plus de valeur dans leur juxtaposition. Pour nous, la réalisation de ce constructeur et son utilisation était donc un début de “preuve” de la validité de notre approche.

Les deux problèmes importants que l’on rencontre dans la génération des évaluateurs sont les suivants : les évaluateurs d’attributs engendrés sont en général très gourmands en place mémoire, et le temps de construction de ces derniers peut être très important. Il faut bien admettre que ces deux points ont souvent été un frein important à l’utilisation des GA, surtout sur des données de taiile importante. En effet, dans la théorie des grammaires attribuées, les résultats théoriques de complexité sont souvent exprimés dans le pire des cas. Mes travaux ont montré que ces résultats d’explosion combinatoire restent confinés à des cas pathologiques de GA, et qu’en pratique sur des textes importants, ces deux points noirs n’apparaissent pas, ou restent dans des limites très raisonnables et en tout cas très loin des bornes définies par la théorie.

2.3 Transformation des grammaires attribuées : Classes de grammaires attribuées

Pour contrer l’inefficacité en place, plusieurs classes de grammaires d’attributs qui imposent des restrictions sur la GA d’entrée ont été introduites ; grâce à ces limitations, il était alors possible de construire des évaluateurs peu gourmands, mais au prix d’une perte importante de puissance d’expression. Parmi ces classes, celle des GA l-ordonnées joue un rôle particulier. En effet, elle est la plus large classe pour laquelle il est possible d’engendrer un évaluateur efficace en mémoire, — à base de séquence de visite — sans pour autant pénaliser l’efficacité en temps. Cette classe se caractérise par la connaissance statique d’un ordre total d’évaluation des attributs. En outre, toute GA peut être transformée en une GA l-ordonnée équivalente, mais avec un risque d’exponentialité de la taille de cette dernière. Enfin, le test de caractérisation de cette classe l-ordonnée est un problème NP-complet. Mon premier travail a été de concevoir un nouvel algorithme de transformation [Par87, Par88, JPJ^{+}90], qui fait que ce facteur d’exponentialité reste confiné à des cas pathologiques. Pour être tout à fait précis, pour l’instant, je n’ai réalisé cette transformation qu’à partir d’une sous-classe de GA nommée FNC — fortement non-circulaire — mais dans ma thèse [Par87] j’ai défini la transformation complète, à partir des GA bien formées qui est la plus large classe des GA.

2.4 Analyse de flot de grammaire

Cependant cet algorithme de transformation impose d’effectuer en cascade un ensemble de tests de caractérisation (test FNC, test doublement non circulaire, etc) qui introduisaient un temps de construction important, l’autre point noir des GA. J’ai montré que grâce à l’introduction de nouvelles techniques [Par85, Par87, JP90a] (stabilité sémantique et ordonnancement optimal), ces différents tests de caractérisation deviennent quasiment linéaires en la taille de la GA alors qu’ils sont polynomiaux en théorie. En outre, le test de caractérisation des GA bien formées, théoriquement exponentiel, devient en pratique parfaitement réaliste [Par88]. Ceci m’a permis d’envisager rapidement la transformation des GA bien formées en des GA l-ordonnées. De plus, nous nous sommes rendus compte que ces problèmes appartiennent à une classe beaucoup plus générale — analyse de flot de grammaires — et que nos optimisations pouvaient, du même coup, prendre une signification plus importante [JP90a].

2.5 Optimisation mémoire

avec C. Julié (DEA [Jul86], puis thèse [Jul89])

En collaboration avec Catherine Julié , nous avons travaillé sur les méthodes d’optimisation mémoire introduites sur les GA l-ordonnées. Dans ce domaine il existe un résultat théorique “gênant” : la recherche d’un schéma optimal de stockage des attributs devient très vite (même pour des sous-classes de GA très étroites) un problème NP-complet. Malgré cela, des méthodes ont été définies dans le cadre des GA l-ordonnées, et donnent des résultats très satisfaisants, bien que le schéma d’allocation ne soit pas optimal. En effet, avec la connaissance de l’ordre total d’évaluation, il est possible sous certaines conditions de décider que tel attribut peut s’implanter, soit en variable globale soit en pile (c’est-à-dire hors de l’arbre). Nous avons amélioré ces méthodes au point de déterminer des conditions nécessaires et non plus seulement suffisantes. Nos résultats pratiques [Jul89, JP90b] montrent qu’environ 50% à 70% des attributs sont implantés en variables, et que de 20% à 40% des attributs sont implantés en pile.

Les résultats que nous avons acquis en 1990 nous permettent de stocker hors de l’arbre, outre tous les attributs temporaires, c’est-à-dire ceux dont la durée de vie est limitée à une seule visite du nœud qui les porte, une bonne partie des attributs non temporaires : ceux qui peuvent être stockés dans des variables globales ou dans des piles strictes [JP90b, JP90c]. Nous savons aussi, au moins théoriquement, comment implanter ceux qui restent dans des piles “cactus”.

Le fait de pouvoir stocker tous les attributs hors de l’arbre, outre ses effets bénéfiques sur la consommation de mémoire, permettra d’augmenter la puissance d’expression des GA en réutilisant les mêmes techniques d’évaluation (cf. la section 2.10). Ce travail a aussi eu de l’importance pour d’autre travaux de recherche (cf. la section 2.11 ou la section 2.12.1).

2.6 Évaluation incrémentale

J’ai aussi développé une méthode originale d’évaluation incrémentale [Par87, Par88, JPJ^{+}90]. Quelques mots sur le problème à résoudre : soit un arbre complètement décoré par des attributs, tel que ceux-ci soient consistants vis-à-vis des règles sémantiques de la GA qui les définissent. Une modification syntaxique de l’arbre (comme on peut en faire avec un éditeur structurel tel que Centaur) peut se ramener au remplacement d’un sous-arbre consistant par un autre sousarbre extrait précédemment d’un autre arbre lui aussi consistant. Au point de modification cependant, les valeurs des attributs peuvent ne pas être consistantes. L’évaluation incrémentale a pour but de rétablir la consistance du nouvel arbre en ne recalculant que les instances d’attributs nécessaires. À la suite des travaux de T. Reps, ce thème de recherche a connu un grand succès. La plus grande difficulté consiste à trouver des algorithmes de réévaluation asymptotiquement optimaux, c’est-à-dire dont la complexité est proportionnelle au nombre d’instances d’attributs dont la valeur dans le nouvel arbre est différente de celle dans l’arbre initial. Le problème est que les dites instances ne sont pas connues au moment où l’algorithme commence. Dans la réévaluation incrémentale comme dans l’évaluation exhaustive, il s’agit de trouver le meilleur compromis entre l’efficacité et la puissance d’expression. Ma méthode, fondée sur des travaux de G. Filé [Fil86], utilise un évaluateur quasi-déterministe capable de commencer son évaluation en tout nœud de l’arbre et de “remonter” si besoin est. Un tel évaluateur peut être construit pour toute grammaire doublement non circulaire (DNC). La classe DNC est intermédiaire entre la classe FNC et la classe l-ordonnée, mais notre transformation FNC-l-ordonnée (cf. la section 2.3) permet d’appliquer ma méthode à toute grammaire FNC. La réévaluation incrémentale s’obtient en ajoutant à cet évaluateur un contrôle sémantique, dont le rôle est de tester, avant de réévaluer une instance, si c’est effectivement nécessaire et, après avoir réévalué une instance, de comparer sa nouvelle valeur avec son ancienne, de façon à savoir s’il faut réévaluer ses descendants. J’ai pu tester notre méthode dans des conditions réalistes (cf. la section 3.3.2) dans d’un environment interactif comme le système Centaur . De plus la séparation entre le contrôle sémantique et la méthode de réévaluation proprement dite induit une très grande souplesse d’utilisation de cette méthode. En effet, le contrôle sémantique, en règle générale, dépend fortement du type de l’application décrite. Ainsi ce dernier peut être redéfini pour l’application en question (voir la section 3.3.2).

2.7 Évaluateurs d’attributs sur machines parallèles

avec B. Marmol (DEA [Mar90], puis thèse [Mar94])

L’efficacité des évaluateurs séquentiels à base de séquences de visites est due à la connaissance d’un ordre total d’évaluation des attributs de chaque non-terminal, qui fait que l’évaluateur sait à tout instant quels attributs il a déjà calculé. En ce sens, cette contrainte est “utile” puisqu’elle permet de gagner en efficacité. En revanche, l’ordre de calcul des attributs d’une production n’est contraint que par l’ordre de calcul des attributs de chaque non-terminal et par les dépendances locales ; ceci ne définit en général qu’un ordre partiel, et tous les ordres totaux compatibles avec celui-ci sont équivalents en efficacité.

On peut donc imaginer que, sur une machine parallèle, il est important de conserver un ordre total pour évaluer les attributs de chaque non-terminal, de façon à éviter des attentes et des synchronisations inutiles, mais qu’il est bénéfique de parcourir en parallèle des sous-arbres disjoints pour calculer leurs attributs ([Mar90]).

Nous avons créé une version modifiée de Fnc-2 qui produit des évaluateurs parallèles fondés sur la méthode précédente. Ces évaluateurs sont écrits en C pour une machine Sequent Balance, dont nous possédons un exemplaire à Rocquencourt, et son système d’exploitation Dynix. L’architecture de cette machine, multi-processeur à mémoire partagée, est parfaitement adaptée à l’implantation de notre méthode d’évaluation. Après avoir résolu de nombreux problèmes très irritants dûs à notre inexpérience de la programmation d’applications parallèles (le travail de B. Marmol), nous avons pu mener quelques expériences sur des GA et des textes sources relativement réalistes. Les résultats sont tout à fait satisfaisants puisque nous observons une parallélisation très réussie (multiplication de la vitesse de traitement par un facteur supérieur à 5 avec 6 processeurs, soit une efficacité de 86%). Ces travaux sont décrits plus en détail dans [Mar94, JMP94].

Par ailleurs, nous avons étendu les techniques d’optimisation de la gestion de la mémoire des évaluateurs classiques à nos évaluateurs parallèles. Plus précisément, nous considérons les évaluateurs parallèles comme une famille d’évaluateurs exhaustifs séquentiels, sur chacun desquels nos algorithmes d’optimisation mémoire peuvent s’appliquer. La description formelle de cette décomposition est achevée [Mar94] s’appuyant fortement sur nos travaux de la section 2.5 ; malheureusement, nous n’avons pas pour l’instant le temps de la mettre en œuvre.

2.8 Généricité dans les Grammaires Attribuées

avec C. Le Bellec (DEA [Le 89], puis thèse [Le 93])

Une GA générique est une GA normale qui décrit un algorithme classique (comme l’identification à l’aide d’une table des symboles) sur une syntaxe très abstraite, minimale, qui ne comporte que les notions syntaxiques utiles pour cet algorithme (comme la déclaration d’un identificateur, l’utilisation d’un identificateur et le bloc). On voudrait alors avoir un moyen d’appliquer cet algorithme sur une syntaxe réelle décrivant un langage complet. Cette application est spécifiée par l’association à chaque non-terminal de la GA générique d’un ensemble de non-terminaux de la GA réelle. Il est alors possible, moyennant certaines conditions, de plaquer les calculs spécifiés par la GA générique sur la grammaire réelle et de construire une GA sur cette grammaire réelle qui est équivalente à la GA générique (notion d’instanciation).

Pour construire alors, sur la syntaxe réelle, une nouvelle grammaire attribuée réalisant la sémantique de la GA générique (notion d’instanciation), on procède ainsi :

– On construit d’abord une première grammaire qui a pour base la syntaxe de la grammaire réelle et qui fournit, pour tout arbre de celle-ci, l’arbre de la syntaxe de la GA générique qui lui correspond selon l’association entre non-terminaux définie ci-dessus.

– On compose ensuite cette grammaire avec la GA générique, à l’aide du coupleur décrit dans la section 2.9 basé sur la composition descriptionnelle.

Le problème se “réduit” donc à construire automatiquement cette première GA à partir de la syntaxe du gène, de la syntaxe “cible” et de leur association. Nous avons mis au point une famille d’algorithmes qui effectuent cette construction dans diverses situations de complexité croissante [LJPR93, Le 93].

Il faut savoir que l’idée d’utiliser la méta-composition pour faire de la généricité est la pièce maîtresse de cette méthodologie que je nommerais par la suite généricité structurelle. J’ai personnellement eu cette idée (très simple) au tout début 1992 mais malheureusement quelque semaines tard dans [FMY92] nous découvrions quasiment la même approche.

En 1993, Hervé Benvel [Ben93] a commencé une thèse avec nous, pour poursuivre ces travaux, mais malheureusement Hervé^{2} n’a jamais vraiment commencé à travailler. En gros, le premier travail que j’ai essayé de lui faire faire (notion de forme standard), Loïc Correnson l’a effectué en quelque mois par la suite en 1995.

avec Loïc Correnson en stage d’option de l’École Polytechnique [Cor96]

Nous avons implanté dans le système Fnc-2 nos travaux de 1993-94 sur la généricité dans les grammaires attribuées, en réalisant un “instancieur” de GA. Celui-ci prend en entrée un gène, c’est-à-dire une GA décrivant un algorithme sur une syntaxe minimale, une syntaxe cible et une description de l’association entre les éléments des deux syntaxes, et produit une nouvelle GA qui décrit l’exécution de l’algorithme du gène sur la syntaxe cible.

Au cours de cette réalisation, L. Correnson a amélioré l’applicabilité de la méthode en introduisant la notion de forme standard de la syntaxe d’une GA, ainsi qu’un algorithme de réduction d’une GA en sa forme standard qui préserve la sémantique. Il a aussi prouvé qu’un gène transformé en sa forme standard est instanciable sur un nombre au moins aussi élevé (et en général plus élevé) de syntaxes cible que lorsqu’il est sous sa forme originelle. Il est à noter que cette notion de forme standard peut aussi servir à déterminer (avec des critères syntaxiques) si deux GA sont équivalentes. Par ailleurs, il a donné une nouvelle définition, plus large, de la relation de correspondance entre deux syntaxes qui prend en compte mon travail de la section 3.3.3. Ces travaux sont décrits dans [Cor96] et ont valu à Loïc Correnson le prix d’option de l’École Polytechnique.

2. Personnellement, je ne souhaitais pas le prendre en thèse car lors de son DEA je ne l’avais déjà presque jamais vu

2.9 La composition descriptionnelle (ou méta-composition) des GA

Cet axe concerne la composition descriptionnelle (ou méta-composition) des GA, définie par Ganzinger et Giegerich [GG84] avec leurs grammaires couplées par attributs. L’idée de base est que, si l’on a deux GA spécifiant chacune une transduction d’arbres attribués (c’est-à-dire une fonction d’une première syntaxe abstraite attribuée vers une seconde), et si la syntaxe de sortie de la première est égale à la syntaxe d’entrée de la seconde, il est possible de composer ces GA. Une manière simple pour ce faire est de produire un évaluateur pour chaque GA et de passer l’arbre de sortie du premier, qu’on construit explicitement, comme arbre d’entrée du second. H. Ganzinger et R. Giegerich ont prouvé qu’il existait une manière plus efficace d’aboutir au même résultat en produisant, à partir de ces deux GA, une troisième GA spécifiant la composition des transductions sans construire explicitement l’arbre intermédiaire. De plus ils donnent un algorithme pour effectuer cette construction.

avec S. Taouil en DEA [Tao88]

S. Taouil était chargée d’étudier en quoi les constructions offertes par Olga pour la construction d’arbres par attributs pouvaient compromettre la possibilité d’effectuer la composition descriptionnelle de deux GA. Dans le principe, les GA manipulées par Fnc-2 vérifient les conditions imposées par cette construction, mais certaines possibilités d’Olga (nœuds listes en particulier) s’écartent du cadre initial. S. Taouil a montré que ces constructions ne compromettaient pas en fait la composition descriptionnelle et a donné une nouvelle version de l’algorithme de construction adaptée à Olga. J’avoue que le stage de S. Taouil n’a pas été d’une excellente qualité et ces travaux ont dû être approfondi par la suite.

avec Gilles Roussel (Magistère [Rou92b], puis thèse [RPJ94])

Nous (essentiellement le travail de Gilles Roussel) avons réalisé un coupleur de GA qui, à partir de deux GA composées séquentiellement, produit une GA qui réalise la même fonction que l’exécution séquentielle des deux GA initiales mais sans construire l’arbre intermédiaire. Cela favorise évidemment l’écriture modulaire de grosses applications sans nuire à l’efficacité (au contraire). Notre coupleur est fondé sur l’algorithme de méta-composition de Ganzinger et Giegerich, modifié pour traiter les constructions “inhabituelles” d’Olga (nœuds liste, …) et les conditionnelles. Nous avons en outre réalisé un optimiseur de GA qui transforme une GA en une autre GA équivalente mais plus “efficace”, en particulier en court-circuitant des chaînes de règles de copie [Rou92a] ; cet optimiseur est particulièrement utile sur les GA produites par le coupleur.

Nous proposons aussi [RPJ95, RPJ94, Rou94b] une autre approche de la méta-composition, plus dynamique, qui conserve l’avantage essentiel de ne pas construire les arbres intermédiaires. Cette approche a été motivée et guidée par les contraintes de l’utilisation de la méta-composition dans la mise en œuvre de la généricité dans les GA (cf. la section 2.8). En effet, nous avons défini une méta-composition qui travaille directement au niveau des évaluateurs et non plus au niveau “source” des GA. Les avantages de cette approche est qu’elle permet, en premier lieu, de s’affranchir des conditions de clôture de la métacomposition classique : il est en effet toujours possible de coupler deux évaluateurs selon notre méthode, alors que la méta-composition des GA correspondantes peut être impossible pour des questions de circularité ou de classe de la GA résultante.

Plus précisément, nous avons définis deux types approches, l’une qui produit des coupleurs dit statiques (l’approche de Gilles Roussel) et l’autre des coupleurs dit dynamique (mon approche).

De plus, mon approche permet une réelle compilation séparée. En effet, nous montrons comment construire séparément des évaluateurs particuliers qui peuvent s’affranchir de l’existence physique de leur arbre de base mais accèdent au travers les uns des autres à l’arbre d’entrée de la grammaire attribuée qui fait appel à ces évaluateurs.

Nous pensons étendre cette approche en faisant en sorte que ce type d’évaluateur puisse commencer son évaluation à n’importe quel nœud de l’arbre. Ceci sera certainement fait en utilisant la trame des évaluateurs incrémentaux DNC (cf. la section 2.6) que nous développons dans le contexte de l’intégration de Fnc-2 et de Centaur (cf. la section 3.3.2 ).

2.10 Les Grammaire Attribuée Dynamiques : une nouvelle vision des GA

Bien que les GA aient été introduites il y a trente ans, leur manque de pouvoir d’expression les a jusqu’ici confiné dans le domaine du traitement des langages de programmation. Nous voulons étudier les conséquences de la possibilité de stocker tous les attributs hors de l’arbre (cf. la section 2.5). En effet, s’il ne sert plus à porter les attributs, le seul rôle de l’arbre est de guider le parcours de l’évaluateur. L’arbre peut alors être un objet dynamique et/ou virtuel.

Depuis longtemps, je soutien qu’il est possible d’étendre cette expressivité et que les GA peuvent être utilisées pour décrire des calculs sur des structures qui ne sont pas uniquement des arbres, mais aussi des formes abstraites permettant de décrire des structures infinies.

Cette nouvelle formulation est fondée sur les deux remarques suivantes :

– la théorie des GA ne se préoccupe nullement des moyens mis en œuvre pour la construction des arbres ni de leur représentation physique ; – la théorie des GA n’utilise pas la propriété de terminaison des calculs

induite par le fait qu’ils sont dirigés par une structure finie.

Plus précisément, notre interprétation de la grammaire sous-jacente à une GA est la même que celle de la grammaire décrivant les arbres d’appels pour un programme fonctionnel donné ou les arbres de preuve pour un programme logique donné : elle décrit l’ensemble des flots de contrôle possibles. Dans ce contexte une production décrit un schéma récursif élémentaire (flot de contrôle), tandis que les règles sémantiques décrivent les calculs associés à ce schéma (flot de données).

Il est très important de remarquer que la plus grande partie des résultats théoriques et pratiques concernant les GAs, en particulier les algorithmes de construction d’évaluateurs efficaces, sont fondés uniquement sur une abstraction du flot de contrôle grâce à la grammaire, et pas du tout sur la manière dont une instance particulière de ce flot est obtenue au cours d’une exécution. En conséquence, nous proposons [PDRJ96] deux extensions syntaxiques qui sont en accord avec cette vision :

– les productions conditionnelles qui permettent de diriger le flot de contrôle grâce à des valeurs d’attributs,

– et les schémas de production qui permettent de décrire un schéma de récursion indépendamment de toute structure physique et/ou permettent une combinaison différente des éléments d’une structure physique (production) donnée.

Nous obtenons ainsi un langage dont le pouvoir d’expression est comparable à celui de la plupart des langages fonctionnels du premier ordre, avec un côté déclaratif beaucoup plus marqué.

Comme ces extensions ne remettent pas en cause les bases du formalisme des GA, leur implantation dans le système Fnc-2 ne concerne que les parties avant et arrière du compilateur Olga et pas le générateur d’évaluateurs, qui est la partie la plus importante et la plus compliquée. J’ai réalisée en quelques hommes-semaines une première implantation des grammaires attribuées dynamiques.

L’intérêt de ces extensions est de redonner aux GA leur expressivité intrinsèque. De plus, elles nous permettent d’envisager de nouveaux axes de recherche en comparant nos techniques d’analyses à celles qui ont été développées dans des formalismes de même expressivité. C’est dans ce cadre que s’inscrivent en particulier nos travaux sur les mises à jour destructives dans les GA [DPJ95] ou les relations avec la programmation fonctionnelle (cf. la section 2.12.1).

Notre première présentation des GA dynamiques [PDRJ96] était, volontairement, assez informelle et intuitive. En 1996, nous avons formalisé la notion de GA dynamique, ainsi que leur implantation à base de séquences de visite [PRJD96a, PRJD96b] ; nous avons en particulier prouvé formellement la validité de la technique de “changement de plan”, qui permet de réutiliser sans modification un générateur d’évaluateurs existant, comme celui de notre système Fnc-2 .

2.11 Mises à jour destructives dans les GA

avec Étienne Duris (en DEA [Dur94], puis thèse en cours)

Une GA est une spécification déclarative d’un calcul sur un arbre qui peut être considérée comme un cas particulier de programme applicatif ou fonctionnel. Le générateur d’évaluateurs analyse la partie syntaxique de la GA et, par souci d’efficacité, la transforme en un programme impératif effectuant des effets de bord. Cependant, l’analyse des fonctions sémantiques n’est pas aussi poussée. En particulier, sous certaines conditions de typage, une règle sémantique X.a : = f(Y.a, …) , où f est une fonction de mise à jour , peut être traduite par l’affectation v : = F (v, …), grâce aux analyses de durée de vie des attributs (cf. la section 2.5), qui conserve entre autres son caractère applicatif. Pour augmenter l’efficacité, on voudrait remplacer cette affectation par l’instruction P (v,); , où la procédure P est l’équivalent destructif de F. Pour cela, il faut d’une part déterminer les conditions dans lesquelles cette transformation est légitime et, d’autre part, pouvoir construire automatiquement P à partir de la définition de f. Nous avons étudié et résolu ces deux problèmes dans le cas où f est définie par une grammaire attribuée [Dur94, DPJ95] . Cependant notre algorithme déterminant la légalité de la transformation, qui repose sur la possibilité que l’ancienne valeur de v soit partagée par une valeur encore active, est assez pessimiste (bien que parfaitement sûr) et peut être amélioré.

2.12 Relation avec la programmation fonctionnelle

Il est intéressant de noter que, au cours de ce travail, nous avons été amené à étudier un problème équivalent dans le cadre de la programmation fonctionnelle, ainsi que les solutions qui lui ont été apportées précédemment. Cela a renforcé notre conviction – déjà étayée par des travaux de Thomas Johnsson [Joh87] et d’autres – qu’il existait des relations très étroites entre ces deux styles de programmation (GA et programmation fonctionnelle) et que l’étude de ces relations pouvait être très fructueuse pour les deux. Par exemple, nous avons constaté [Dur94] des similarités, mais aussi des différences, entre la méta-composition des GA et la déforestation des programmes fonctionnels, deux transformations de programme visant à éliminer la constructions de structures intermédiaires inutiles; nous espérons, en poursuivant cette étude comparée, pouvoir améliorer chacune de ces deux méthodes.

2.12.1 Programmation dirigée par la structure et déforestation

Avec Étienne Duris et Gilles Roussel

Les GA dynamiques nous permettent d’atteindre le même pouvoir d’expression que les langages fonctionnels du premier ordre. Dans ceux-ci, le problème de l’élimination des structures intermédiaires (déforestation) est abordé à l’aide de l’opérateur de contrôle générique fold, qui permet de rendre la structure des données plus explicite (programmation dirigée par la structure). Cette propriété structurelle étant intrinsèque aux GA, nous avons été amenés à comparer les GA et les folds, tant sur le plan du pouvoir d’expression que sur celui de leurs méthodes de “composition optimisante” (composition descriptionnelle et fusion, respectivement).

Dans [DPRJ96a, DPRJ96b, DPRJ97], nous présentons nos premiers résultats. Les folds du premier ordre sont équivalents aux GAs purement synthétisées. Dans ce cadre, la fusion des folds et la composition descriptionnelle aboutissent au même résultat, mais cette dernière est complètement indépendante de l’évaluation (transformation de source à source) tandis que la fusion nécessite la connaissance de la méthode d’évaluation. De plus, beaucoup de programmes qui nécessitent l’usage de folds d’ordre supérieur peuvent être traités avec des GA du premier ordre, grâce à la notion d’attribut hérité. Les approches différentes de ce problème dans ces deux formalismes permettent d’envisager des fertilisations croisées entre GA et programmation fonctionnelle.

Plus généralement, les folds étant des catamorphismes [FJMM91], nous avons commencé à étudier les GA en termes algébriques, afin de comparer plus facilement les résultats obtenus en GA et en programmation fonctionnelle et de faciliter le passage de connaissances d’un domaine à l’autre. En particulier, nous commençons à étudier notre notion de généricité structurelle dans le monde fonctionnel [DPRJ97].

2.12.2 Évaluation indulgente

Avec Étienne Duris

Certains exemples de programmes fonctionnels se traitent en “une passe” en évaluation paresseuse mais nécessitent une décomposition en plusieurs fonctions en cas d’évaluation stricte. En général, cette décomposition doit être effectuée à la main. Or ces exemples s’écrivent en GA aussi facilement que la version fonctionnelle paresseuse tandis que la décomposition (calcul de l’ordre d’évaluation et des séquences de visite) est réalisée automatiquement par le système. Nous avons démarré une étude systématique sur ce sujet, mais nous n’avons pas encore de résultat méritant publication, juste quelques comparaison avec le langage fonctionnel paresseux Haskell sur des exemples types [Jou96].

2.12.3 Sémantique dénotationnelle

Avec Stéphane Leibovitsch (DEA [Lei96])

Les relations entre la sémantique dénotationnelle et les GA ont été peu étudiées : un seul article de H. Ganziger [Gan80] traite vraiment de ce sujet, en montrant comment traduire une spécification de langage en sémantique dénotationnelle en un interprète écrit en GA. Malheureusement, les GA produites dépassent le cadre traditionnel des GA, puisqu’elles nécessitent une évaluation paresseuse et circulaire. Or, les GA dynamiques permettent de décrire ce type d’extension. Nous avons donc étudié si elles pouvaient constituer une réponse aux diverses questions laissées ouvertes par H. Ganzinger.

S. Leibovitsch a su répondre positivement à cette question [Lei96]. Il a repris et adapté le schéma de traduction de Ganzinger et montré que les GA qu’il produit sont des GA dynamiques acceptables par Fnc-2 . Il a en outre réalisé (au moins en partie) un prototype de traducteur automatique mettant en œuvre ce schéma. La seule construction qui pose encore problème est l’utilisation de continuations pour traiter les transferts de flot de contrôle non structurés (l’instruction goto).

2.13 Transformation d’arbres attribués

Avec A. Souah (en DEA [Sou87], puis en thèse [Sou90])

A. Souah a travaillé sur la transformation d’arbre attribuées: cette technique permet de décrire agréablement des transformation de programmes — optimisations dans les compilateurs , traduction vers un langage intermédiaire — que les grammaire attribuée ne permettent pas.

Son sujet consistait à concevoir et implanter un nouveau système de transformation d’arbre attribués (STAA) qui se distingue des travaux antérieurs [LMOW88] par sa puissance d’expression supérieure, un côté déclaratif plus marqué et une sémantique beaucoup mieux définie. On peut voir un tel système de transformation comme un système de réécriture conditionnelle ou les conditions sont exprimées à l’aide d’une grammaire attribuée. Nous avons défini une notion de cohérence d’un tel système de réécriture conditionnelle.

Cette approche pose plusieurs problèmes théoriques :

– Au cours du processus de transformation le contexte associé à l’arbre transformé évolue. Ainsi, il est possible que plusieurs instances d’attributs changent de valeur. En particulier, les instances d’attributs arguments des prédicats de pré-conditions peuvent être affectées par la modification. Donc la valeur d’une pré-condition d’une règle de transformation dont le modèle d’entrée filtre un sous-arbre peut varier. Nous dirons qu’une pré-condition est stable si sa valeur ne varie pas quelle que soit l’évolution du contexte par ailleurs. L’idée clé de notre approche est qu’une transformation ne peut s’effectuer que si sa pré-condition est dans un état stable. Nous dirons qu’une telle transformation est cohérente. Bien sur, nos travaux sur l’évaluation incrémentale (cf. la section 2.6) trouvent ici une application directe.

– La notion de cohérence nous a poussé à étudier la possibilité de vérifier la cohérence d’un système de transformation de manière statique. En effet, le test de la cohérence du système revient à pouvoir calculer les dépendances entre deux instances d’attributs dans n’importe quel arbre de dérivation. Nous proposons deux algorithmes très proches des algorithmes de tests de caractérisation (cf. la section 2.3) : le premier calcule cette dépendance dans le cas des GA bien formées, tandis que le second se restreint à la classe des grammaires Doublement Non Circulaires (DNC).

– L’aspect déclaratif du système pose deux problèmes :

1. Du fait qu’on n’associe pas de stratégie de parcours d’arbre au système de transformation, le système peut effectuer les transformations dans n’importe quel ordre ; il faut garantir à l’utilisateur l’unicité du résultat de ses transformations : nous introduisons la notion de Aconfluence.

2. L’existence de plusieurs stratégies de transformation nous amène à déterminer la manière optimale d’opérer les transformations : il est légitime alors d’essayer de trouver un moyen pour éviter les transformations inutiles. En s’inspirant des travaux existants sur les systèmes de réécriture et en utilisant la méthode des GA (évaluation incrémentale cf. la section 2.6), on obtient un algorithme simple trouvant la stratégie optimale.

L’essentiel de notre effort a porté sur la formalisation mathématique de cette idée de cohérence en terme de terminaison et de confluence. Mais il faut bien admettre le point faible de notre approche : la notion de cohérence d’un STAA est indépendante de la stratégie de transformation, ce qui conduit à rejeter beaucoup de STAA intéressants et pratiques, alors que l’utilisateur recherche une stratégie rendant le système cohérent.

3 Participation à des projets européen ou francofrancais

J’ai regroupé dans cette section l’ensemble de mes activitées de recherche qui ont été “vendues” comme justificatif de nos financements externes. J’aimerais souligner ici que la réalisation de notre système Fnc-2 a été l’un de nos atouts (produit phare) pour la participation à ces projets ou contrats.

3.1 Projet Cocos

Avec Antoine Rizk

J’ai participé au projet ESPRIT Cocos (Components for Future Computing Systems) qui s’est déroulé de 1986 à 1988 inclus et regroupait BULL-MTS, BULL-CRG, Olivetti, ICL, Nixdorf, SGS et l’INRIA (en tant que sous-traitant de BULL-MTS). Le but de Cocos était la conception d’une architecture ouverte pour station de travail multi-usages et la réalisation d’un certain nombre de composants matériels et logiciels pour cette architecture.

La réalisation du système Fnc-2 était l’un des composants logiciels que nous proposions et vu l’état d’avancement de notre système cela m’a demandé de fournir une première version très rapidement (version semi-bootstrappée).

Ma participation à ce projet a aussi consisté à aider Antoine Rizk dans la réalisation d’un compilateur et du système d’exécution pour le langage de programmation logique PARLOG à l’aide Syntax et Fnc-2 . Ces travaux sont présentés dans [GJR87].

3.2 Projet MultiWork

Avec Antoine Rizk

Nous avons participé au projet ESPRIT 2105 “MULTImedia WORKstation”, dont les principaux partenaires etait BULL, ICL, Olivetti, Philips et AEG. Notre place dans ce projet était celle de sous-traitant de BULL-MTS.

Le projet (MultiWorks) etait un projet TIP (Projet d’Intégration de Technologies) dont l’objectif etait la conception de stations de travail multimédia à un prix relativement bas.

Le projet possèdait deux axes principaux : un axe matériel basé sur une architecture RISC et un axe logiciel basé sur un système compatible Unix avec une plateforme hypermédia pour développer des applications avancées de gestion de documents multimédia.

Dans la première phase du projet MultiWork qui s’est achevée le 9 novembre 1990, notre travail s’est concentré autour d’un système pour la création d’applications hypermédia. Dans ce cadre, nous avons contribué d’une part à la conception d’un modèle général d’un système hypermédia qui a été adopté par les principaux partenaires de MultiWork, d’autre part à la définition d’un langage de script pour la programmation du système hypermédia.

Ce langage a été implanté dans le cadre du système hypermédia à l’aide des outils Syntax et Fnc-2, sur un environnement SUN/Unix/X11-MOTIF. J’ai aidé Antoine Rizk dans l’utilisation de Fnc-2 pour cette implantation. L’implantation de ce langage a été portée par Bull sur une machine d’Olivetti issue du projet MultiWork: le CP 486.

3.3 Opération Intersem

L’objectif de l’opération Intersem financée par le greco de Programmation qui s’est déroulé d’avril 1989 à décembre 1991, était de proposer une alternative intéressante au bien connu “Synthesizer Generator” [RT84] développé par T. Reps et T. Teitelbaum, en réunissant les compétences des équipes de recherches françaises suivantes :

– nous même, avec les grammaires attribuées et Fnc-2 ;

– le projet croap de G. Kahn avec l’environnement de programmation multi-langgages Centaur [BCD^{+}88];

– l’équipe de P. Franchi-Zannettacci avec le système Gigas [CLFZ88] à l’ESSI de sophia.

De notre côté, nous avons essentiellement travaillé sur le couplage de Fnc-2 et Centaur, et plus précisément sur l’intégration dans Centaur d’évaluateurs d’attributs exhaustifs ou incrémentaux produits par Fnc-2 . Mais c’est aussi la base de notre collaboration sur la traduction de Typol en GA avec I. Attali [Att88], dans le but de proposer une évaluation incrémentale de Typol et aussi une meilleur efficacité en espace mémoire. Une présentation du système Minotaur, résultat de tout ce travail, se trouve dans [AP94].

Ce travail se décompose en les points suivants:

– traduction d’Olga en Le Lisp ;

– génération d’évaluateurs incrémentaux ;

– évolution de nos propres langage de spécification pour unifier les différentes notions (syntaxe abstraite) entre les deux systèmes ;

– travail de formulation en terme de grammaires attribuées de la notion de sous-typage utilisée aussi bien dans les spécifications de syntaxe abstraite Metal qu’en sémantique naturelle (Typol).

– réalisation d’un environnement Centaur pour l’utilisation de Fnc-2 comme outils de démonstration (cf. la section 4.10).

3.3.1 Le traducteur d’Olga en Le Lisp

avec O. Durin

Olga ne fait aucune référence à un langage d’implantation particulier, même si la plupart de ses traits sont hérités de langages bien connus comme Lisp, Modula-2 ou ML. Cette indépendance, tout à fait voulue, permet de le traduire au choix vers plusieurs langages cibles. Le traducteur vers Lisp [Dur89] permet de produire des évaluateurs exhaustifs en Lisp et de les intégrer à une application bâtie sur Centaur (voir le projet croap ). Les évaluateurs produits en Lisp utilisent des services fournis par Centaur (et en particulier le vtp) pour parcourir l’arbre et y accrocher des attributs. Ceci a nécessité le développement de traducteurs entre les langages de Fnc-2 et ceux de Centaur, en particulier asx/atc et Metal.

Cependant le départ d’Olivier Durin^{3} en 1992 a fortement diminuer l’effort que nous pouvons consacrer à cette tâche.

3.3.2 Évaluation incrémentale dans le cadre Fnc-2 et Centaur

avec Christophe Roudet (DEA)

En 1994 , j’ai pu poursuivre notre travail d’intégration de Fnc-2 et du système de construction d’environnements de programmation Centaur développé par le projet croap à l’INRIA–Sophia. En effet, grâce au travail de Christophe Roudet [Rou94a], encadré par Isabelle Attali, j’ai pu valider nos évaluateurs incrémentaux sur une application complète. En effet, il a fallu que je remette à jour dans le générateur d’évaluateur, la version incrémentale que j’avais développé pendant ma thèse (cf. la section 2.6). Le travail de Christophe Roudet consistait à développer un générateur de décompilateurs d’arbres graphiques, dont le langage d’entrée est un sous-ensemble de PPML et qui utilise comme moteur la boîte graphique FIGUE. Grâce à l’emploi de la technologie GA ( Fnc-2 /Lisp et son interface avec Centaur ), les décompilateurs produits peuvent fonctionner de manière incrémentale, ce qui améliore le confort de l’utilisateur dans des applications interactives. De plus Christophe Roudet a utilisé la grande souplesse d’utilisation induite par la séparation entre le contrôle sémantique et la méthode de réévaluation (cf. la section 2.6). Enfin il s’est très largement inspiré de notre travail sur ppat (cf. la section 4.6), enutilisant la même méthode et architecture logicielle.

3. Personnellement, j’ai rencontré de grande difficultés avec Olivier pour sa thèse. Il n’arrivais pas à ce concentrer plus de 15 jours sur un sujet donné.

3.3.3 La traduction de Typol en GA

avec I. Attali

J’ai regroupé ici l’ensemble des problèmes que nous avons rencontré avec I. Attali dans la traduction de Typol en GA. Notre collaboration a dépassé d’ailleurs largement les relations client–fournisseur pour se placer aussi sur un plan plus théorique.

Sans reprendre nos longues discutions avec I. Attali, la traduction de Typol en GA, n’a pas été aussi simple que l’on pouvait l’imaginer au départ et deux à trois années plus tard Dephine Terrasse [Ter95] a rencontré des problèmes analogues^{4} dans la conception de l’interface Typol et Coq (du projet Coq INRIA/Rocquencourt).

L’un des plus importants a été certainement la notion d’inclusion de phylum (notion de sous-type), surtout que le typage était, aussi bien pour le langage Metal (le VTP) que pour le langage Typol (traduit en prolog), un mécanisme dynamique (résolu à l’execution). Mais je dois tout de même admettre que cela a permis de faire évoluer avantageusement mes travaux de recherche sur les GAs et le développement de Fnc-2 sur les points suivants :

– l’élimination de la séparation du domaine syntaxique et du domaine sémantique dans les GA ;

– l’introduction de la notion de surcharge d’opérateur comme une solution au problème d’inclusion de phyla. J’ai aussi utilisé cette notion pour la traduction fsdl vers asx dans le cadre du projet Compare (cf. la section 3.4.1)

– motivation pour la notion de Grammaire Attribuée Dynamique (cf. la section 2.10).

avec Philippe Rouzier (DESS) [Rou93]

Par ailleurs, nous avons travaillé sur une meilleure intégration au niveau lexico-syntaxique, selon deux axes [Rou93]. D’une part, nous avons remplacé le constructeur Yacc initialement utilisé dans Centaur par notre propre constructeur Syntax, tout en conservant les langages de description de Centaur (metal, ppml). Ainsi, les analyseurs incrémentaux utilisés dans Centaur disposent d’un mécanisme de récupération d’erreurs très agréable et n’échouent plus à la première erreur rencontrée. D’autre part, nous avons, grâce au protocole de construction d’arbre proposé dans Centaur, établi une interconnexion entre ce dernier et les analyseurs engendrés à partir de nos propres spécifications de construction d’arbre abstrait (langage atc). L’intérêt de ce travail est de fournir à l’utilisateur de Fnc-2 le même langage atc dans le contexte de Centaur. Ceci nous facilitera grandement la tâche de développement avec Centaur d’environnements de programmation pour nos propres langages, en particulier Olga.

4. d’après une journée de discutions, mais rien de très formel.

3.4 Le projet ESPRIT Compare

Le projet ESPRIT 5399 Compare (COMpiler generation for PARallel machinEs ) a démarré le 01.01.1991. Outre nous-mêmes, ce projet regroupait le CWI (Pays-Bas), le GMD (R.F.A.), Associated Computer Exports ACE (Pays-Bas, coordinateur), Harlequin (Royaume-Uni), STERIA (France) et, en tant que partenaire associé, l’Université de Sarre (R.F.A). Il disposait d’une force de travail d’environ 100 hommes / années sur quatre ans, et la part de l’INRIA correspondait à trois personnes à temps plein.

Le but de Compare était de développer un certain nombre de générateurs produisant, à partir de spécifications de haut niveau, des (parties de) compilateurs pour des langages plus ou moins classiques et des machines disposant d’un certain degré de parallélisme (RISC et superscalaires essentiellement). Ces moteurs communiquent entre eux à travers une représentation intermédiaire et sont dirigés par un superviseur; la RI (représentation intermédaire), son interface vis-à-vis des moteurs et le superviseur forment ensemble le système de compilation (Cosy ) de Compare . Cosy autorise une très grande diversité dans la conception et la réalisation de la communication entre les divers moteurs, depuis un enchaînement séquentiel sur un monoprocesseur jusqu’à une coopération entre moteurs incrémentaux sur une machine parallèle. Le lecteur trouvera un bonne et courte présentation de Cosy dans [Con95].

Notre participation à Compare a consisté essentiellement en l’adaptation de nos systèmes Pagode et Fnc-2 à Cosy et en particulier à son langage de description de RI, fsdl [Con94a] (langage de définition des structures), et à la ccmir (Common Compare Medium-level IR ), ainsi qu’en la production à l’aide de Pagode un générateur de code pour le processeur SuperSPARC. Je noterais que Fnc-2a été choisi par le Consortium Compare[Con91] comme le meilleur système de grammaires attribuées parmi d’autres systèmes concurrents.

En 1992, ma participation a été consacrée au compilateur de démonstration du mini-langage CLaX pour le SPARC. J’ai organisé en catastrophe^{5} la réalisation d’un traducteur du niveau de la RI qui est proche du langage source (HIR), produit par la partie frontale du compilateur, vers le niveau intermédiaire (MIR), sur lequel peuvent travailler des moteurs indépendants des langages source et objet (allocateur mémoire, optimiseurs divers) et qui est le langage d’entrée du générateur de code. Ce compilateur de démonstration m’a permis de mieux comprendre le modèle Cosy, du moins dans ses aspects “structures de données” (fsdl, description de la RI) et “ingéniérie” (intégration de moteurs développés indépendamment chez différents partenaires). J’ai été le premier à faire cette expérience pour le projet Compare et quasiment le seul dans l’équipe à comprendre vraiment le modèle Cosy.

5. Juste un mois avant la revue, notre ingénieur expert a avoué son échec dans la réalisation de cette tache.

Enfin, j’ai aidé François Thomasset dans le développement d’un analyseur d’un sous-ensemble de Fortran à l’aide de Syntax et Fnc-2 . C’était sa première utilisation de Fnc-2 .

En 1993, une nouvelle version du plan de travail a été mise au point par le consortium et adoptée par la Commission Européenne. L’ensemble des partenaires étaient largement en retard sur le planning, en particulier la tache sur la définition et l’implantation du langage de description fsdl (élement important pour la plate forme Cosy). Six mois avant la deuxième revue (février 94) du projet Compare après un tour de table dans l’équipe, je me ne suis rendu compte que nous étions très largement en retard vis-à-vis du plan de travail. En particulier, le méta-générateur de code Pagode (qui devait être livré lors de cette deuxième revue), était à un stade de développement très embryonnaire, cela indépendamment de l’adaptation à Cosy .

3.4.1 Compare : un travail en équipe

En employant résolument une méthode de travail d’équipe (j’ai utilisé mon expérience dans le développement de Fnc-2 voir la section 4.1), j’ai organisé et participé à notre effort très important de développement et d’ingénierie sur les points suivants :

– Adaptation du système Fnc-2 à Cosy ; En gros, j’ai quasiment refait le même travail que pour le traducteur Lisp (cf. la section 3.3.1). Mais en plus j’ai rencontré les deux difficultées suivantes :

– La définition du le langage fsdl et son implantation ont été vraiment définitif qu’en fin d’année 1993. Par l’exemple le choix de C comme langage d’implantation n’a été décidé qu’en fin mai 1993.

– Le langage fsdl est un langage de description de structure avec en plus, un nommage explicite des champs, des notions d’héritages, de surcharge de constructeur, d’extensions (ajout de champs) et enfin une notion de foncteur. Mon travail a consisté à définir une traduction des spécifications fsdl en des spécifications asx , qui n’a pas été aussi simple que prévu initialement.

– Réalisation du système Pagode en terme d’un vrai méta-générateur de code. En six mois, j’ai organisé et largement participé au travail du sousgroupe Pagode qui à partir d’un ensemble de programmes (algorithmes) a construit une vraie première version de leur méta-générateur de code Pagode. Certes il restait encore beaucoup de travail à partir de ce premier prototype présenté lors de la revue (février 94), mais c’était une base solide pour les futurs développements et travaux de recherche du projet.

Je noterai juste que cela a représenté 50.000 lignes de code assemblé en six mois [Con94b].

– Adaptation du système Pagode à Cosy, et en particulier à son langage de description de RI, fsdl, et à la ccmir (Common Compare Medium-level IR).

– Intégration et réalisation des premiéres tests sur la plate forme (le framework). Cette étape n’a pas été une mince affaire étant donné l’état d’avancement de la plateforme Cosy et des outils de distribution de cette dernière (réception et distribution par le logiciel cadese des arbres de référence contenant l’ensemble des développements de tous les partenaires du projet Compare ).

En 1994-95, le projet Compare m’a demandé d’organiser et de participer fortement à notre effort de développement et d’ingénierie très important, aux dépens d’un certain ralentissement de mes travaux de recherche sur les grammaires attribuées. Mais avec le peu de temps “tranquille” qu’il me restait, j’ai très honorablement poursuivi mes recherches sur les GA ( [Rou94b, Dur94, PDRJ96] avec les soutenances de thèse de G. Roussel [RPJ94] et B. Marmol [Mar94]).

Pour moi, l’objectif initial de tous ces efforts était presque atteint : l’équipe compilation pure et dure disposait maintenant d’une chaîne de compilation complète qui permettait d’implanter et de tester facilement^{6} leurs futurs travaux de recherche et de les valider sur des exemples réels. En outre, la disponibilité du modèle Cosy permettait d’imaginer de nouveaux algorithmes d’analyse de programme qui pouvait aboutir à la production de code objet encore plus efficace.

3.4.2 Interface avec la plate-forme de compilation Cosy

Pour la revue finale (mars 95), j’ai dû consolider notre interface entre Fnc-2 et la plate-forme Cosy — la base des développements dans Compare , —, essentiellement sur les points suivants :

– mise en place d’une structure de distribution conforme à Cosy , en utilisant le logiciel de gestion de configuration cadese choisi par le consortium Compare ;

– création d’un outil de visualisation des structures utilisées en utilisant le logiciel VCG ;

– écriture d’un outil de création automatique, à partir des spécifications d’entrée de Fnc-2 , des spécifications fsdl (langage de définition des structures) et des vues associées, nécessaires à la plate-forme Cosy ;

– enfin, réalisation de l’intégration complète dans la version finale de la plate-forme Cosy qui contenait vraiment toutes les fonctionnalités prévues, comme par exemple la véritable notion de vue, spécification des enchaînements des divers moteurs avec le langage EDL (Engines Description Language).

6. avec une forte visibilité vis-à-vis d’autre partenaires ou équipe de recherche

Cela m’a demandé un effort de travail intense sur quelques mois, mais cela a montré que notre choix d’utiliser Fnc-2 pour intégrer nos outils de compilation comme Pagode était très judicieux : Pagode lui-même est totalement indépendant de Cosy , toute l’interface étant réalisée à travers Fnc-2 . Par ailleurs, avec Olga et Fnc-2 , nous offrons à la plate-forme Cosy un vrai langage de programmation au dessus du langage de description de structures fsdl . Mais le grand intérêt de cette approche, est de rendre notre développements (la partie écrite en Olga) relativement indépendante de la plate forme Cosy. En effet, graçe aux différents traducteurs de Fnc-2(en particulier le couplage avec Centaur) il est possible d’effectuer un transfert de notre développement dans un autre contexte d’utilisation que Cosy .

3.4.3 Bilan du projet Compare

En conclusion, j’aimerais insister sur la caractéristique importante de ce projet qui a été une réelle réalisation logicielles en commun, grâce à la plate forme Cosy dans l’implantation d’une famille de compilateurs (au nombre de trois et pour trois type de machines lors la revue finale). Sans trop me tromper, je pourrais dire qu’une telle réalisation logicielle partagée de cette ampleur (100 x 4 années hommes) à travers un projet Esprit est assez exceptionnel (rare). Je noterais aussi la remarque (expérience acquise) de Martijn de Lange^{7} lors de son discours de conclusion et de remerciement lors de la revue finale qui disait en substances : pour aboutir à ses propres objectifs, il faut parfois bousculer (avoir une forte volonté) ses collègues et partenaires et surtout ne pas expliquer ces échecs en responsabilisant les autres partenaires. Je suis obligé d’avouer que je ne suis retrouvé quasiment tout seul (a avoir cette même volonté d’y arriver, prendre les décisions importantes, organiser le travail de l’équipe, etc…) face aux objectifs alors que l’équipe était composé d’au moins sept personnes confirmées (sur poste, sans les stagiaires et thésards). Je rappellerai que ce projet a quand même permis le financement de deux thèses INRIA complètes, des compléments de bourses, d’achat de machines et de nombreuses missions. Notre engagement correspondait à trois personnes à temps plein. J’avais espéré trouver à travers notre participation au projet Compare un fort soutient pour le développement de Fnc-2 (en faire un produit industriel) mais cela n’a absolument pas été le cas, bien au contraire.

Pour finir sur une note plus positive, je reste tout de même farouchement convaincu que l’approche du modèle Cosy va dans le bon sens en tant qu’outils coopératif et générique et j’espère que mon travail autour de l’adaptation de Fnc-2 portera dans un très proche avenir ses fruits. Je sais que depuis quelque temps le modèle Cosy obtient auprès des industriels un certain succès.

7. Le grand responsable du projet Compare , patron de ACE.

4 Implantation et développement de Fnc-2

J’ai placé sous cette section un ensemble de travaux autour du développement de Fnc-2 effectué par moi-même ou par des stagiaires que j’ai exclusivement encadré.

4.1 Mise en place d’outils de développement partagé

A partir de la première version de Fnc-2 , j’ai conçu, au cours de l’année 1990, une méthode de travail pour permettre le développement à plusieurs de notre système Fnc-2 en utilisant l’outil sccs (the Source Code Control System) de gestion de version. Après quelques erreurs de jeunesses et tentatives j’ai donc conçu une méthodologie de développement en équipe de notre système Fnc-2 , qui me permet maintenant d’offrir aux nouveaux arrivants un environnement leur permettant d’ajouter très rapidement et facilement leur propre développement à Fnc-2 . Cette expérience m’a bien été utile pour le développement de Pagode sous Cosy (cf. la section 3.4.1). J’ai quasiment utilisé les même outils qui (je dois l’avouer), en terme de fonctionnalités, remplacent très avantageusement le logiciel cadese que nous avons payé fort cher à notre partenaire ACE.

4.2 Évolution des langages de spécification de Fnc-2

4.2.1 Le langage Olga et son analyseur

En 1986, nous avons confié à J. Bonnet [Bon86] une étude préliminaire sur les langages existants pour la spécification de GA. Cette étude nous a permis par la suite de jeter les bases de notre nouveau langage Olga. En 1987, C. Ayrault a travaillé sur la traduction en C du langage Olga [Ayr87].

À partir de 1990, les langages de spécification (Olga , asx , atc ) de Fnc-2 ont subi un ensemble d’améliorations, ou d’importantes modifications dans le but de répondre aux demandes des utilisateurs (Centaur et Compare) et pour la facilité d’expression des GA. Cela a nécessité de modifier une bonne part des composants du système Fnc-2 . Je donne ici une liste non-exhaustive de ces différentes modifications :

– élimination de la séparation entre le domaine syntaxique (les arbres) et le domaine sémantique (les attributs) (cf. la section 3.3.3) ;

– permettre d’utiliser une GA comme une fonction à part entière, en particulier depuis une règle sémantique d’une autre GA ;

– introduction de la notion de surcharge d’opérateur comme une solution au problème d’inclusion de phyla (cf. les sections 3.3.3 et 3.4.1) ;

– introduction de la notion de nommage des champs dans une spécification asx (cf. la section 3.4.1) ;

– introduction des notions de schéma de production et de production conditionnelle (cf. la section 2.10). avec C. Le Bellec (DEA [Le 89])

En 1990 avec C. Le Bellec, nous avons implanté le mécanisme étendu de construction automatique des règles sémantiques non explicitement spécifiées, qui permet maintenant de construire des règles non triviales à partir de “modèles” génériques décrivant des classes d’attributs.

4.3 Le constructeur d’arbres abstraits atc

avec C. Zylberman stage de l’École Télécom [Zyl90]

atc est une interface entre Fnc-2 et un générateur d’analyseurs lexicosyntaxiques comme Syntax. Une spécification pour atc est une grammaire non contextuelle augmentée par des règles de construction d’arbres attachées aux productions.

La première incarnation d’atc a été construite au dessus de Syntax. Pour éviter de lier la diffusion de Fnc-2 à celle de ce dernier, nous avons développé une seconde incarnation d’atc au dessus d’un système similaire à Syntax mais dont la diffusion est beaucoup plus large : le couple Lex–Yacc, disponible gratuitement sur toutes les machines Unix. Cette seconde implantation d’atc a été réalisée en moins de trois mois par C. Zylberman [Zyl90]. Il faut noter que cette étudiante ne connaissait en arrivant ni les GA, ni Fnc-2 , ni atc; son travail montre donc l’efficacité des GA et de Fnc-2 en tant qu’outil de développement.

4.4 Glaneur de cellules

avec D. Devillard (DEA [Dev90])

Le code que Fnc-2 produit est assez gourmand en mémoire, essentiellement à cause de l’absence d’un “glaneur de cellules” qui permettrait de profiter pleinement des optimisations décrites dans la section 2.5. Dans le cadre de son stage de DEA [Dev90], nous avons donc chargé D. Devillard d’effectuer une étude de plusieurs implantations en C de langages voisins d’Olga et d’en tirer des méthodes permettant de définir une nouvelle implantation d’Olga en C, comportant en particulier un glaneur de cellules. Le résultat de cette étude est très proche des travaux d’A. Appel sur ML. Cependant ces propositions ne sont pas encore implantées dans Fnc-2 , et cette implantation demandera encore un certain temps. En 1991, R. Gomez a commencé l’implantation du glaneur de cellules à recopie dans les évaluateurs produits en C [Gom91], en se fondant sur les travaux de D. Devillard.

4.5 Compilation du filtrage d’arbres

avec P. Bazet (DEA [Baz92])

Nous avons élaboré un nouvel algorithme de compilation du filtrage d’arbres avec règle de priorité spécifique et nœuds d’arité variable décrits par des constructeurs commutatifs [Baz92]. Ces deux caractéristiques distinguent ce travail de ceux qu’on trouve habituellement dans la littérature.

A partir des modèles d’entrée, cet algorithme produit une représentation intermédiaire dans laquelle chaque modèle d’entrée est représenté par un ou plusieurs modèles incompatibles, ce qui permet de se ramener au cas de modèles d’arité fixe. Ensuite, il construit un arbre de décision représentant les différentes étapes du filtrage, optimisé pour minimiser le temps d’exécution. En particulier, à chaque étape de filtrage où c’est possible, il détermine un index, c’est-à-dire un des fils du nœud courant qu’il faut absolument examiner pour déterminer quel modèle filtre l’arbre. La méthode employée est une amélioration et une adaptation à la priorité spécifique de celle de Puel et Suarez. Nous conjecturons que ce nouvel algorithme est au moins aussi efficace en temps et en place que ses prédécesseurs.

Cet algorithme a été encapsulé dans un module aux interfaces bien définies et faciles à utiliser, écrit en C. Ce travail forme la base du micro-système de transformation d’arbres que nous avons développé dans le cadre du projet Compare mais n’est pas limité à cette application.

4.6 Le générateur de décompilateurs ppat

avec J.P Jouve (stage d’option de l’École Polytechnique [Jou91])

ppat est un générateur de décompilateurs d’arbres attribués similaire à PPML (celui de Centaur) mais capable en plus de traiter les valeurs d’attribut. La conception de ppat avait été l’objet du stage de DEA d’E. Planes [Pla89] en 1989. L’année 91 en a vu la réalisation complète [Jou91]. Outre l’utilité de ppat en tant que tel, cette réalisation a été très enrichissante pour nous car elle constitue une des premières grosses applications de Fnc-2 à avoir été effectuée par un utilisateur extérieur au petit cercle des développeurs de Fnc-2 . Ce fut un succès total : en trois mois et alors qu’il ne connaissait pas Fnc-2 du tout, J.-P. Jouve a écrit, mis au point et testé plus de 8000 lignes d’Olga et autres langages, réparties en plus de 15 fichiers. Il a ainsi validé l’utilisabilité du système et les concepts dont nous nous étions fait le héraut : modularité, réutilisabilité, etc.

4.7 Interface graphique pour Fnc-2

avec Bernard Amilien en 92-93 [Ami92, Ami93]

Jusqu’à présent l’utilisateur qui devait construire une grosse application à l’aide de Fnc-2 était aidé par un shell-script qui vérifiait la présence des fichiers source requis, contrôlait leurs dépendances et assurait l’enchaînement des divers constructeurs ; ce programme dialoguait avec l’utilisateur à travers une interface textuelle assez frustre. En 92 B. Amilien [Ami92] a réalisé une version graphique de ce programme Xfnc2 tournant sous X-Window. Les indications de l’utilisateur sont données par sélection dans des menus et les messages produits par les divers constructeurs sont dirigés vers une fenêtre déroulante. L’accès aux services de Fnc-2 est ainsi encore plus simple que précédemment.

En 1993, nous avons poursuivi notre effort sur les supports pour faciliter l’utilisation de Fnc-2 en réalisant un autre outil graphique Xvisu [Ami93]. Cet outil est une interface graphique pour notre test de circularité dans une GA [PDRJ96], qui permet de visualiser d’une manière graphique des portions d’une GA — plus précisément les graphes de dépendances entre les attributs — et de se déplacer interactivement dans la GA, en se souvenant des productions visitées, pour y rechercher la ou les règles sémantiques “fautives”. Ainsi à l’aide d’un protocole sur les graphes de dépendances le système de trace de circularité interagis avec l’utilisateur à travers une interface graphique. Le choix d’utiliser un protocole est largement inspiré des travaux de projet croap autour de système Sophtalk, pour un éventuel interfaçage comme pour atcCentaur (cf. la section 3.3.3). J’ai donc remis à jour (recodé) le test de circularité que j’avais défini lors de mon stage de DEA en 1985 [PDRJ96]. Il est aussi possible d’utiliser cette même interface comme browser, pour visualiser simplement et graphiquement les dépendances dans une GA sans qu’il y ait forcément de circularité.

4.8 Le traducteur vers Caml

avec Gilles Le Bâtard stage de maîtrise [Le 95]

Pour améliorer la diffusion de Fnc-2 , nous lui avons ajouté un nouveau traducteur (générateur de code) qui produit du code Caml [Le 95]. L’objectif de ce travail est double. Premièrement, cela va permettre d’étendre le champ d’application de Fnc-2 et d’en faire un complément intéressant aux systèmes de programmation fonctionnelle comme Caml et Caml-Light. Par ailleurs, et surtout, cette traduction nous sera très utile pour valider les travaux décrits dans la section 2.12.1.

Pour faciliter l’intégration du code Caml produit par Fnc-2 dans une application écrite en partie en Caml, nous avons pris lors de cette traduction les hypothèses suivantes:

– Les GA décrites sont des GAs purement fonctionnelles, sans effet de bord sur la structure arborescente. Les GA procédurales, qui modifient les arbres en les décorant, ne peuvent être prises en compte dans cette traduction.

– La définition de la structure arborescente est totalement libre, à la charge de l’écrivain, afin d’être indépendante de nos techniques de GA. L’écrivain doit juste décrire ses structures sous le format asx pour que Fnc-2 puisse travailler.

Dans son état actuel, ce traducteur traite la quasi-totalité de notre langage Olga , en particulier toute la partie description de GA. De plus, pour faciliter l’intégration, nous avons écrit un petit traducteur asx to ml d’une spécification d’arbre en asx vers une collection de types concrets en Caml.

4.9 Quelques autres utilisations de Fnc-2

Dans cette section, j’ai regroupé un ensemble d’utilisations de Fnc-2 dont je n’ai pas encore parlé et qui ont fait l’objet d’un rapport écrit (au moins pour certain d’autre eux) ou d’une certaine collaboration (mail électronique).

– Première évaluation d’utilisation de Fnc-2 pour l’enseignementà INRIA/Lorraine [LNP90] ;

– Utilisation de Fnc-2 pour Pascal [Dur88, Ben93] ;

– Utilisation de Fnc-2 pour la définition de protocole de communication [And95] ;

– Utilisation de Fnc-2 pour E-LOTOS[Viv96] ;

– Utilisation de Fnc-2 pour un mini-JAVA ;

4.10 Diffusion des résultats et distribution

Lorsque Fnc-2 a été opérationnel (1990) nous nous sentions plus à l’aise pour en parler publiquement. Donc en 1990 nous avons accompli un très important effort de diffusion des résultats en publiant plusieurs communications sur différents aspects du système [JPJ^{+}90, JP90b, JP90a]. Cependant, une partie importante de mes efforts en 1990 a été consacrée à l’obtention d’une version distribuable de Fnc-2 (par FTP, permettant au moins une évaluation de ses possibilités. Mais je dois admettre que j’ai mis un certain temps à convaincre l’auteur du logiciel Syntax, de me permettre de distribuer une version simplifié de Syntax (c’est un produit payant pour les industriels) dans la distribution de Fnc-2 .

Nous avons aussi effectué un effort de documentation par la mise à jour du manuel de référence [JP] de Fnc-2 (mais pas autant qu’il le faudrait), comme l’ajout d’un guide de première utilisation avec l’outil graphique xfnc (cf. la section 4.7).

En 1992, avec l’environnement Centaur j’avais pu concevoir une présentation (démonstration) de Fnc-2 que j’ai en particulier présenté aux 25^{ème} anniversaire de l’INRIA avec I. Attali et aux journées GRECO programmation à Toulouse [AP92]. Mais comme l’essentiel de cette présentation était réalisé par moi-même, il m’a été difficile de suivre les diverses évolutions (versions) du système Centaur par la suite.

4.10.1 Diffusion de nos résultats à travers le “WEB”

A partir de 1996, j’ai choisi le WEB comme moyen de diffusion de nos résultats en particulier sur les points suivants :

   – À l’adresse http://www-rocq.inria.fr/oscar/FNC-2/index.html ;

– Page d’accueil sur la recherche sur les Grammaires Attribuées (liste de personne, liste des principaux sujets etc…) ;

– Maintenance de notre bibliographie sur les Grammaires Attribuées (plus de 950 références [PJ] ;

– Accès à nos publications et à notre logiciel Fnc-2 .

Actuellement, je pense avoir abouti à quelques résultats qui permettront dans l’avenir (je l’espère) de rompre un peu l’isolement de la communauté des grammaires attribuées (pas de conférence vraiment spécialisée pour le domaine). Personnellement, ce moyen de communication m’a permis de découvrir plusieurs travaux de recherche sur les GAs.

5 Supports techniques et organisation d’un important groupe de recherche

Ppour que les choses se passent au mieux, une équipe de recherche de l’importance (en nombre de personnels) que nous avions atteint lors du projet Compare induit forcément un ensemble de taches communes (rapport d’activité, support logiciels, achat de machines et taches administratives que Martin Jourdan a assuré avec brio). Je dois admettre (hélas !) que depuis la création du projet ChLoE, le groupe Grammaires Attribuées (en particulier Gilles Roussel et Bruno Marmol) a assuré quasiment toutes les charges communes d’une importante équipe de recherche. En particulier, lors de la création du projet ChLoE en 91, j’ai assuré avec Martin Jourdan (tous les deux pendant les 2 premières années, après Gilles et Bruno nous ont bien aidé) les taches d’ingénieur système pour un ensemble de 25 machines avec environ 30 utilisateurs qui contenait au départ le sous-groupe programmation logique du bâtiment 8. Pour essayer d’alléger notre tache, j’ai travaillé sur la mise en place d’un protocole d’installation des machines^{8}, des logiciels et surtout d’un environnement (X-windows) partagé identique pour tous, pour nous éviter de répondre 30 fois aux mêmes questions des utilisateurs (à chaque modification du serveur). En d’autres termes, le groupe Grammaire Attribuée formait le noyau dur (une vrai équipe) de l’axe compilation (forte collaboration, entre-aide) qui, de mon point de vue, facilite grandement les échanges scientifiques. L’expérience du projet Compare ne fait que me convaincre encore plus de la justesse de mon approche.

6 Conclusion

Pour conclure sur les qualités du générateur d’évaluateurs , j’énoncerai deux remarques sur notre propre expérience en tant qu’utilisateurs du système (l’ensemble de la carrosserie, le front-end du langage Olga et les traducteurs — C, Le Lisp, fsdl, Caml — sont spécifiés en GA :

8. c’était aussi les années du passage de Sun3 à Sun4

– Lors d’une génération du système, c’est la compilation des objets C engendrés qui prend le plus de temps, et non leur construction proprement dite. Ceci montre une très grande efficacité en temps, d’une part lors de la construction des évaluateurs, et d’autre part lors de leur exécution.

– Enfin, depuis la sortie de la première version de Fnc-2 en 1990, il a été fortement utilisé au sein de notre projet (environ 75 000 lignes de code pour le développement autour de Fnc-2 et 50 000 pour le projet ESPRIT Compare ).

En conséquence, j’ai encadré personnellement de nombreux utilisateurs et même s’ils ont accaparé beaucoup de mon temps, ils m’ont permis de tester Fnc-2 à fond et de confirmer nos choix sur Olga. En effet, il apparaît que la majorité de leurs erreurs sont détectées à la construction (statiquement), et celles qui peuvent rester sont dûes principalement à leur manque d’expérience d’utilisation du langage Olga (surtout sur les fonctionnalités peu classiques du langage).

Nous sommes convaincus que nous avons atteint à travers la réalisation de Fnc-2 , notre objectif de départ. En effet, les très bonnes qualités de la méthode des GA — spécifications déclaratives et structurées — étaient masquées par les problèmes d’exécution et de langage de spécification qui n’avaient pas reçu jusqu’ici de solution satisfaisante. Notre système propose donc une solution satisfaisante, comme le montrent nos propres résultats, et permet donc enfin, de rendre à la programmation par GA ses qualités.

Pour conclure, je ferai référence à l’excellent survey sur les grammaires attribuées [Paa95] ou l’auteur mentionne très explicitement les grandes qualités de notre système Fnc-2 (les motivations de réaliser un tel système pour promouvoir les AGs), mais surtout il est pour moi un appui (justification) à mon programme de travail pour les années à venir qui fait l’objet d’un document séparé.

7 Encadrement de stagiaires

Dans cette section je ne ferais que redonner la liste des stagiaires que j’ai encadré en précisant l’année de leur stage et pour les thèse l’année de la soutenance puisque j’ai déjà présenté et décris leur travaux par sujets (voir au dessus). Ici je voudrai encore insister sur le fait que j’ai assuré la plus grande partie du travail d’encadrement des stages et des thèses car je suis tout simplement favorable à un encadrement réel et soutenu des stagiaires. En effet, je suis convaincu que par ce fort échange de point de vue, les stagiaires ont fortement collaboré et participé à l’évolution de mes recherches.

– En 1986

– J Bonnet (DEA d’Orléans) ;

– C. Julié (DEA d’Orléans) ; – En 1987

– C. Ayrault (DEA d’Orléans) ;

– A. Souah (DEA d’Orléans) ;

– Début de la thèse de C. Julié ;

– En 1988 – O. Durin (stage d’option de l’École Polytechnique)

– S. Taouil (DEA d’Orléans) ;

– En 1989 – O. Durin (DEA);

– E. Planes (DEA d’Orléans) ;

– C. Le Bellec (DEA d’Orléans) ;

– Soutenance de thèse de C. Julié ;

– En 1990 – C. Zylberman (telecom) ;

– B. Marmol (DEA d’Orléans) ;

– D. Devillar (DEA d’Orléans) ;

– Début de thèse de C. Le Bellec ;

– Début de thèse de O. Durin (École Polytechnique) ;

– Soutenance de thèse de A. Souah ;

– En 1991 – Début de la thèse de Bruno Marmol ;

– J.P Jouve (stage d’option de l’École Polytechnique) ;

– R. Gomez (DEA)

– En 1992 – P. Bazet (DEA) ;

– Bernard Amilien ;

– Début de la thèse de Gilles Roussel ;

– En 1993 – Philippe Rouzier ;

– Bernard Amilien ;

– Hervé Benvel (DEA) ;

– Soutenance de thèse de C. Le Bellec ; – En 1994

– Christophe Roudet ;

– Étienne Duris (DEA d’Orléans) ;

– soutenance de la thèse de Bruno Marmol ;

– soutenance de la thèse de Gilles Roussel ;

– En 1995 Gilles Le Bâtard ;

– En 1996

– Stéphane Leibovitsch (DEA sémantique et preuves) ;

– Loïc Correnson (stage d’option de l’École Polytechnique) ;

– Début de la thèse d’Étienne Duris ;

8 Enseignement

Depuis 1989, j’assure en tant que Chef de travaux pratiques en exercice partiel (stagiaire les deux premières années) à l’École Polytechnique, les travaux dirigés du cours d’informatique du tronc commun, et du cour de compilation de la majeure “informatique fondamentale et application” dirigé par P. Cousot. Cela représente environ 70 heures de travaux dirigés sur l’année.

Références

[AM91] Henk Alblas and Bor̆ivoj Melichar, editors. Attribute Grammars, Applications and Systems, volume 545 of Lect. Notes in Comp. Sci. Springer-Verlag, New York–Heidelberg–Berlin, June 1991. Prague.

[Ami92] Bernard Amilien. Interfaces graphiques interactives sous XWindows pour le système de traitement de grammaires attribuées Fnc-2. Rapport de stage, Institut d’Ingéniérie Informatique de Limoges, September 1992.

[Ami93] Bernard Amilien. Réalisation d’un complément interactif de trace de circularité dans le compilateur de grammaires attribuées Fnc-2. Rapport de stage de fin d’études, Institut d’Ingéniérie Informatique de Limoges, 1993.

[And95] Laurent Andrey. Protocoles de communication et grammaires attribuées. PhD thesis, Université de Mancy, 1995.

[AP92] Isabelle Attali and Didier Parigot. Centaur et fnc-2 : un génénérateur d’environnements de programmation. In CNRS département SPI, editor, Rencontre recherche en informatique industrie, July 1992.

[AP94] Isabelle Attali and Didier Parigot. Integrating Natural Semantics and Attribute Grammars: the Minotaur System. Rapport de recherche 2339, INRIA, 1994.

[Att88] Isabelle Attali. Compiling typol with attribute grammars. In Pierre Deransart, Bernard Lorho, and Jan Maluszynski, editors, Programming Languages Implementation and Logic Programming, volume 348 of Lecture Notes in Computer Science, pages 252–272. Springer-Verlag, New York–Heidelberg–Berlin, May 1988. Orléans.

[Ayr87] Christine Ayrault. Implantation en C des structures de données du langage OLGA. rapport de DEA, University d’Orléans, September 1987.

[Baz92] Philippe Bazet. Pattern-matching en priorité spécifique sur des types avec constructeurs commutatifs. Rapport de DEA, Université de Paris 11, Orsay, September 1992.

[BCD^{+}88] Patrick Borras, Dominique Clément, Thierry Despeyroux, Janet Incerpi, Gilles Kahn, Bernard Lang, and Valérie Pascual. Centaur: the system. SIGSOFT Software Eng. Notes, 13(5):14–24, November 1988.

[Ben93] Hervé Benvel. Réalisation d’un front-end pascal avec le système FNC-2. Rapport de DEA, Université de Paris 6, September 1993.

[Bon86] Joël Bonnet. Étude des principaux langages de description de grammaires attribuées et spécification d’un nouveau langage basé sur des grammaires abstraites. rapport de DEA, University d’Orléans, September 1986.

[CLFZ88] Bruno Chabrier, Vincent Lextrait, and Paul Franchi-Zannettacci. GIGAS: a graphical interface generator from attribute specifications. In Actes des Journées Int. “Le Génie Logiciel et ses Applications”, pages 1265–1283. EC2, Paris, December 1988. Toulouse.

[Con91] The COMPARE Consortium. Repport of toolselection taskforce. draft, Compare Consortium, august 1991. confidential.

[Con94a] The COMPARE Consortium. fsdl. draft, Compare Consortium, novembre 1994. confidential.

[Con94b] The COMPARE Consortium. Using pagode and fnc-2 in compare. draft, Compare Consortium, july 1994. confidential.

[Con95] The COMPARE Consortium. Cosy compilers overview of their construction and operation with glossary, list of acronyms and index. draft, Compare Consortium, march 1995. confidential.

[Cor96] Loïc Correnson. Généricité dans les grammaires attribuées. Rapport de stage d’option, École Polytechnique, 1996.

[Dev90] David Devillard. Amélioration de l’implantation en C des évaluateurs d’attributs produits par FNC-2. Rapport de DEA, Université d’Orléans, September 1990.

[DJ90] Pierre Deransart and Martin Jourdan, editors. Attribute Grammars and their Applications (WAGA), volume 461 of Lecture Notes in Computer Science. Springer-Verlag, New York–Heidelberg–Berlin, September 1990. Paris.

[DPJ95] Etienne Duris, Didier Parigot, and Martin Jourdan. Mises à jour destructives dans les grammaires attribuées. Rapport de recherche 2686, INRIA, October 1995.

[DPRJ96a] Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Attribute grammars and folds: Generic control operators. Rapport de recherche 2957, INRIA, August 1996.

ftp://ftp.inria.fr/INRIA/publication/RR/RR-2957.ps.gz.

[DPRJ96b] Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Grammaires attribuées et folds: Opérateurs de contrôle Génériques. In journées du GDR de programmation, Orléans, 1996.

[DPRJ97] Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Structure-directed genericity in functional programming and attribute grammars. Rapport de Recherche 3105, INRIA, February 1997.

[Dur88] Olivier Durin. Traduction en OLGA d’une grammaire attribuée écrite en lisp. rapport de stage d’option, École Polytechnique, Palaiseau, July 1988.

[Dur89] Olivier Durin. Génération en le lisp d’évaluateurs d’attributs spécifiés en olga. rapport de magistère, École Normale Supérieure, Paris, September 1989.

[Dur94] Etienne Duris. Transformation de grammaires attribuées pour des mises à jour destructives. Rapport de DEA, Université d’Orléans, September 1994.

[Fil86] Gilberto Filé. Classical and incremental attribute evaluation by means of recursive procedures. In Paul Franchi-Zannettacci, editor, 11th Coll. on Trees in Algebra and Programming (CAAP ’86), volume 214 of Lecture Notes in Computer Science, pages 112–126. Springer-Verlag, New York–Heidelberg–Berlin, March 1986. Nice.

[FJMM91] M. M. Fokkinga, J. Jeuring, L. Meertens, and E. Meijer. A translation from attribute grammars to catamorphisms. The Squiggolist, 2(1):20–26, 1991.

[FMY92] Rodney Farrow, Thomas J. Marlowe, and Daniel M. Yellin. Composable attribute grammars: Support for modularity in translator design and implementation. In 19th ACM Symp. on Principles of Programming Languages, pages 223–234, Albuquerque, NM, January 1992. ACM press.

[Gan80] Harald Ganzinger. Some principles for the development of compiler from denotational language definitions. Bericht TUM-INFO-8006, Institut für Informatik, Tech. University München, May 1980.

[GG84] Harald Ganzinger and Robert Giegerich. Attribute coupled grammars. In ACM SIGPLAN ’84 Symp. on Compiler Construction, pages 157–170, Montréal, June 1984. Published as ACM SIGPLAN Notices, 19(6).

[GJR87] José Garcia, Martin Jourdan, and Antoine Rizk. An implementation of PARLOG using high-level tools. In Commission of the European Communities—Directorate General XIII, editor, ESPRIT ’87: Achievements and Impact, pages 1265–1275. North-Holland, Amsterdam, November 1987. Brussels.

[Gom91] Roberto Gomez Cardenas. Amélioration de l’implantation en C des évaluateurs d’attributs produits par Fnc-2. Rapport de DEA, Université de Paris 7, September 1991.

[JMP94] Martin Jourdan, Bruno Marmol, and Didier Parigot. Experiments with a Real Parallel Attribute Evaluator. En préparation pour soumission, 1994.

[Joh87] Thomas Johnsson. Attribute grammars as a functional programming paradigm. In Gilles Kahn, editor, Func. Prog. Languages and Computer Architecture, volume 274 of Lecture Notes in Computer Science, pages 154–173. Springer-Verlag, New York–Heidelberg– Berlin, September 1987. Portland.

[Jou91] Jean-Philippe Jouve. Réalisation du décompilateur d’arbres attribués du système FNC-2 : ppat. Rapport de stage d’option, École Polytechnique, 1991.

[Jou96]  Martin Jourdan.  Presentation of dynamic attribute

grammars, 1996. http://www-rocq.inria.fr/oscar/FNC-2/Presentation/DynAG.slides.ps.gz.

[JP] Martin Jourdan and Didier Parigot. The FNC-2 System User’s Guide and Reference Manual. INRIA, Rocquencourt, 1.9 edition.

[JP90a] Martin Jourdan and Didier Parigot. Techniques for Improving Grammar Flow Analysis. In Neil Jones, editor, European Symp. on Programming (ESOP ’90), volume 432 of Lect. Notes in Comp. Sci., pages 240–255, Copenhague, 1990. Springer-Verlag.

[JP90b] Catherine Julié and Didier Parigot. Space Optimization in the FNC-2 Attribute Grammar System. In Deransart and Jourdan [DJ90], pages 29–45. Paris.

[JP90c] Catherine Julié and Didier Parigot. Space Optimization in the FNC-2 Attribute Grammar System. Rapport de recherche 1165, INRIA, 1990.

[JP91] Martin Jourdan and Didier Parigot. Internals and Externals of the FNC-2 Attribute Grammar System. In Alblas and Melichar [AM91], pages 485–504. Prague.

[JP92] Martin Jourdan and Didier Parigot. Application development with the FNC-2 attribute grammar system. In Dieter Hammer, editor, Compiler Compilers ’90, Lecture Notes in Computer Science, pages 85–94. Springer-Verlag, New York–Heidelberg–Berlin, October 1990 January 1992. Schwerin.

[JPJ^{+}90] Martin Jourdan, Didier Parigot, Catherine Julié, Olivier Durin, and Carole Le Bellec. Design, implementation and evaluation of the FNC-2 attribute grammar system. In Conf. on Programming Languages Design and Implementation, pages 209–222, White Plains, NY, June 1990. Published as ACM SIGPLAN Notices, 25(6).

[Jul86] Catherine Julié. Optimisation de l’espace mémoire pour les compilateurs générés selon la méthode d’évaluation OAG: étude des travaux de kastens et propositions d’améliorations. rapport de DEA, Dépt. d’Informatique, University d’Orléans, September 1986.

[Jul89] Catherine Julié. Optimisation de l’espace mémoire pour l’évaluation de grammaires attribuées. PhD thesis, Université d’Orléans, September 1989.

[Le 89] Carole Le Bellec. Spécification de règles sémantiques manquantes. rapport de DEA, Dépt. d’Informatique, University d’Orléans, September 1989.

[Le 93] Carole Le Bellec. La généricité et les grammaires attribuées. PhD thesis, Département de Mathématiques et d’Informatique, Université d’Orléans, 1993.

[Le 95] Gilles Le Bâtard. Réalisation dans le système FNC-2 d’un traducteur vers ML. rapport de stage de maîtrise, IFI, Université de Marne-la-Vallée, July 1995.

[Lei96] Stéphane Leibovitsch. Relations entre la sémantique dénotationnelle et les grammaires attribuées. Rapport de DEA, Université de Paris VII, September 1996.

[LJPR93] Carole Le Bellec, Martin Jourdan, Didier Parigot, and Gilles Roussel. Specification and Implementation of Grammar Coupling Using Attribute Grammars. In Maurice Bruynooghe and Jaan Penjam, editors, Programming Language Implementation and Logic Programming (PLILP ’93), volume 714 of Lect. Notes in Comp. Sci., pages 123–136, Tallinn, August 1993. Springer-Verlag.

[LMOW88] Peter Lipps, Ulrich Möncke, Matthias Olk, and Reinhard Wilhelm. Attribute (re)evaluation in OPTRAN. Acta Informatica, 26:213– 239, 1988. See also: ESPRIT PROSPECTRA Project Report S.1.3 - R.4.0, University des Saarlandes, Saarbrücken (1986).

[LNP90] Thierry Ledig, Dang Khoa Nguyen, and Antoine Proietto. Introduction didactique aux grammaire attribuée: manual d’utilisation. Dess informatique, option génie logiciel, I.S.I.A.L mancy, 1990.

[Mar90] Bruno Marmol. Évaluateurs d’attributs parallèles sur multiprocesseurs à mémoire partagée. rapport de DEA, University d’Orléans, September 1990.

[Mar94] Bruno Marmol. La parallélisation et l’optimisation mémoire dans l’évaluation des grammaires attribuées. PhD thesis, Université d’Orléans, 1994.

[Paa95] Jukka Paakki. Attribute grammar paradigms — A high-level methodology in language implementation. ACM Computing Surveys, 27(2):196–255, June 1995.

[Par85] Didier Parigot. Un système interactif de trace des circularités dans une grammaire attribuée et optimisation du test de circularité. rapport de DEA, University de Paris-Sud, Orsay, September 1985.

[Par87] Didier Parigot. Mise en œuvre des grammaires attribuées: transformation, évaluation incrémentale, optimisations. thèse de 3ème cycle, University de Paris-Sud, Orsay, September 1987.

[Par88] Didier Parigot. Transformations, Évaluation Incrémentale et Optimisations des Grammaires Attribués: Le Système FNC-2. PhD thesis, Université de Paris-Sud, Orsay, 1988.

[PDRJ96] Didier Parigot, Etienne Duris, Gilles Roussel, and Martin Jourdan. Les grammaires attribuées : un langage fonctionnel déclaratif. In Journées Francophones des Langages Applicatifs, pages 263–279, Val-Morin, Québec, January 1996. ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/jfla96.ps.gz.

[PJ] Didier Parigot and Martin Jourdan. A bibliography on attribute

grammars. http://www-rocq.inria.fr/oscar/FNC-2/AG.html

Updated regularly. Contains around 950 references to papers on Attribute Grammars. INRIA, France.

[Pla89] Étienne Planes. PPAT: un décompilateur d’arbres attribués pour le système FNC-2. rapport de DEA, Dépt. d’Informatique, University d’Orléans, September 1989.

[PRJD96a] Didier Parigot, Gilles Roussel, Martin Jourdan, and Etienne Duris. Dynamic Attribute Grammars. Rapport de recherche 2881, INRIA, May 1996.

ftp://ftp.inria.fr/INRIA/publication/RR/RR-2881.ps.gz.

[PRJD96b] Didier Parigot, Gilles Roussel, Martin Jourdan, and Etienne Duris. Dynamic Attribute Grammars. In Herbert Kuchen and S. Doaitse Swierstra, editors, Int. Symp. on Progr. Languages, Implementations, Logics and Programs (PLILP’96), volume 1140 of Lect. Notes in Comp. Sci., pages 122–136, Aachen, September 1996. Springer-Verlag.

[Rou92a] Gilles Roussel. Élimination de suites de règles de copies dans les grammaires attribuées. 1992.

[Rou92b] Gilles Roussel. Méta-composition des grammaires attribuées. rapport de magistère, École Normale Supérieure, Paris, September 1992.

[Rou93] Philippe Rouzier. Réalisation d’une interface entre les systèmes Centaur, FNC-2 et syntax. Rapport de stage de DESS “Systèmes et communication homme-machine”, Université de Paris 11, September 1993.

[Rou94a] Christophe Roudet. Visualisation graphique incrémentale par évaluation d’attributs. Stage de DEA informatique de l’ESSI, Université NICE, 1994.

[Rou94b] Gilles Roussel. Algorithmes de base pour la modularité et la réutilisabilité des grammaires attribuées. PhD thesis, Département d’Informatique, Université de Paris 6, March 1994.

[RPJ94] Gilles Roussel, Didier Parigot, and Martin Jourdan. Coupling Evaluators for Attribute Coupled Grammars. In Peter A. Fritzson, editor, 5th Int. Conf. on Compiler Construction (CC’ 94), volume 786 of Lect. Notes in Comp. Sci., pages 52–67, Edinburgh, April 1994. Springer-Verlag.

[RPJ95] Gilles Roussel, Didier Parigot, and Martin Jourdan. Static and Dynamic Coupling Attribute Evaluators. Rapport de recherche 2670, INRIA, October 1995.

ftp://ftp.inria.fr/INRIA/publication/RR/RR-2670.ps.gz.

[RT84] Thomas Reps and Tim Teitelbaum. The synthesizer generator. In ACM SIGSOFT/SIGPLAN Symp. on Practical Software Development Environments, pages 42–48. Pittsburgh, PA, April 1984. Joint issue with Software Eng. Notes 9, 3.Published as ACM SIGPLAN Notices, volume 19, number 5.

[Sou87] Aziz Souah. Système de transformation d’arbres attribués: étude des principaux systèmes et spécification d’un nouveau système. rapport de DEA, University d’Orléans, September 1987.

[Sou90] Aziz Souah. Contribution à la sémantique déclarative des systèmes de transformation d’arbres attribués. PhD thesis, Université d’Orléans, November 1990.

[Tao88] Souad Taouil. Étude et implantation des grammaires couplées par attributs dans le système FNC-2. rapport de DEA, Dépt. d’Informatique, University d’Orléans, September 1988.

[Ter95] Delphine Terrasse. Vers un environnement de développement de preuves en Sémantique Naturelle. PhD thesis, Ecole Nationale des Ponts et Chaussées (ENPC), October 1995.

[Viv96] Bruno Vivien. Etude du système syntax/FNC-2 pour la génération de compilateur. Technical report, Conservatoire national des arts et metiers, Grenoble, 1996.

[Zyl90] Catherine Zylberman. Réalisation du constructeur d’arbre abstrait (ATC) du système de grammaire attribuée FNC-2 au dessus de l’analyseur lexico-syntaque lex-yacc. Rapport de stage de troisième année, Telecom Paris, 1990.