From Attribute Grammars to Constraint Handling Rules

Attribute grammars provide a framework to de ne compu-tations over trees, by decorating those trees with attributes. Attributegrammars have been successfully applied in many areas, including compilerconstruction and natural language processing. In this paper we presenta translation of attribute grammars to Constraint Handling Rules, aformalism based on constraint rewriting.Our translation is able to express in a simple way several extensions toattribute grammars. Higher-order attributes are attributes whose valueis again a tree, for which attributes can be computed recursively. Look-ahead enables attribute de nitions to depend not only on the currentnode, but also on the shape of its subtrees. Specialization provides a wayto override the default computation of an attribute when some conditionsare met; a natural way to de ne exceptions to the default tree processing.