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.