We now introduce the classical formalism of Attribute Grammars using a simple example called bird [Bir84, Joh87]. The purpose is to take as input a binary tree with integer leaves, and to give as output the same binary tree where all leaves are replaced by the minimum value of the input tree leaves.
Before the specification of the Attribute Grammar, we specify the tree type, or
abstract syntax. This abstract syntax is also translated into an ML
type.
The Attribute Grammar specification of the example follows. The attribute $min is used to compute the minimum value of the input tree leaves, $n propagates the minimum value throughout the tree, and $tree computes the new output tree.
A simple syntactic transformation [Joh87] results in the following single ML function:
Finally, here is the same example specified with inference rules:
Our FNC-2 system can produce evaluators in several different languages, including ML [Bât95]. The ML form of the evaluator that is automatically generated from the Attribute Grammar\ specification given above is given below. This form does not require lazy evaluation, but inferring it requires more intellectual effort. In the Attribute Grammar specification, no order of evaluation was specified, and this is the essence of its declarativeness and attractiveness: it is not necessary to write it in a specific way to make it efficient. Indeed, the evaluator generator has automatically determined that the minimum should first be evaluated, and then the tree should be constructed. These two passes break the ``circularity''. In this simple example the evaluation order is easy to find by hand, but this is not always the case.
