Attribute grammars as tree transducers over cyclic representations of infinite trees and their descriptional composition

Résumé : L'évaluation des attributs d'une grammaire attribuée peut s'obtenir inductivement à l'aide de fonctions exprimant les dépendances fonctionnelles entre attributs hérités et synthétisés d'un même noeud. Le codage de ce mécanisme d'évaluation se fait de manière directe dans un langage fonctionnel paresseux (comme Haskell). Néanmoins l'utilisation de fonctions d'ordres supérieurs rend difficile l'optimisation de ces fonctions lorsqu'il s'agit de composer de telles grammaires attribuées. Nous présentons une implémentation alternative de l'évaluation des attributs reposant uniquement sur des fonctions du premier ordre pour laquelle l'arbre d'entrée est néanmoins rendu cyclique en ajoutant un lien de chaque noeud vers son père permettant ainsi l'accès aux informations héritées. Ces représentations de zippers (arbres donnés avec leurs contextes) sont des généralisations naturelles des listes avec double chaînage pour une signature arbitraire. Nous montrons que par ce codage la composition descriptionnelle des grammaires attribuées se réduit à une composition de transducteurs d'arbres.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2013, 480, pp.1-25. 〈10.1016/j-tcs.2013.02.007〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00915031
Contributeur : Eric Badouel <>
Soumis le : vendredi 6 décembre 2013 - 14:31:53
Dernière modification le : jeudi 15 novembre 2018 - 11:58:45

Identifiants

Citation

Eric Badouel, Rodrigue Tchougong, Célestin Nkuimi-Jugnia, Bernard Fotsing. Attribute grammars as tree transducers over cyclic representations of infinite trees and their descriptional composition. Theoretical Computer Science, Elsevier, 2013, 480, pp.1-25. 〈10.1016/j-tcs.2013.02.007〉. 〈hal-00915031〉

Partager

Métriques

Consultations de la notice

405