Abstract EN:

Les grammaires attribuées introduites à l'origine par Knuth pour décrire les sémantiques dirigées parla syntaxe ont été présentées de façon modulaire par Ganzinger et Giegerich sous la forme de grammaires couplées par attributs. La composition de ces grammaires, appelée composition descriptionnelle, s'apparente aux techniques d'optimisation des programmes fonctionnels, telles que la déforestation qui consiste à éliminer des structures de données intermédiaires lors de la composition des fonctions. Dans ce travail, nous présentons une approche fonctionnelle d'ordre supérieure pour l'évaluation des attributs basée sur les dépendances locales entre les attributs synthétisés et les attributs hérités. Cette traduction, de nature non syntaxique et à ce titre non compatible avec les techniques de déforestation, procure néanmoins une implémentation directe des grammaires attribuées dans un langage fonctionnel paresseux d'ordre supérieur. Nous présentons alternativement une traduction fonctionnelle du premier ordre dans laquelle l'arbre d'entrée et son contexte sont représentés simultanéement par un arbre sur une signature étendue. Nous montrons que la composition descriptionnelle des grammaires attribuées se ramène, par cette traduction, en une simple composition de transducteurs d'arbres.