Yet Another Implementation of Attribute Evaluation

Eric Badouel (1) , Bernard Fotsing (1) , Rodrigue Tchougong (1)

1 S4 - System synthesis and supervision, scenarios

We introduce another item in the already large list of techniques for attribute evaluation. Our algorithm consists in computing attributes by reductions to normal forms using a transducer operating on tree encodings of a cyclic representation of zippers. A zipper is a data structure introduced by Gérard Huet for representing a subtree together with its context, i.e. it is a tree with a focus that points to some node inside it. We mention some potential applications of this representation of attribute grammars as zipper transformers.

Mots clés: Attribute Grammars; Attribute Evaluation; Cyclic Data Structures; Zipper

Domaines: Mathématique discrète [cs.DM]

Eric Badouel, Bernard Fotsing, Rodrigue Tchougong. Yet Another Implementation of Attribute Evaluation. [Research Report] RR-6315, INRIA. 2007. ⟨inria-00175810v2⟩