Definition: A syntax-directed definition is a grammar together with semantic rulesassociated with the productions. These rules are used to compute attribute values. A parse tree augmented with the attribute values at each node is called an annotated parse tree.

For the bottom-up approach I will illustrate now, we annotate a node after having annotated its children. Thus the attribute values at a node can depend on the children of the node but not the parent of the node. We call these synthesizedattributes, since they are formed by synthesizing the attributes of the children.

In chapter 5, when we study top-down annotations as well, we will introduce inherited attributes that are passed down from parents to children.

We specify how to synthesize attributes by giving the semantic rules together with the grammar. That is we give the syntax directed definition.

ProductionSemantic

Ruleexpr → expr1 + termexpr.t := expr1.t || term.t || '+'expr → expr1 - termexpr.t := expr1.t || term.t || '-'expr → termexpr.t := term.tterm → term1 * factorterm.t := term1.t || factor.t || '*'term → term1 / factorterm.t := term1.t || factor.t || '/'term → factorterm.t := factor.tfactor → digitfactor.t := digit.tfactor → ( expr )factor.t := expr.tdigit → 0digit.t := '0'digit → 1digit.t := '1'digit → 2digit.t := '2'digit → 3digit.t := '3'digit → 4digit.t := '4'digit → 5digit.t := '5'digit → 6digit.t := '6'digit → 7digit.t := '7'digit → 8digit.t := '8'digit → 9digit.t := '9'

We apply these rules bottom-up (starting with the geographically lowest productions, i.e., the lowest lines on the page) and get the annotated graph shown on the right. The annotation are drawn in green.