Attribute Evaluation in Syntax Trees: Dependency Graphs, Evaluation Order, and an Example

Attribute evaluation in a syntax tree is the mechanism by which a compiler computes semantic information (types, values, symbol-table bindings, etc.) from the parse structure. In attribute grammar terminology, each node in a syntax tree carries attributes that are computed using semantic rules. There are two common kinds: inherited attribute and synthesized attribute.

A practical way to reason about “which semantic rules must run first” is to build a dependency graph: a graph whose edges represent “attribute B depends on attribute A”. If that dependency graph is acyclic, an evaluation order exists that guarantees every attribute is computed before it is needed. This is closely related to the well-known dependency graph approach used for attribute grammars.

Below, the process is presented in three layers:

1. how to write semantic rules on a syntax tree,
2. how to construct the dependency graph from attribute read/write relationships,
3. how to choose an evaluation order that respects those dependencies (often implemented via a topological order).

3

Footnotes

1. Wikipedia — Attribute grammar (intro to inherited/synthesized attributes) - https://en.wikipedia.org/wiki/Attribute_grammar - Defines attribute grammars and inherited/synthesized attributes. ↩

2. Wikipedia — Syntax tree (parse tree concept used as carrier for attributes) - https://en.wikipedia.org/wiki/Syntax_tree - Provides background on syntax trees as parse representations. ↩

3. Wikipedia — Dependency graph (general concept of modeling dependencies) - https://en.wikipedia.org/wiki/Dependency_graph - General graph-theoretic framing for dependencies. ↩

Key concepts and workflow

Syntax tree nodes are created by parsing. Then semantic rule bodies reference attributes of the current node and related nodes (children, parent, siblings via inherited flow). The compiler then:

• instantiates attributes at each node,
• determines which semantic rules can be evaluated,
• iteratively computes attribute values in a legal order.

The central correctness requirement is: if a semantic rule for attribute $a$ uses attribute $b$ in its expression, then $b$ must be computed before $a$. The dependency graph makes that explicit. Topological order is a natural evaluation order when dependencies form a DAG. In many textbooks, the “acyclic dependency graph” condition is what makes evaluation feasible for general attribute grammars. Well-formedness is the name often used for such guarantees.

3

Footnotes

1. Wikipedia — Attribute grammar (intro to inherited/synthesized attributes) - https://en.wikipedia.org/wiki/Attribute_grammar - Defines attribute grammars and inherited/synthesized attributes. ↩

2. Wikipedia — Syntax tree (parse tree concept used as carrier for attributes) - https://en.wikipedia.org/wiki/Syntax_tree - Provides background on syntax trees as parse representations. ↩

3. Wikipedia — Dependency graph (general concept of modeling dependencies) - https://en.wikipedia.org/wiki/Dependency_graph - General graph-theoretic framing for dependencies. ↩

Construction of dependency graphs from attribute rules

Assume a production of the form:

$$A \rightarrow X_1\,X_2\,\dots\,X_k$$

and semantic rules that assign attributes on the parent $A$ and/or children $X_i$. For example, synthesized rules look like:

$$b \leftarrow f(a_1, a_2, \dots)$$

meaning: attribute $b$ is computed from attributes $a_1,a_2,\dots$.

Dependency graph definition

To construct the dependency graph for a particular syntax tree:

1. Create graph nodes for each attribute occurrence you will compute (e.g., $E.\text{type}$ at a specific tree node).
2. For each semantic rule that assigns a target attribute $t$ from a set of source attributes $\{s_i\}$, add directed edges:

$$s_i \rightarrow t$$

3. The result is a directed graph capturing all “must happen before” relationships.

If the graph contains a cycle, no evaluation order can satisfy all dependencies simultaneously—this is why acyclic dependency conditions are used in practice. A common approach is to compute a topological sorting order of the dependency graph nodes and then evaluate in that order.

3

Footnotes

1. Wikipedia — Attribute grammar (intro to inherited/synthesized attributes) - https://en.wikipedia.org/wiki/Attribute_grammar - Defines attribute grammars and inherited/synthesized attributes. ↩

2. Wikipedia — Syntax tree (parse tree concept used as carrier for attributes) - https://en.wikipedia.org/wiki/Syntax_tree - Provides background on syntax trees as parse representations. ↩

3. Wikipedia — Topological sorting (used to produce a valid evaluation order for DAGs) - https://en.wikipedia.org/wiki/Topological_sorting - States that DAGs admit topological orders, matching feasible attribute evaluation schedules. ↩

Evaluation order of attributes

Given the dependency graph is a DAG, an evaluation order exists. Two standard viewpoints:

1) Rule-triggering view (operational)

Evaluate any semantic rule whose dependencies are already satisfied. After evaluating, mark its target attribute as available; this may enable more rules.

This operational method is equivalent to repeatedly taking nodes with in-degree $0$ in the dependency graph (Kahn-style logic), conceptually producing a topological order.

2) Ordering view (declarative)

