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. Attribute
grammars have been successfully applied in many areas, including compiler
construction and natural language processing. In this paper we present
a translation of attribute grammars to Constraint Handling Rules, a
formalism based on constraint rewriting.
Our translation is able to express in a simple way several extensions to
attribute grammars. Higher-order attributes are attributes whose value
is again a tree, for which attributes can be computed recursively. Look-
ahead enables attribute de nitions to depend not only on the current
node, but also on the shape of its subtrees. Specialization provides a way
to override the default computation of an attribute when some conditions
are met; a natural way to de ne exceptions to the default tree processing.