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:
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é
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.