Second, it is at odds with the declarative
character of the specification because it forces the writer to think
about dependencies and evaluation order.
The basic idea is to feed the evaluator generator with a version of the input Attribute Grammar in which the extensions have been replaced by their effect on the control flow. In the case of conditional productions, this is achieved by removing the conditions and uniquely renaming each alternative. In the case of scheme productions, no transformation is needed at all.
After the evaluator generator has ran on this extensions-less Attribute Grammar, it is necessary to reintroduce in the generated evaluator the semantics of the extensions.
For scheme productions, this simply means to replace references to nodes in the RHS of a scheme by references to their corresponding ``real'' nodes (if any). In the case of circular schemes, such as the while example, this means that a given node may be visited twice or more, or even indefinitely (which is exactly the purpose of this extension). This mandates that the evaluator be able to store all attributes outside the tree. FNC-2, in particular, uses sophisticated analysis techniques based on attribute lifetimes that allow most attributes to be stored in global variables or stacks [JP90b], resorting to a more systematic technique such as binding trees [SV91] for the very few that remain.
Conditional productions introduce a new way to choose between the various alternatives applicable at a given point. To take this into account, the back-end should generate a new production selector. The selection of a production which has been renamed from a conditional production occurs when the pattern match implied by the underlying production succeeds, and the condition specified in the extended form is satisfied. Of course, this is only possible when the condition is evaluable before--i.e. does not depend on--any attribute computed in the production.
This restriction is clearly not acceptable. First, it strongly reduces the
expressive power. Second, it is at odds with the declarative
character of the specification because it forces the writer to think
about dependencies and evaluation order.
To solve these problems we propose another syntactic form of conditional productions, called a factored form. A possible factored form of the while example is given in Fig. 3.
Figure 3: Factored form of the while example in Olga
There are two important features to notice. First, the conditions do not control all semantic rules, which allows the conditions to depend on attributes computed in these independent rules (or on input attributes that depend on them). Thus, condition evaluation may occur anywhere in the attribute evaluation process and not only at production-selection time. Second, the precedence of the various conditions is now explicit.
From this factored form it is possible to produce a flattened form close to the type we have been using, with a simple distributive transformation. The back-end can then collect the evaluation code generated for all alternatives and can rearrange it into a common part followed by a classical conditional statement; this allows the evaluation of the condition to occur elsewhere than at the beginning.
The validity of this process has been demonstrated by its implementation into FNC-2, which took only a few man-weeks and indeed left the evaluator generator strictly untouched.