Dependency Graph

A dependency graph shows which attributes must be computed before which. Build one for a single arithmetic expression, read off a valid evaluation order with a topological sort, and see why our example is a DAG with no cycles.

Definition

Dependency graph. Given an annotated parse tree, the dependency graph has one node per attribute instance (one attribute at one tree node, e.g. the val on a specific T), and a directed edge b → c whenever the semantic rule that computes c uses b as an input.

A valid evaluation order is any topological sort of this graph: an ordering in which every node appears before all nodes that depend on it. Such an order exists if and only if the graph is acyclic — a DAG (directed acyclic graph).

If the graph has a cycle, some attribute would have to be computed before itself, so no valid order exists and the SDD is rejected for that tree.

The Example

We use one running grammar for arithmetic with a single synthesized attribute, val.

Example

Production Semantic Rule

───────────── ─────────────────────────────

S → E n print(E.val)

E → E1 + T E.val = E1.val + T.val

E → T E.val = T.val

T → T1 * F T.val = T1.val * F.val

T → F T.val = F.val

F → ( E ) F.val = E.val

F → digit F.val = digit.lexval

Input: ( 3 * 5 + 2 ) * 2 n (here n is the end marker / newline).

How each rule becomes edges. Read the right-hand side of every rule: each attribute it uses points into the attribute being defined.

Example

E.val = E1.val + T.val → E1.val → E.val

T.val → E.val

T.val = T1.val * F.val → T1.val → T.val

F.val → T.val

F.val = digit.lexval → digit.lexval → F.val

Because every val is synthesized (computed from children), every edge points from a child attribute up toward its parent.

Solution — Building the Graph

Build the dependency graph for the val instances of ( 3 * 5 + 2 ) * 2. The leaves carry digit.lexval; edges flow upward to the root, where print consumes the top E.val.

Example

digit(3).lexval ─► F.val=3 ─► T.val=3 ──────────────┐

▼

digit(5).lexval ─► F.val=5 ─────────────────► T.val=15 (3 * 5)

│

▼

E.val=15 ──────┐

digit(2).lexval ─► F.val=2 ─► T.val=2 ─────────────────────►│

▼

E.val=17 (15 + 2)

│

▼

F.val=17 (parenthesized)

│

▼

digit(2).lexval ─► F.val=2 ─► ────────────────────────► T.val=34 (17 * 2)

│

▼

E.val=34 ─► print(34)

Every edge points upward (child → parent), so the graph has no cycle — it is a DAG.

A valid topological order. Reading the DAG bottom-up gives one evaluation order in which each attribute is ready before it is used:

Example

F.val=3 (digit 3)

T.val=3 (T = F)

F.val=5 (digit 5)

T.val=15 (3 * 5)

E.val=15 (E = T)

F.val=2 (digit 2)

T.val=2 (T = F)

E.val=17 (15 + 2)

F.val=17 (parenthesized E)

T.val=17 (T = F)

F.val=2 (digit 2)

T.val=34 (17 * 2)

E.val=34 (E = T)

print(34) (S → E n)

Because all edges point up, this single bottom-up pass evaluates every attribute with its inputs already computed. The final print outputs 34.

Cycles — Circular SDDs

Our running example is acyclic, but not every SDD is. A cycle means an attribute depends on itself (directly or transitively), so no topological order — and no evaluation order — exists.

A small contrived pair of rules shows it:

Example

A.s = f(B.i) → B.i → A.s

B.i = g(A.s) → A.s → B.i

Cycle: A.s → B.i → A.s → …

A.s needs B.i, but B.i needs A.s — a 2-node cycle. There is no topological order, so the SDD is unevaluable for that tree and must be rejected.

In contrast, the val grammar above has only child → parent edges, so it can never form such a loop.

S-Attributed and L-Attributed SDDs

Two restricted classes are guaranteed acyclic, so the compiler never has to build or sort a dependency graph — a fixed traversal always works.

Class	Definition	Safe traversal
S-attributed	every attribute is synthesized (child → parent only)	post-order / bottom-up; fits LR parsers
L-attributed	each inherited attribute depends only on the parent and on left siblings	one depth-first, left-to-right pass; fits LL parsers

Our running val grammar is S-attributed — every attribute is synthesized — which is exactly why the single bottom-up pass above just works.

Key Points

A dependency graph has one node per attribute instance and an edge b → c when the rule for c uses b.
A valid evaluation order is a topological sort; it exists iff the graph is a DAG.
For ( 3 * 5 + 2 ) * 2, all val edges point upward, so one bottom-up pass evaluates everything and prints 34.
A cycle (e.g. A.s ↔ B.i) makes an SDD unevaluable.
S-attributed SDDs (like ours) are always acyclic and evaluate in post-order.

