Attribute Grammars

/* From D. Knuth, Semantics of Context Free Languages *//* The abstract syntax tree of fractional binary numbers, attributed */number: Nonfraction(bitstring) | Fraction(bitstring bitstring) {floatvalue;/* synthesized */} ;

bitstring:Oneb(bit) | Moreb(bitstring bit) {floatvalue;/* synthesized */intlength;/* synthesized */intscale;/* inherited */} ;

bit: One() | Zero() {floatvalue;/* synthesized */intscale;/* inherited */} ;

The first example of an evaluation scheme derives from the observation that each
phylum occurrence can be viewed as a set of functions, each of which computes
a synthesized attribute from the inherited attributes.
So, there is a set of functions *eval_**phylum_synthesized_attr*.
Each rule for a synthesized attribute corresponds to a case in one of these functions,
and each rule for an inherited attribute appears as a parameter of one of the calls to these
functions.
The function invocation structure is isomorphic to the attribute dependency graph.
This scheme can also be characterised as a *demand-driven* scheme.

There are at least two problems with this approach.
First, an inherited attribute of a phylum can be dependent on a synthesized attribute
of that phylum.
For example *bitstring_scale* depends on *bitstring_length*, and the computation
of *bitstring_length* can therefore not have the *scale* as an argument.
An analysis of the attribute dependencies is necessary to prune the argument lists
of the functions.
Second, as each used occurrence of a synthesized attribute is represented
as a call to the corresponding function, attributes may be evaluated more than once.
This is of course the other side of not storing results in the tree.

/* illustrating attribute evaluation without storing the attributes */floateval_number_value(number $n) { Nonfraction(b): {returneval_bitstring_value(b,0); } Fraction(b1, b2): {returneval_bitstring_value(b1,0) + eval_bitstring_value(b2, -eval_bitstring_length(b2));} }

floateval_bitstring_value(bitstring $bs,intscale) { Oneb(b): {returneval_bit_value(b, scale); } Moreb(bs_bs, bs_b): {returneval_bitstring_value(bs_bs,scale+1)+ eval_bit_value(bs_b, scale); } }

inteval_bitstring_length(bitstring $bs) { Oneb: {return1; } Moreb(bs_bs, *): {returneval_bitstring_length(bs_bs)+1; } }

%{#include<math.h> %}

floateval_bit_value(bit $b,intscale) { One: {returnexp2((float)scale); } Zero: {return0.0; } }

The second example of an evaluation scheme visits the tree a number of times and
computes at each visit of a node all the attributes that can be computed.
In the implementation there are procedures called *pass**number_phylum*.
In our example there are two passes.
In the first pass the attribute *length* is computed, and in the second pass the other attributes.

Again, this scheme has its disadvantages. The allocation of attributes to passes has to be derived from an analysis of the attribute dependencies. Second, in comparison with the previous scheme, this one represents the opposite time/space trade-off. No attribute is evaluated more than once, but at the expense of storing all intermediate results. Finally, this scheme does not coexist very well with unique storage of phyla that have inherited attributes. Two occurrences of a phylum cannot be shared if they have different inherited attributes.

/* illustrating a multi-pass evaluation */voidpass1_number(number $n) { Nonfraction(b): { pass1_bitstring(b); } Fraction(b1, b2): { pass1_bitstring(b1); pass1_bitstring(b2); } }

voidpass1_bitstring(bitstring $b) { Oneb: { b->length=1;} Moreb(bs, *): { pass1_bitstring(bs); b->length=bs->length+1; } }

/* pass1_bit omitted, it does nothing */

voidpass2_number(number $n) { Nonfraction(b): { b->scale=0; pass2_bitstring(b); n->value= b->value; } Fraction(b1, b2): { b1->scale=0; b2->scale= -b2->length; pass2_bitstring(b1); pass2_bitstring(b2); n->value= b1->value+b2->value; } }

voidpass2_bitstring(bitstring $bs) { Oneb(b): { b->scale= bs->scale; pass2_bit(b); bs->value= b->value; } Moreb(b1, b2): { b2->scale= bs->scale; b1->scale= bs->scale+1; pass2_bitstring(b1); pass2_bit(b2); bs->value= b1->value + b2->value; } }

voidpass2_bit(bit $b) { One: { b->value= exp2((float)b->scale); } Zero: { b->value= 0.0; } }

Here follows for the sake of completeness the main program to call the attribute evaluations.

/* the main program to call the evaluations */voidmain() { number n; n = Fraction(Moreb(Moreb(Moreb(Oneb(One()), One()), Zero()), One()), Moreb(Oneb(Zero()), One()));/* 1101.01 */printf(`" %f \n"`

, eval_number_value(n)); pass1_number(n); pass2_number(n); printf(`" %f \n"`

, n->value);

n = Nonfraction(Moreb(Moreb(Moreb(Oneb(One()), One()), Zero()), One())); printf(`" %f \n"`

, eval_number_value(n));/* 1101 */pass1_number(n); pass2_number(n); printf(`" %f \n"`

, n->value); }

The examples illustrate that the term processor does not prescribe a particular evaluation scheme. The advantage is that schemes can be mixed at liberty, and can even be combined with non-attribute grammar paradigms. The disadvantage is of course that evaluation order, e.g. in pass allocation, has to be determined manually, or by using some other tool. Conceivably a system can be made to generate term processor input from an attribute grammar.