Any tree computation algorithm has three components: a set of computations done at each node, a traversal strategy, and a mechanism for managing intermediate storage. When the algorithm is written by hand, the author must design and implement all three components. It is well known, however, that the traversal strategy and the storage management mechanism can be deduced from the dependences among the computations at the nodes [WG84].
Attribute grammars [Knu68] can be used as declarative specifications of the dependence among computations at the nodes of a tree [Wai90]. In their original form, however, they were difficult to write and to maintain. Moreover, early translators for attribute grammars generated evaluation modules with poor performance in both space and time. These problems have now been overcome. Modern attribute grammar tools, such as LIGA [Kas91], generate modules whose efficiency is within a few percent of hand code from declarative specifications that are modular and reusable.
Here is a typical attribute grammar specification of computations at a node representing a C while statement:
RULE While: it_statement ::= 'while' '(' exp ')' statement
COMPUTE
it_statement.Ptg=
PTGWhile(exp.Ptg, statement.Ptg, exp.Target, PTGLabel(NewPtgInt()));
exp.Target=PTGLabel(NewPtgInt());
END;
This specification describes the computations involved in constructing a text fragment, using the module generated from the specification in the last section. Assume that NewPtgInt is defined operationally by the user, and yields a PTGNode representing the next integer each time it is invoked. PTGLabel might then be generated from a declarative specification like Label: "L" $ that constructs a valid assembly language label from an integer.
The dependence among the text fragments is defined by the Ptg attributes attached to the symbols in the rule. A label is generated by PTGLabel(NewPtgInt()), and sent down the expression tree by assigning it to exp.Target. This label will be incorporated into the text fragment representing the translation of the expression, which will be assigned to exp.Ptg by code generated from some rule with exp on the left-hand side. The value of the Ptg attribute of the it_statement on the left-hand side of the While rule then depends on that fragment, the fragment representing the translation of the statement controlled by the while (statement.Ptg), and two generated labels.
Clearly the While rule must have other computations associated with it. They could be added to the specification given above, but it would probably be better to place them in other files with related computations at other nodes. The specification given above would then be in a file with computations involving text fragment construction at nodes representing expressions and other statements. A tool like LIGA would then read all of the files, combining all of the computations for each individual rule, to obtain the complete attribute grammar.
The computations at a node appear in an attribute grammar as function applications; the tool that translates them does not recognize any operators like + or ==. Modules must be provided to carry out all of the computations specified. When the computations are standard, like those needed to implement scope rules, they can be provided by library modules [KW94]. Computations that solve standard problems with special data structures, like those needed to maintain the definition table or construct text fragments, can be provided by modules generated by tools. Computations special to the application must be provided by modules written by the user. In any case, however, these modules need deal only with local computations. The tree traversal strategy and intermediate storage mechanisms are handled by the attribute grammar tool.
An attribute grammar tool can also generate a module to construct the tree described by the rules. For example, LIGA generates a module that exports a function for each rule and a function for each non-literal terminal symbol. Rule functions are invoked with one argument defining the source text coordinates and one argument for each non-literal symbol on the right-hand side of the rule. The latter arguments are pointers to tree nodes, and the function yields a pointer to the tree node representing the rule with the argument nodes as children. The name of the function is the name of the rule, prefixed by Mk. Thus the LIGA-generated tree construction module will export a rule MkWhile with three arguments for the rule described above.
Functions generated for non-literal terminal symbols are invoked with one argument defining the source text coordinates and one argument giving a single integer value representing the non-literal terminal symbol.