Attribute Grammars

Structural induction is a special case of attribute grammars, where there is only one pass, computing only synthesized attributes. This is not the place to give an overview of attribute grammars. Suffice it to say that each node, or term, is decorated with a number of attributes, of which the value is computed from the values of the subterms of the node (synthesized attributes) or from the encompassing node (inherited attributes). An evaluation scheme walks a tree a number of times to compute all the attributes. Two schemes are demonstrated here. The example is from the original paper on attribute grammars[Knu68], and computes the value of a fractional binary number, e.g 1101.01. First the abstract syntax.

 

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


bitstring:Oneb(bit)
|         Moreb(bitstring bit)
{         float value;  /* synthesized */
          int length;   /* synthesized */
          int scale;    /* inherited */
}
;


bit:      One()
|         Zero()
{         float value;  /* synthesized */
          int scale;    /* 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 */
float eval_number_value(number $n) {
    Nonfraction(b):     { return eval_bitstring_value(b,0); }
    Fraction(b1, b2):   { return eval_bitstring_value(b1,0) +
                                 eval_bitstring_value(b2, -eval_bitstring_length(b2));}
}


float eval_bitstring_value(bitstring $bs, int scale) {
    Oneb(b):            { return eval_bit_value(b, scale); }
    Moreb(bs_bs, bs_b): { return eval_bitstring_value(bs_bs,scale+1)+ eval_bit_value(bs_b, scale); }
}


int eval_bitstring_length(bitstring $bs) {
    Oneb:               { return 1; }
    Moreb(bs_bs, *):    { return eval_bitstring_length(bs_bs)+1; }
}


%{
#include <math.h>
%}


float eval_bit_value(bit $b, int scale) {
    One:                { return exp2((float)scale); }
    Zero:               { return 0.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 passnumber_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 */
void pass1_number(number $n) {
    Nonfraction(b):     { pass1_bitstring(b); }
    Fraction(b1, b2):   { pass1_bitstring(b1);
                          pass1_bitstring(b2); }
}


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


/* pass1_bit omitted, it does nothing */


void pass2_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; }
}


void pass2_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; }
}


void pass2_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 */
void main() {
    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.