Attribute Grammars as Recursion Schemes over Cyclic Representations of Zippers

Résumé : L'évaluation des attributs d'une grammaire attribuées peut s'obtenir inductivement à l'aide d'une fonction exprimant les dépendances entre les attributs synthétisés et les attributs hérités. Cette interprétation d'ordre supérieure s'implémente de façon immédiate dans un langage fonctionnel paresseux tel que Haskell. Néanmoins cette interprétation n'est pas compatible avec les techniques usuelles d'optimisation et nous présentons par conséquent une interprésentation alternative du premier ordre. Cette dernière requière de remplacer l'arbre d'origine par une version cyclique du zipper (arbre dans son contexte) dans laquelle chaque noeud admet un fils supplémentaire donnant accès à son contexte. Nous montrons comment ces représentations cycliques de zippers sont les généralisations naturelles à des signatures arbitraires des représentations des listes avec double chaînage.
Type de document :
Article dans une revue
Electronic Notes in Theoretical Computer Science, Elsevier, 2011, Proceedings of the Second Workshop on Mathematically Structured Functional Programming (MSFP 2008), 229 (5), pp.39-56
Liste complète des métadonnées

https://hal.inria.fr/hal-00650799
Contributeur : Eric Badouel <>
Soumis le : lundi 12 décembre 2011 - 12:01:59
Dernière modification le : lundi 13 octobre 2014 - 15:43:25

Identifiants

  • HAL Id : hal-00650799, version 1

Citation

Eric Badouel, Célestin Nkuimi, Rodrigue Tchougong, Bernard Fotsing. Attribute Grammars as Recursion Schemes over Cyclic Representations of Zippers. Electronic Notes in Theoretical Computer Science, Elsevier, 2011, Proceedings of the Second Workshop on Mathematically Structured Functional Programming (MSFP 2008), 229 (5), pp.39-56. 〈hal-00650799〉

Partager

Métriques

Consultations de la notice

63