Evaluation Orders for SDD's


"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