WG211/M15Sloane

Respect Your Parents: How Attribution and Rewriting Can Get Along

Anthony Sloane, Macquarie University

Attribute grammars describe how to decorate static trees. Rewriting systems describe how to transform trees into new trees. Attri- bution is undermined by rewriting because a node may appear in both the source and product of a transformation. If an attribute of that node depends on the node’s context, then a previously computed value may not be valid. We explore this problem and formalise it as a question of ancestry: the context of a node is given by the tree’s parent relationships and we must use the appropriate parents to calculate attributes that de- pend on the context. We show how respecting parents naturally leads to a view of context-dependent attributes as tree-indexed attribute families. Viewed in this way, attribution co-exists easily with rewriting transfor- mations. We demonstrate the practicality of our approach by describing our implementation in the Kiama language processing library.