Beyond Symbol Tables

Attributes of uniquely stored terms can be used to implement symbol tables,  or more exactly, the contents of symbol tables. Looking up translates to newly creating a term (which is represented uniquely) and then inspecting its attributes. One can view this as making the look up function a memo function.

The nice thing is that entire terms can be used as the key in the `symbol table'. This is useful for e.g. nested scopes. A key can then be a term composed of an identifier and a scope indication. This tuple should be unique.

As an example, we consider the detection of common subexpressions. Every subexpression is a key in the symbol table, and one pass over the expression computes the attribute ocs, which represents the number of occurrences of each subexpression.

     

/* A very simple tree structure */
funnytree {uniq}:       Str(casestring)
|                       Cons(funnytree funnytree)
{                       int ocs = 0;
                        funnytree next ;
                        { $0->next = alltrees;
                          alltrees = $0; }
}
;


void occurs(funnytree $f) {
    Str:                { f->ocs++; }
    Cons(f1, f2):       { f->ocs++; occurs(f1); occurs(f2); }
}


%{ KC_TYPES_HEADER
funnytree alltrees;
%}


void main() {
    funnytree ft, it;


alltrees = (funnytree)0;
    ft = Str(mkcasestring("foo"));
    ft = Cons(ft, ft);
    ft = Cons(ft, Str(mkcasestring("bar")));
    ft = Cons(ft, ft);
    it = alltrees;
    occurs(it);
    for(; it!= (funnytree)0; it= it->next) {
        if (it->ocs>1) {
            printf("occurs %d times:\n", it->ocs);
            print_funnytree(it);
}   }   }

The example also illustrates a technique through which all values of a particular phylum in the symbol table can be accessed. The idea is that they are strung together using an attribute (here next) and a global variable (here alltrees), which are manipulated in the initialisation part of a term. The other essential components of this technique are the initialisation of the global variable, and the inclusion of its definition in all the files through KC_TYPES_HEADER. This technique also works for non unique phyla. Unique phyla should not be used when some of the attributes depend on the context of their nodes.