Automatic generation of fixed-point-finding evaluators for circular, but well-defined, attribute grammars

Abstract

In the traditional formulation of attribute grammars (AGs) circularities are not allowed, that is, no attribute-instance in any derivation tree may be defined in terms of itself. Elsewhere in mathematics and computing, though, circular (or recursive) definitions are commonplace, and even essential. Given appropriate constraints, recursive definitions are well-founded, and the least fixed-points they denote are computable. This is also the case for circular AGs.