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

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 evaluation can straightforwardly be implemented in a higher-order lazy functional language like Haskell. The resulting evaluation functions are, however, not easily amenable to optimization when we want to compose two attribute grammars. We present an alternative first-order functional interpretation of attribute grammars where the input tree is replaced by an extended cyclic tree each node of which is aware of its context viewed as an additional child tree. These cyclic representations of zippers (trees with their context) are natural generalizations of doubly-linked lists to trees over an arbitrary signature. Then we show that, up to that representation, descriptional composition of attribute grammars reduces to the composition of tree transducers.
Document type :
Journal articles
Liste complète des métadonnées

https://hal.inria.fr/hal-00915031
Contributor : Eric Badouel <>
Submitted on : Friday, December 6, 2013 - 2:31:53 PM
Last modification on : Friday, April 12, 2019 - 10:18:03 AM

Identifiers

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⟩

Share

Metrics

Record views

420