Proposition de stage : Amélioration de la gestion du stockage des attributs dans les évaluateurs produits par le système Fnc-2

Les Grammaires Attribuées (GA) sont un paradigme de programmation déclaratif et dirigé par la syntaxe qui a prouvé sa valeur sur de grosses applications comme les compilateurs. Nous étudions les GA depuis de nombreuses années dans le projet Oscar de l'INRIA­Rocquencourt. La concrétisation de ces travaux est le système Fnc-2, destiné à traiter des applications industrielles mais qui est aussi le support de tous nos travaux de recherche.

Pour obtenir des évaluateurs d'attributs efficaces, il est indispensable de pouvoir déterminer le moyen le plus économique de les placer en mémoire. Par ailleurs, nous avons récemment défini des extensions au formalisme originel des GA qui impliquent que l'on soit capable de stocker tous les attributs hors de l'arbre d'entrée. Dans les deux cas, cela s'obtient en effectuant une analyse statique des durées de vie des attributs. Le générateur d'évaluateurs de Fnc-2 contient un module d'optimisation mémoire qui est capable de déterminer quels attributs peuvent être stockés dans des variables globales et lesquels peuvent être stockés dans des piles (simples), mais il reste encore quelques attributs qui échappent à cette classification et doivent donc être attachés à l'arbre d'entrée. Nous connaissons deux techniques qui permettent de stocker ces derniers attributs en dehors de l'arbre : les ``piles cactus'' étudiées par Parigot et Julié et les ``binding trees'' de Vogt et al (Utrecht).

Le stage proposé consiste à :

  1. se familiariser avec le formalisme des GA ;
  2. étudier et comparer les techniques d'optimisation mémoire pour les GA, en particulier les deux mentionnées ci-dessus, ainsi que les techniques équivalentes dans le monde de la programmation fonctionnelle et de la programmation en logique ;
  3. déterminer laquelle de ces techniques ou combinaison de techniques est la plus efficace pour résoudre le problème du stockage de tous les attributs hors de l'arbre ;
  4. si le temps le permet, implanter cette technique dans le système Fnc-2.

Ce stage peut se prolonger par l'application de la technique choisie à d'autres paradigmes de programmation (fonctionnel, logique) et plus généralement par l'étude systématique des relations entre les techniques d'analyse statique et d'implantation des GA avec celles utilisées pour ces autres paradigmes.

Lieu du stage :
Avant-projet Oscar, INRIA, bâtiment 13, Domaine de Voluceau, Rocquencourt, B. P. 105, 78153 Le Chesnay Cedex
Responsables :
Didier Parigot (Didier.Parigot@inria.fr, 39.63.55.46), Martin Jourdan (Martin.Jourdan@inria.fr, 39.63.54.35)

Généralités et autres sujets de stage sur les grammaires attribuées proposés par le projet Oscar