CD Notes

Dependency Graphs: Visualizing Attribute Computation Order in Semantic Analysis

Understand dependency graphs for attribute evaluation: node ordering, cycle detection, topological sort algorithms, evaluation schemes, practical implementations in modern compilers with visual examples.

Introduction

A dependency graph is a directed acyclic graph (DAG) that represents attribute dependencies in a parse tree. It shows which attributes must be computed before others, determining the evaluation order for attribute grammar rules.

Purpose

Example

Dependency Graph shows: 1. Which attributes depend on which 2. Valid evaluation orders (topological sorts) 3. Cycles (if grammar not well-formed) 4. Parallel evaluation opportunities

Graph Construction

Algorithm: Building Dependency Graphs

Example

For each parse tree: 1. Create node for each attribute instance 2. For each attribute a computed by rule a := f(b₁, b₂, ...): - Create edge from b₁ to a - Create edge from b₂ to a - ... (for each dependency) Result: DAG showing all attribute relationships

Example: Simple Expression Grammar

Grammar

E → E₁ + T {E.val = E₁.val + T.val}

E → T {E.val = T.val}

T → F {T.val = F.val}

F → num {F.val = num.value}

Parse: 5 + 3

Parse tree

E (val=?)

/ \

E₁ T (val=3)

/ |

T F

| |

5 3

Dependency nodes

F₁.val, T₁.val, T₂.val, E₁.val, E.val, num₁.val, num₂.val

Dependency edges

num₁ → F₁ (num1.value → F1.val)

F₁ → T₁ (F1.val → T1.val)

num₂ → F₂

F₂ → T₂

T₁ → E₁ (T1.val → E1.val)

E₁ → E (E1.val → E.val, T2.val → E.val)

T₂ → E

Evaluation Order Computation

Topological Sort Algorithm

Example

Algorithm: TopologicalSort(Graph): 1. Compute in-degree for each node 2. Queue = [nodes with in-degree 0] 3. result = [] while Queue not empty: node = Queue.pop() result.append(node) for each successor of node: decrement in-degree(successor) if in-degree(successor) == 0: Queue.append(successor) if length(result) < number of nodes: CYCLE DETECTED (not well-formed) return result

Example Topological Sort

Dependency Graph

A → B (A depends on B)

A → C

B → D

C → D

In-degrees

D: 0

B: 1

C: 1

A: 2

Execution

1. In-degree 0: [D]

Process D: decrements B (0), C (0)

Queue: [B, C]

2. Process B: decrements A (1)

Queue: [C]

3. Process C: decrements A (0)

Queue: [A]

4. Process A

Order: D, B, C, A (or D, C, B, A)

Cycle Detection

Algorithm: Detecting Circular Dependencies

Code example

Algorithm: HasCycle(Graph):
  visited = set()
  rec_stack = set()  // Recursion stack
  
  for each node:
    if DFS(node, visited, rec_stack):
      return true  // Cycle found
  
  return false

DFS(node, visited, rec_stack):
  visited.add(node)
  rec_stack.add(node)
  
  for each neighbor of node:
    if neighbor not in visited:
      if DFS(neighbor, visited, rec_stack):
        return true
    elif neighbor in rec_stack:
      return true  // Back edge found (cycle)
  
  rec_stack.remove(node)
  return false

Example: Circular Dependency

Grammar (INVALID)

A.x := B.y

B.y := C.z

C.z := A.x

Dependency graph

A.x → B.y → C.z → A.x

Cycle: A.x → B.y → C.z → A.x

Result: No evaluation order exists ✗

Practical Implementation

Example 1: Multi-Pass Evaluation Strategy

If dependency graph suggests multiple "layers"

1. Input attributes (from tokens)

2. Layer 1 attributes (depend on inputs)

3. Layer 2 attributes (depend on Layer 1)

4. ...

Process in layers (breadth-first)

Pass 1: Compute all Layer 1 attributes

Pass 2: Compute all Layer 2 attributes

