Introduction: The idea of associating quantities with programming constructs—for example, values and types with expressions—can be expressed in terms of grammars. We associate attributes with non-terminals and terminals. Then, we attach rules to the productions of the grammar; these rules describe how the attributes are computed at those nodes of the parse tree where the production in question is used to relate a node to its children.
A syntax-directed definition associates
1. With each grammar symbol, a set of attributes, and
2. With each production, a set of semantic rules for computing the values of the attributes associated with the symbols appearing in the production.
Attributes can be evaluated as follows. For a given input string x, construct a parse tree for x. Then, apply the semantic rules to evaluate attributes at each node in the parse tree, as follows.
Suppose a node A?" in a parse tree is labeled by the grammar symbol X. We write X.a to denote the value of attribute a of X at that node. A parse tree showing the attribute values at each node is called an annotated parse tree. For example, Fig. 2.9 shows an annotated parse tree for 9-5 2 with an attribute t associated with the non-terminals expr and term. The value 95-2 of the attribute at the root is the postfix notation for 9-5 2. We shall see shortly how these expressions are computed.
An attribute is said to be synthesized if its value at a parse-tree node N is determined from attribute values at the children of N and at N itself. Synthesized attributes have the desirable property that they can be evaluated during a single bottom-up traversal of a parse tree. In Section 5.1.1 we shall discuss another important kind of attribute: the "inherited" attribute. Informally, inherited attributes have their value at a parse-tree node determined from attribute values at the node itself, its parent, and its siblings in the parse tree.
Example: The annotated parse tree in Fig. 2 . 9 is based on the syntax directed definition in Fig. 2 . 1 0 for translating expressions consisting of digits separated by plus or minus signs into postfix notation. Each nonterminal has a string-valued attribute t that represents the postfix notation for the expression generated by that nonterminal in a parse tree. The symbol || in the semantic rule is the operator for string concatenation.
The postfix form of a digit is the digit itself; e.g., the semantic rule associated with the production term -» 9 defines term.t to be 9 itself whenever this production is used at a node in a parse tree. The other digits are translated similarly. As another example, when the production expr term is applied, the value of term.t becomes the value of expr.t.
The production expr —> exprx term derives an expression containing a plus operator.3 The left operand of the plus operator is given by exprx and the right operand by term. The semantic rule
expr.t = expr.t \\ term.t \\ ' '
associated with this production constructs the value of attribute expr.t by concatenating the postfix forms expr.t and term.t of the left and right operands, respectively, and then appending the plus sign. This rule is a formalization of the definition of "postfix expression."
Convention Distinguishing Uses of a Nonterminal: In rules, we often have a need to distinguish among several uses of thesame nonterminal in the head and/or body of a production; e.g., see Example2.10. The reason is that in the parse tree, different nodes labeledby the same nonterminal usually have different values for their translations.We shall adopt the following convention: the nonterminal appearsun-subscripted in the head and with distinct subscripts in the body. Theseare all occurrences of the same nonterminal, and the subscript is not partof its name. However, the reader should be alert to the difference betweenexamples of specific translations, where this convention is used, andgeneric productions like A —> X1X2, • • • ,Xn, where the subscripted X'srepresent an arbitrary list of grammar symbols, and are not instances ofone particular nonterminal called X.