Definition

Dependency graph. Given an annotated parse tree, the dependency graph has one node per attribute instance (one attribute at one tree node, e.g. the val on a specific T), and a directed edge b → c whenever the semantic rule that computes c uses b as an input.

If the graph has a cycle, some attribute would have to be computed before itself, so no valid order exists and the SDD is rejected for that tree.

The Example

We use one running grammar for arithmetic with a single synthesized attribute, val.

Example

Production Semantic Rule

───────────── ─────────────────────────────

S → E n print(E.val)

E → E1 + T E.val = E1.val + T.val

E → T E.val = T.val

T → T1 * F T.val = T1.val * F.val

T → F T.val = F.val

F → ( E ) F.val = E.val

F → digit F.val = digit.lexval

Input: ( 3 * 5 + 2 ) * 2 n (here n is the end marker / newline).

How each rule becomes edges. Read the right-hand side of every rule: each attribute it uses points into the attribute being defined.

Example

E.val = E1.val + T.val → E1.val → E.val

T.val → E.val

T.val = T1.val * F.val → T1.val → T.val

F.val → T.val

F.val = digit.lexval → digit.lexval → F.val

Because every val is synthesized (computed from children), every edge points from a child attribute up toward its parent.

Solution — Building the Graph

Build the dependency graph for the val instances of ( 3 * 5 + 2 ) * 2. The leaves carry digit.lexval; edges flow upward to the root, where print consumes the top E.val.

Example

digit(3).lexval ─► F.val=3 ─► T.val=3 ──────────────┐

▼

digit(5).lexval ─► F.val=5 ─────────────────► T.val=15 (3 * 5)

│

▼

E.val=15 ──────┐

digit(2).lexval ─► F.val=2 ─► T.val=2 ─────────────────────►│

▼

E.val=17 (15 + 2)

│

▼

F.val=17 (parenthesized)

│

▼

digit(2).lexval ─► F.val=2 ─► ────────────────────────► T.val=34 (17 * 2)

│

▼

E.val=34 ─► print(34)

Every edge points upward (child → parent), so the graph has no cycle — it is a DAG.

A valid topological order. Reading the DAG bottom-up gives one evaluation order in which each attribute is ready before it is used:

Example

F.val=3 (digit 3)

T.val=3 (T = F)

F.val=5 (digit 5)

T.val=15 (3 * 5)

E.val=15 (E = T)

F.val=2 (digit 2)

T.val=2 (T = F)

E.val=17 (15 + 2)

F.val=17 (parenthesized E)

T.val=17 (T = F)

F.val=2 (digit 2)

T.val=34 (17 * 2)

E.val=34 (E = T)

print(34) (S → E n)

Because all edges point up, this single bottom-up pass evaluates every attribute with its inputs already computed. The final print outputs 34.

Cycles — Circular SDDs

Our running example is acyclic, but not every SDD is. A cycle means an attribute depends on itself (directly or transitively), so no topological order — and no evaluation order — exists.

A small contrived pair of rules shows it:

Example

A.s = f(B.i) → B.i → A.s

B.i = g(A.s) → A.s → B.i

Cycle: A.s → B.i → A.s → …

A.s needs B.i, but B.i needs A.s — a 2-node cycle. There is no topological order, so the SDD is unevaluable for that tree and must be rejected.

In contrast, the val grammar above has only child → parent edges, so it can never form such a loop.

S-Attributed and L-Attributed SDDs

Two restricted classes are guaranteed acyclic, so the compiler never has to build or sort a dependency graph — a fixed traversal always works.

Class	Definition	Safe traversal
S-attributed	every attribute is synthesized (child → parent only)	post-order / bottom-up; fits LR parsers
L-attributed	each inherited attribute depends only on the parent and on left siblings	one depth-first, left-to-right pass; fits LL parsers

Our running val grammar is S-attributed — every attribute is synthesized — which is exactly why the single bottom-up pass above just works.

Key Points

A dependency graph has one node per attribute instance and an edge b → c when the rule for c uses b.
A valid evaluation order is a topological sort; it exists iff the graph is a DAG.
For ( 3 * 5 + 2 ) * 2, all val edges point upward, so one bottom-up pass evaluates everything and prints 34.
A cycle (e.g. A.s ↔ B.i) makes an SDD unevaluable.
S-attributed SDDs (like ours) are always acyclic and evaluate in post-order.