A translation from attribute grammars to catamorphisms

Abstract

G has a simple form, so that the actual translation can be formulated without too many indices and the like. 1 . The context free grammar G determines a functor F . . Lemma T is a subset of the carrier of the initial F -algebra. . The attribute evaluation rules A determine a function # : (X Y ) . . Theorem [[A]](t, x) = ([F| #]) t x . We assume that we are working in the category Set , or in a Set -like category, like CPO . Simplification of the attribute grammar For notational simplicity we make the following three assumptions, without loss of generality. (1) Any terminal a is produced only by rules of the form lhs a where a in the right hand side has no attributes. This can be achieved by the addition of auxiliary nonterminal symbols, say one for each terminal symbol a . (2) Any nonterminal has precisely one inherited and one synthesized attribute. This can be achieved for any AG by tupling the inherited attributes of each nonterminal, and also the synthesized on