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 :
uvre pour
la construction des arbres ni de leur représentation physique ;
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:
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 .