Evaluating an SDD at the Nodes of a Parse Tree

Parse tree helps us to visualize the translation specified by SDD. 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.


With synthesized attributes, we can evaluate attributes in any bottom-up order, such as that of a postorder traversal of the parse tree. Example: Annotated Parse Tree for 3*5+4n
Inherited attributes are useful when the structure of a parse tree does not match the abstract syntax of the source code. They can be used to overcome the mismatch due to grammar designed for parsing rather than translation.

In the SDD below, the nonterminal Thas an inherited attribute inh as well as a synthesized attribute val. Tinherits F.val from its left sibling F in the production 
T ->F T
SDD for expression grammar with inherited attributes
Annotated Parse Tree for 3*5 using the above SDD is as below.
An SDD with both inherited and synthesized attributes does not ensure any guaranteed order; even it may not have an order at all. For example, consider nonterminals A and B, with synthesized and inherited attributes A.s and B.i, respectively, along with the production and rules as in Fig.5.2. These rules are circular; it is impossible to evaluate either A.s at a node N or B.i at the child of N without first evaluating the other. The circular dependency of A.s and B.i at some pair of nodes in a parse tree is suggested by Fig.

0 comments