Evaluating an SDD at the Nodes of a Parse Tree
Introduction: To visualize the translation specified by an SDD, it helps to work with parse trees, even though a translator need not actually build a parse tree. Imagine therefore that the rules of an SDD are applied by first constructing a parse tree and then using the rules to evaluate all of the attributes at each of the nodes of the parse tree. A parse tree, showing the value(s) of its attribute(s) is called an annotated parse tree.
How do we construct an annotated parse tree? In what order do we evaluate attributes? Before we can evaluate an attribute at a node of a parse tree, we must evaluate all the attributes upon which its value depends. For example, if all attributes are synthesized, as in following Example, then we must evaluate the val attributes at all of the children of a node before we can evaluate the val attribute at the node itself.
With synthesized attributes, we can evaluate attributes in any bottom-up order, such as that of a postorder traversal of the parse tree; the evaluation of S-attributed.
For SDD's with both inherited and synthesized attributes, there is no guarantee that there is even one order in which to evaluate attributes at nodes. For instance, consider nonterminals A and B, with synthesized and inherited attributes A.s and BA, respectively, along with the production and rules
PRODUCTION SEMANTIC RULES
A^B A.s = B.i;
B.i = A.s l
These rules are circular; it is impossible to evaluate either A.s at a node N or BA at the child of N without first evaluating the other. The circular dependency of A.s and BA at some pair of nodes in a parse tree.
It is computationally difficult to determine whether or not there exist any circularities in any of the parse trees that a given SDD could have to translate.1 Fortunately, there are useful subclasses of SDD's that are sufficient to guarantee that an order of evaluation exists.
Example: Figure 5.3 shows an annotated parse tree for the input string 3 * 5 4 n, constructed using the grammar and rules of Fig. 5.1. The values of lexval are presumed supplied by the lexical analyzer. Each of the nodes for the nonterminals has attribute val computed in a bottom-up order, and we see the resulting values associated with each node. For instance, at the node with a child labeled *, after computing T.val = 3 and F.val = 5 at its first and third children, we apply the rule that says T.val is the product of these two values, or 15.
Inherited attributes are useful when the structure of a parse tree does not "match" the abstract syntax of the source code. The next example shows how inherited attributes can be used to overcome such a mismatch due to a grammar designed for parsing rather than translation.