...

Example 2: On-The-Fly Attribute Computation

Example

def evaluate_attribute(node, attr_name): # Memoization: prevent recomputation if (node, attr_name) in memo: return memo[(node, attr_name)] # Get the rule that computes this attribute rule = semantic_rule_for(node.production, attr_name) # Recursively evaluate dependencies dependencies = rule.dependencies() dep_values = {} for dep in dependencies: if dep.is_child_attribute: child = node.child_for(dep) dep_values[dep] = evaluate_attribute(child, dep.attr_name) elif dep.is_inherited: # Get inherited from parent dep_values[dep] = node.parent.get_attribute(dep.attr_name) # Compute the attribute result = rule.compute(dep_values) memo[(node, attr_name)] = result return result

Comparing Evaluation Strategies

Strategy 1: Top-Down (Demand-Driven)

Advantages

Compute attributes on-demand
Advantages: Lazy evaluation, only compute needed attributes
Example:
evaluate(E.val):
need E₁.val and T.val
compute E₁.val (recursive)
compute T.val (recursive)
return E₁.val + T.val

Disadvantages

Strategy 2: Bottom-Up (Supply-Driven)

Advantages

Compute all attributes bottom-up post-order
Advantages: Efficient one-pass
Example:
post_order_traversal(tree):
for each child:
post_order_traversal(child)
compute_all_synthesized_attributes(node)

Disadvantages

Strategy 3: Topological Order

Advantages

Compute attributes in order given by topological sort
Advantages: Respect dependencies, efficient
Example:
order = topological_sort(dependency_graph)
for each attribute in order:
compute(attribute)

Disadvantages

Attributes and Parse Trees

Full Dependency Graph Example

Parse tree with attributes

E.val

/ \

E.val T.val

/ \ / |

E₁.val T.val F.val

/ | |

T.val T.val id.val

Dependencies

T.val depends on F.val (via T → F rule)

E.val depends on E₁.val, T.val (via E → E+T rule)

Evaluation order

1. id.val (leaf value)

2. F.val (F → id)

3. T.val (T → F)

4. E₁.val

5. E.val (E → E+T)

Error Handling

Handling Undefined Attributes

Example

def evaluate_attribute_safe(node, attr): if attr not in node.attributes: if attr in computed_cache: return computed_cache[attr] rule = semantic_rule_for(node.production, attr) if rule is None: raise AttributeError(f"No rule for {attr}") try: value = rule.compute(dependencies_computed) computed_cache[attr] = value return value except: # Default value if computation fails return default_value_for(attr)

Quick Revision Notes

Dependency graph: DAG showing attribute computation dependencies
Node: Each attribute instance in parse tree
Edge: From dependency to dependent attribute
Acyclic: Necessary for well-formed attribute grammar
Topological sort: Valid evaluation order
Circular dependency: Indicates grammar malformation
On-demand evaluation: Compute attributes when needed (memoize)
Batch evaluation: Compute in layers or post-order

Interview Q&A

Q1: When would you actually construct an explicit dependency graph?

A: During attribute grammar compiler design or when analyzing attribute flow. For implementation, you typically use implicit dependency ordering (top-down recursion or post-order traversal) without constructing the graph explicitly.

Q2: How do you detect circular dependencies before parsing?

A: Many attribute grammar compilers do static analysis on the grammar rules before parsing any input. If the grammar rules allow circular dependencies, parsing will fail. Good compilers reject such grammars at compile-time.

Q3: Can you have different evaluation orders for the same grammar?

A: Yes! Any topological order of the dependency graph is valid. Multiple different orders may correctly evaluate attributes. However, some orders are more efficient (fewer redundant computations) than others.

Q4: What's the relationship between attribute dependencies and left-recursion?

A: Left recursion can create unusual dependencies. For example, A → Aα might have A.syn depending on its own value. This can still be acyclic if properly structured (like attribute computation over left-associated trees).

