Compiler Design

Evaluation Order & Dependency Graphs

Before attributes can be evaluated, the compiler must determine a valid order of evaluation. This is done by analyzing attribute dependencies across the parse tree.

Dependency Graphs

A Dependency Graph is a directed graph that represents the flow of information among the attribute instances in a parse tree.

Create a node in the dependency graph for each attribute instance associated with each node in the parse tree.
For each semantic rule b := f(c_1, c_2, ..., c_k) associated with a production at a node:
- Draw a directed edge from each c_i to b.
- This directed edge indicates that c_i must be computed before b.
If the resulting dependency graph is a **Directed Acyclic Graph (DAG)**, a topological sort will yield a valid evaluation order.
If the dependency graph contains a **CYCLE**, the SDD is circular and cannot be evaluated.

Circularity and Topological Sort

A topological sort of a DAG is any linear ordering of its nodes such that if there is an edge from node U to node V, then U appears before V in the ordering.

Circularity Detection:

A compiler generator (like Yacc or Bison) checks statically whether a grammar is circular. Circular SDDs represent recursive equations with no base case (e.g. A.val = B.val and B.val = A.val + 1) and are rejected.

Methods of Evaluating Attributes

Compilers utilize different execution strategies depending on the attributes' structural dependencies:

Method	Description	Advantages	Limitations
Parse-tree based (Dynamic)	Builds the complete parse tree, builds the dependency graph, performs a topological sort, and evaluates attributes in that order.	Works for any non-circular SDD.	Memory intensive; requires keeping the full tree in memory; multi-pass.
Rule-based (Static)	The compiler-compiler analyzes the grammar at compile-generation time and determines a fixed evaluation order.	Fast at compile time; no runtime dependency graph required.	Order is statically fixed for all programs.
Oblivious (Postorder)	The evaluation order is independent of actual attributes; it always runs in postorder.	Extremely simple; matches standard parser stack behavior.	Correct only for S-attributed SDDs.
On-the-fly (Single-Pass)	Evaluates attributes incrementally as parsing proceeds, discarding tree nodes.	Highly efficient; fits in a single pass; minimal memory footprint.	Only works for L-attributed SDDs.

S-Attributed & L-Attributed Definitions Symbol Table