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 T’ has
an inherited attribute inh as
well as a synthesized attribute val. T’ inherits
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