Q5: How do memoization and dependency graphs interact?

A: Memoization prevents redundant computation. If you evaluate on-demand and memoize results, you effectively follow dependencies lazily. The dependency graph tells you which orders are valid; memoization ensures efficiency.

Q6: Why is topological sort stable under grammar transformations?

A: If you restructure a grammar (eliminate left recursion, factor prefixes), you change the parse tree structure but not the underlying attribute relationships. The dependency graph should remain equivalent, maintaining evaluation correctness.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Dependency Graphs: Visualizing Attribute Computation Order in Semantic Analysis.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, syntax, directed, translation, dependency

Continue learning this concept

Syntax Directed TranslationAttribute Grammars: Foundation of Semantic Analysis and Code GenerationComprehensive study of attribute grammars in compiler design: attribute definitions, evaluation schemes, dependency graphs, parsing integration, practical implementations for modern compilers with industry examples.Syntax Directed TranslationInherited Attributes: Top-Down Attribute Computation for Context TransferDeep dive into inherited attributes: computation semantics, parent-to-child propagation, L-attributed grammars, evaluation algorithms, practical uses in type checking and code generation with examples.Syntax Directed TranslationSyntax-Directed Definitions: Attribute Grammars for Semantic AnalysisComplete guide to syntax-directed definitions (SDD) with attribute types, semantic rules, translation tables, consistency checking, dependency analysis, and practical compiler implementation techniques.Syntax Directed TranslationSyntax-Directed Translation Schemes: Execution Semantics and Code GenerationMaster syntax-directed translation schemes (SDT) with evaluation order, semantic actions, attribute dependencies, L-attributed vs R-attributed grammars, parsing algorithm integration with complete examples.Syntax Directed TranslationSynthesized Attributes: Bottom-Up Attribute Computation in Compiler DesignIn-depth exploration of synthesized attributes in compilers: definition, computation rules, dependency analysis, parsing table integration, S-attributed grammar implementation with complex examples.Intermediate Code GenerationDirected Acyclic Graphs (DAGs) in Compiler DesignComplete guide to DAGs as intermediate representation covering DAG construction, common subexpression detection, code generation from DAGs, and optimization using DAG representation.

PreviousAttribute Grammars: Foundation of Semantic Analysis and Code Generation NextInherited Attributes: Top-Down Attribute Computation for Context Transfer

CD Notes

Dependency Graphs: Visualizing Attribute Computation Order in Semantic Analysis

Introduction

Purpose

Example

Dependency Graph shows: 1. Which attributes depend on which 2. Valid evaluation orders (topological sorts) 3. Cycles (if grammar not well-formed) 4. Parallel evaluation opportunities

Graph Construction

Algorithm: Building Dependency Graphs

Example

Example: Simple Expression Grammar

Grammar

E → E₁ + T {E.val = E₁.val + T.val}

E → T {E.val = T.val}

T → F {T.val = F.val}

F → num {F.val = num.value}

Parse: 5 + 3

Parse tree

E (val=?)

/ \

E₁ T (val=3)

/ |

T F

| |

5 3

Dependency nodes

F₁.val, T₁.val, T₂.val, E₁.val, E.val, num₁.val, num₂.val

Dependency edges

num₁ → F₁ (num1.value → F1.val)

F₁ → T₁ (F1.val → T1.val)

num₂ → F₂

F₂ → T₂

T₁ → E₁ (T1.val → E1.val)

E₁ → E (E1.val → E.val, T2.val → E.val)

T₂ → E

Evaluation Order Computation

Topological Sort Algorithm

Example

Example Topological Sort

Dependency Graph

A → B (A depends on B)

A → C

B → D

C → D

In-degrees

D: 0

B: 1

C: 1

A: 2

Execution

1. In-degree 0: [D]

Process D: decrements B (0), C (0)

Queue: [B, C]

2. Process B: decrements A (1)

Queue: [C]

3. Process C: decrements A (0)

Queue: [A]

