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 (nuds 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 (nuds 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éta-composition 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 nud 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 ).