"Dependency
graphs" are a useful tool for determining an
evaluation order for the attribute instances in a given parse tree. While an
annotated parse tree shows the values of attributes, a dependency graph helps
us determine how those values can be computed.
A
dependency graph shows the flow of information among the attribute instances in
a particular parse tree; an edge from one attribute instance to another means
that the value of the first is needed to compute the second. Edges express
constraints implied by the semantic rules.
•
Each attribute is associated to a node
•
If a semantic rule associated with a production p
defines the value of synthesized attribute A.b
in terms of the value of X.c, then graph has an edge from X.c to A.b
•
If a semantic rule associated with a production p
defines the value of inherited attribute B.c
in terms of value of X.a, then graph has an edge
from X.a to B.c
Example:
Dependency graph for the annotated parse tree for 3*5
0 comments