Attribute Grammars as Recursion Schemes over Cyclic Representations of Zippers

Eric Badouel 1, * Bernard Fotsing 2 Rodrigue Tchougong 2
* Auteur correspondant
1 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Evaluation of attributes w.r.t. an attribute grammar can be obtained by inductively computing a function expressing the dependencies of the synthesized attributes on inherited attributes. This higher-order functional approach to attribute grammars leads to a straightforward implementation using a higher-order lazy functional language like Haskell. The resulting evaluation functions are, however, not easily amenable to optimization rules. We present an alternative first-order functional interpretation of attribute grammars where the input tree is replaced with an extended cyclic tree each node of which is aware of its context viewed as an additional child tree. By the way, we demonstrate that these cyclic representations of zippers (trees with their context) are natural generalizations of doubly-linked lists to trees over an arbitrary signature.
Type de document :
Article dans une revue
Electr. Notes Theor. Comput. Sci., Elsevier, 2011, 229 (5), pp.39-56. 〈10.1016/j.entcs.2011.02.015〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00748204
Contributeur : Eric Badouel <>
Soumis le : lundi 5 novembre 2012 - 10:10:25
Dernière modification le : vendredi 16 novembre 2018 - 01:24:15

Lien texte intégral

Identifiants

Citation

Eric Badouel, Bernard Fotsing, Rodrigue Tchougong. Attribute Grammars as Recursion Schemes over Cyclic Representations of Zippers. Electr. Notes Theor. Comput. Sci., Elsevier, 2011, 229 (5), pp.39-56. 〈10.1016/j.entcs.2011.02.015〉. 〈hal-00748204〉

Partager

Métriques

Consultations de la notice

261