In the classical theory of Attribute Grammars, the notion of grammar implies the existence of some tree. We now extend this notion with a new notion of scheme productions. These scheme productions describe in a general way how to dynamically connect sets of semantic rules; in the classical Attribute Grammar formalism this connection was driven exclusively by the input tree.
Together with the notion of conditional productions, the scheme productions allow the expression of solutions to many different kinds of recursive problems that could not be handled in the classical formalism. The presentation of this extension uses the well known problem of the Towers of Hanoi.
In addition to the classical productions (with the implicit presence of a tree), we now allow scheme productions to be associated to some left-hand-side non-terminal which can be viewed as a type. Here, a HANOI type is defined, with scheme productions that only describe recursive calls; this purely virtual scheme does not define any physical tree.
The Olga specification for this example is given in Fig. 1. A condition on the number of disks chooses between the recursive and the termination cases. Note that, since HANOI is a pure scheme type, it has no (tree) value and hence cannot (and will not) be used to drive the evaluator flow; the explicit condition will be the sole discriminant.
Figure 1: Towers of Hanoi specified with an Attribute Grammar
This example can be expressed in Typol, as shown in Fig. 2.
Figure 2: Towers of Hanoi specified in Typol