4. Process A

Order: D, B, C, A (or D, C, B, A)

Cycle Detection

Algorithm: Detecting Circular Dependencies

Code example

Algorithm: HasCycle(Graph):
  visited = set()
  rec_stack = set()  // Recursion stack
  
  for each node:
    if DFS(node, visited, rec_stack):
      return true  // Cycle found
  
  return false

DFS(node, visited, rec_stack):
  visited.add(node)
  rec_stack.add(node)
  
  for each neighbor of node:
    if neighbor not in visited:
      if DFS(neighbor, visited, rec_stack):
        return true
    elif neighbor in rec_stack:
      return true  // Back edge found (cycle)
  
  rec_stack.remove(node)
  return false

Example: Circular Dependency

Grammar (INVALID)

A.x := B.y

B.y := C.z

C.z := A.x

Dependency graph

A.x → B.y → C.z → A.x

Cycle: A.x → B.y → C.z → A.x

Result: No evaluation order exists ✗

Practical Implementation

Example 1: Multi-Pass Evaluation Strategy

If dependency graph suggests multiple "layers"

1. Input attributes (from tokens)

2. Layer 1 attributes (depend on inputs)

3. Layer 2 attributes (depend on Layer 1)

4. ...

Process in layers (breadth-first)

Pass 1: Compute all Layer 1 attributes

Pass 2: Compute all Layer 2 attributes

...

Example 2: On-The-Fly Attribute Computation

Example

Comparing Evaluation Strategies

Strategy 1: Top-Down (Demand-Driven)

Advantages

Compute attributes on-demand
Advantages: Lazy evaluation, only compute needed attributes
Example:
evaluate(E.val):
need E₁.val and T.val
compute E₁.val (recursive)
compute T.val (recursive)
return E₁.val + T.val

Disadvantages

Strategy 2: Bottom-Up (Supply-Driven)

Advantages

Compute all attributes bottom-up post-order
Advantages: Efficient one-pass
Example:
post_order_traversal(tree):
for each child:
post_order_traversal(child)
compute_all_synthesized_attributes(node)

Disadvantages

Strategy 3: Topological Order

Advantages

Compute attributes in order given by topological sort
Advantages: Respect dependencies, efficient
Example:
order = topological_sort(dependency_graph)
for each attribute in order:
compute(attribute)

Disadvantages

Attributes and Parse Trees

Full Dependency Graph Example

Parse tree with attributes

E.val

/ \

E.val T.val

/ \ / |

E₁.val T.val F.val

/ | |

T.val T.val id.val

Dependencies

T.val depends on F.val (via T → F rule)

E.val depends on E₁.val, T.val (via E → E+T rule)

Evaluation order

1. id.val (leaf value)

2. F.val (F → id)

3. T.val (T → F)

4. E₁.val

5. E.val (E → E+T)

Error Handling

Handling Undefined Attributes

Example

Quick Revision Notes

Dependency graph: DAG showing attribute computation dependencies
Node: Each attribute instance in parse tree
Edge: From dependency to dependent attribute
Acyclic: Necessary for well-formed attribute grammar
Topological sort: Valid evaluation order
Circular dependency: Indicates grammar malformation
On-demand evaluation: Compute attributes when needed (memoize)
Batch evaluation: Compute in layers or post-order

Interview Q&A

Q1: When would you actually construct an explicit dependency graph?

Q2: How do you detect circular dependencies before parsing?

Q3: Can you have different evaluation orders for the same grammar?

Q4: What's the relationship between attribute dependencies and left-recursion?

Q5: How do memoization and dependency graphs interact?

Q6: Why is topological sort stable under grammar transformations?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Dependency Graphs: Visualizing Attribute Computation Order in Semantic Analysis.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, syntax, directed, translation, dependency

Continue learning this concept

PreviousAttribute Grammars: Foundation of Semantic Analysis and Code Generation NextInherited Attributes: Top-Down Attribute Computation for Context Transfer