Compute a topological order of the dependency graph and evaluate semantic rules in that order. This is often easier to reason about formally.

Inherited vs synthesized implications

• Synthesized attribute: naturally tends to be computable in a bottom-up fashion if the rules only depend on children.
• Inherited attribute: tends to require top-down propagation (parent-to-child), but still can be scheduled safely if dependencies do not form cycles.

A key point: even with inherited attributes, evaluation is correct as long as the dependency graph remains acyclic and every attribute has a defined semantic rule.

3

Footnotes

1. Wikipedia — Attribute grammar (intro to inherited/synthesized attributes) - https://en.wikipedia.org/wiki/Attribute_grammar - Defines attribute grammars and inherited/synthesized attributes. ↩

2. Wikipedia — Syntax tree (parse tree concept used as carrier for attributes) - https://en.wikipedia.org/wiki/Syntax_tree - Provides background on syntax trees as parse representations. ↩

3. Wikipedia — Dependency graph (general concept of modeling dependencies) - https://en.wikipedia.org/wiki/Dependency_graph - General graph-theoretic framing for dependencies. ↩

Example: Type checking and dependency graph for arithmetic expressions

Consider a tiny expression language:

• expressions $E$
• operators $+$ and $*$ on integer literals and identifiers We’ll compute:
• $E.\text{type}$: synthesized type of an expression
• $Env.\text{lookup}$: (conceptually) inherited environment mapping identifiers to types

To keep the example focused, we’ll use a common pattern where types are synthesized from children for operators, while identifier lookup is “inherited-context-driven” (the environment is passed down).

Grammar + semantic rules (informal)

Productions (schematic):

1. $E \rightarrow \text{int}$
   • $E.\text{type} \leftarrow \text{int}$
2. $E \rightarrow id$
   • $E.\text{type} \leftarrow Env[id]$
3. $E \rightarrow E_1 + E_2$
   • $E.\text{type} \leftarrow \text{checkAdd}(E_1.\text{type}, E_2.\text{type})$
4. $E \rightarrow E_1 * E_2$
   • $E.\text{type} \leftarrow \text{checkMul}(E_1.\text{type}, E_2.\text{type})$

Here, $\text{checkAdd}$ and $\text{checkMul}$ return $\text{int}$ if both operands are $\text{int}$ (otherwise they signal a type error). This uses only child synthesized attributes, so the dependency graph for these operator nodes is bottom-up.

Input syntax tree

Take the input:

$$1 + 2 * 3$$

The parse tree is:

• root: $E = E_1 + E_2$
• $E_1 = 1$
• $E_2 = E_3 * E_4$
• $E_3 = 2$, $E_4 = 3$

Dependency graph construction

Attribute nodes (attribute occurrences):

• $\text{T}(1)$: $(E_1.\text{type})$
• $\text{T}(2)$: $(E_3.\text{type})$
• $\text{T}(3)$: $(E_4.\text{type})$
• $\text{T}(2*3)$: $(E_2.\text{type})$
• $\text{T}(1+2*3)$: $(E.\text{type})$

Semantic-rule dependencies:

• $E_1 \rightarrow 1$: $\text{T}(1)$ assigned directly.
• $E_3 \rightarrow 2$: $\text{T}(2)$ assigned directly.
• $E_4 \rightarrow 3$: $\text{T}(3)$ assigned directly.
• $E_2 \rightarrow E_3 * E_4$:
  • $\text{T}(2) \rightarrow \text{T}(2*3)$
  • $\text{T}(3) \rightarrow \text{T}(2*3)$
• $E \rightarrow E_1 + E_2$:
  • $\text{T}(1) \rightarrow \text{T}(1+2*3)$
  • $\text{T}(2*3) \rightarrow \text{T}(1+2*3)$

Evaluation order

A valid topological evaluation order is:

1. compute $\text{T}(1)$, $\text{T}(2)$, $\text{T}(3)$ (independent leaves)
2. compute $\text{T}(2*3)$ from $\text{T}(2)$ and $\text{T}(3)$
3. compute $\text{T}(1+2*3)$ from $\text{T}(1)$ and $\text{T}(2*3)$

This mirrors the intuitive bottom-up flow for synthesized attributes. The dependency graph is what guarantees that any implementation won’t attempt to compute $E_2.\text{type}$ before its children’s types exist.

3

Footnotes

1. Wikipedia — Attribute grammar (intro to inherited/synthesized attributes) - https://en.wikipedia.org/wiki/Attribute_grammar - Defines attribute grammars and inherited/synthesized attributes. ↩

2. Wikipedia — Syntax tree (parse tree concept used as carrier for attributes) - https://en.wikipedia.org/wiki/Syntax_tree - Provides background on syntax trees as parse representations. ↩

3. Wikipedia — Topological sorting (used to produce a valid evaluation order for DAGs) - https://en.wikipedia.org/wiki/Topological_sorting - States that DAGs admit topological orders, matching feasible attribute evaluation schedules. ↩