6.2 S-Attributed vs L-Attributed SDDs & Evaluation Orders

Back to DBMS Notes

📚Module 01S-Attributed vs L-Attributed SDDs & Evaluation Orders⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Unidirectional Assembly Line vs Hierarchical Briefing

Imagine an automotive manufacturing plant where a car moves along an automated line:

1. S-Attributed (Pure Bottom-Up Assembly):
   • Component workers at the lowest tier manufacture sub-assemblies (engine block, transmission gear, wheel hub).
   • Higher-tier assembly workers only combine finished components delivered from below.
   • Information flows strictly upward ($\uparrow$). No assembly worker ever needs instructions from the finished car above them, nor does any station inspect parts to their right.
2. L-Attributed (Hierarchical Left-to-Right Briefing):
   • The floor supervisor hands down a project spec sheet (inherited from parent $\downarrow$).
   • The station installing the electrical wiring harness inspects the engine already installed by the station to its left ($\leftarrow$).
   • Crucially, no station ever asks for a part from a station to its right ($\to$), because that station hasn't even begun work yet!
   • Information flows downward and strictly left-to-right, making it 100% compatible with single-pass top-down compilers.

💻 Bridging to Computer Science: Single-Pass Left-to-Right Evaluation Invariants

In semantic analysis, compilers classify attribute grammars by their evaluation tractability:

• S-Attributed Definitions: Every attribute is synthesized. They are evaluated naturally during standard bottom-up LR shift-reduce reductions without constructing an explicit parse tree in memory.
• L-Attributed Definitions: Allow both synthesized and inherited attributes, but strictly forbid backward dependencies. Inherited attributes of a child symbol may depend only on parent inherited attributes or symbols to its left. This ensures they can be evaluated on-the-fly during a single Depth-First Search (DFS) traversal.

📑Table of Contents

• 🏗️ Architectural Foundations: S-Attributed vs L-Attributed
• 📐 Formal Mathematical Foundations: Definitions & Invariants
  • 🏛️ S-Attributed Definitions
  • 🌲 L-Attributed Definitions
  • 📊 Formal Set Containment Hierarchy
• 🏗️ Dependency Graphs & Topological Evaluation Orders
  • 🔄 Circularity & Topological Ordering
• ⚙️ Bottom-Up Evaluation of S-Attributed SDDs on an LR Parser
  • 🧱 The Parallel Value Stack
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Rigorous SDD Classification
  • Example 2: Type Declaration SDD & Dependency Tracing
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: S-Attributed vs L-Attributed

S-Attributed vs L-Attributed SDD: Core Architectural Distinctions

The structural boundary between bottom-up synthesis and single-pass left-to-right evaluation

S-Attributed

S-Attributed Definition

⬆️

Dominant Architecture / DomainLR Parsers, Bottom-Up Reductions, Yacc/Bison

• •Every attribute in the grammar is strictly Synthesized.
• •Zero inherited attributes are permitted.
• •Values flow strictly upward from children to parent.
• •Naturally evaluated during bottom-up shift-reduce parsing on a value stack.

"Every S-Attributed SDD is a strict subset of L-Attributed SDDs."

L-Attributed

L-Attributed Definition

➡️

Dominant Architecture / DomainLL Parsers, Depth-First Traversal, Single-Pass Compilers

• •Allows both Synthesized and Inherited attributes.
• •Inherited attributes of child X_j can depend only on parent inherited attributes or left siblings X_1 ... X_{j-1}.
• •Strictly prohibits dependencies on right siblings or child synthesized attributes of parent.
• •Evaluated on-the-fly during a single Depth-First Search (DFS) traversal.

"L stands for Left-to-right: dependencies flow strictly downward and to the right."

---

📐 Formal Mathematical Foundations: Definitions & Invariants

🏛️ S-Attributed Definitions

An SDD is S-Attributed if and only if every attribute of every non-terminal is synthesized.

For every production rule:

$$A \to X_1 X_2 \dots X_n$$

Any semantic rule defining attribute $A.s$ must have the form:

$$A.s = f(X_1.s_1, X_2.s_2, \dots, X_n.s_n)$$

Where $X_i.s_i$ are synthesized attributes of the children, or lexical values of terminal symbols.

🌲 L-Attributed Definitions

An SDD is L-Attributed if for every production $A \to X_1 X_2 \dots X_n$, and each semantic rule computing an inherited attribute $X_j.i$:

1. $X_j.i$ depends only on:
   • Inherited attributes of the parent non-terminal $A$ (i.e. $A.i$).
   • Synthesized or inherited attributes of symbols strictly to the left of $X_j$, namely $X_1, X_2, \dots, X_{j-1}$.
   • Inherited attributes of $X_j$ itself, in such a way that no cycle is formed.
2. Any synthesized attribute of the head $A.s$ depends only on:
   • Inherited attributes of $A$.
   • Any attributes of $X_1, X_2, \dots, X_n$, provided there are no circular dependencies.

⚠️ Strict Non-L-Attributed Invariants: An SDD is immediately disqualified from being L-Attributed if:

1. An inherited attribute of child $X_j$ depends on a synthesized attribute of its parent $A.s$ (which causes an immediate circular deadlock).
2. An inherited attribute of child $X_j$ depends on any attribute of a right sibling $X_k$ where $k > j$.

📊 Formal Set Containment Hierarchy

⚡The Formal SDD Expressive Containment Hierarchylaw

$$\text{S-Attributed SDDs} \subsetneq \text{L-Attributed SDDs} \subsetneq \text{Non-Circular SDDs} \subsetneq \text{All SDDs}$$

Every S-Attributed SDD is automatically L-Attributed because the constraint on inherited attributes is vacuously satisfied (there are zero inherited attributes).

---

🏗️ Dependency Graphs & Topological Evaluation Orders

To determine whether an SDD can be evaluated deterministically, compilers construct a Dependency Graph:

Architecture Flow

SDD Evaluation Pipeline via Dependency Graph

From parse tree to attribute DAG to topological evaluation execution

🌳Stage 1

Parse Tree Construction

Grammar produces parse tree nodes for every production instance.

→

Attach Attributes

🕸️Stage 2

Dependency Graph Formulation

Nodes = attribute instances. Directed edge (u, v) = u is used to compute v.

→

Cycle Check

🔢Stage 3

Topological Sort

Linearizes the DAG into an evaluation order u_1, u_2, ..., u_k.

→

Code Generation

⚡Stage 4

Attribute Evaluation

Execute semantic functions strictly in topological order.

🔄 Circularity & Topological Ordering

• Circularity Theorem: A valid attribute evaluation order exists for a parse tree if and only if its dependency graph contains no directed cycles (it is a Directed Acyclic Graph / DAG).
• A Topological Sort of a DAG produces a linear sequence $u_1, u_2, \dots, u_m$ such that for every directed edge $(u_i, u_j)$, $i < j$.
• If a directed cycle exists ($X.a \to Y.b \to X.a$), the SDD is circular, and no sequential compiler can evaluate the attributes.

---

⚙️ Bottom-Up Evaluation of S-Attributed SDDs on an LR Parser

S-Attributed definitions are exceptionally efficient because they require zero explicit parse tree allocation. They evaluate on-the-fly during bottom-up shift-reduce reductions!

🧱 The Parallel Value Stack

Alongside the state stack, the parser maintains a parallel Value Stack val[]:

State Stack:  [ s0 | s1 | s2 | s3 ]
Value Stack:  [ v0 | v1 | v2 | v3 ]
Top Pointer:                   ^ top

When reducing by production rule $A \to X_1 X_2 \dots X_r$:

1. The RHS symbols occupy the top $r$ positions of the stack: val[top - r + 1] through val[top].

2. The semantic action computes the synthesized attribute:

   $$A.s = f(\text{val}[\text{top} - r + 1], \dots, \text{val}[\text{top}])$$

3. The parser pops $r$ states and values from the stack: $\text{top} = \text{top} - r$.

4. The parser pushes the GOTO state and the newly synthesized value:

   $$\text{top} = \text{top} + 1; \quad \text{val}[\text{top}] = A.s;$$

Value Stack Trace During S-Attributed LR Reduction

Reducing E -> E + T with semantic action val[ntop] = val[top-2] + val[top]

Parser Controller

Grammar Stack

Value Stack

Semantic Engine

1

Parser Controller→Grammar Stack

Identify Handle E + T

2

Parser Controller→Semantic Engine

Execute Semantic Function

3

Grammar Stack→Value Stack

Pop RHS & Push LHS

---

🏭 Real-World Production Context: How Industry Builds This

In industrial compiler engines (such as GNU Bison, Yacc, and LLVM Frontends):

Yacc and Bison natively support only S-Attributed SDDs with actions at the very end of productions (A -> X Y { action }). When an engineer writes an embedded action in Bison:

stmt: IF expr { emit_branch_zero(); } THEN stmt ;

Bison translates this into an L-Attributed equivalent by introducing an empty Marker Non-Terminal ($M$):

$$\begin{aligned} M &\to \epsilon \quad \{ \text{emit\_branch\_zero}(); \} \\ stmt &\to \text{IF} \ expr \ M \ \text{THEN} \ stmt \end{aligned}$$

Because $M \to \epsilon$ is reduced immediately after $expr$ is parsed, its action fires at the exact desired moment!

In hand-written recursive-descent parsers (e.g. Clang, Rustc), L-Attributed inherited attributes are passed as function arguments, while synthesized attributes are returned as function return values:

fn parse_expr(&mut self, inherited_type: Type) -> SynthesizedASTNode {
    // inherited_type passed downward
    let child = self.parse_term(inherited_type);
    // returns synthesized AST node upward
    child
}

---

📐 Numerical Applications & Worked Examples

Example 1: Rigorous SDD Classification

Consider the following grammar and semantic rules over terminals $\{\text{id}, \text{num}\}$ and non-terminals $\{S, A, B, C\}$:

$$\begin{array}{lll} \text{Production} & \text{Semantic Rules} \\ \hline 1)\; S \to A \; B & S.val = A.val + B.val \\ 2)\; A \to \text{id} & A.val = \text{id}.lexval \\ 3)\; B \to A \; C & B.val = A.val \times C.val, \quad C.in = B.val \\ 4)\; C \to \text{num} & C.val = C.in + \text{num}.lexval \\ \end{array}$$

Determine analytically whether this SDD is:

1. S-Attributed
2. L-Attributed
3. Neither S-Attributed nor L-Attributed

Step-by-Step Analytical Solution:

1. Classify Each Attribute:

   • $S.val$: Synthesized (computed for LHS $S$ from RHS $A, B$).
   • $A.val$: Synthesized (computed for LHS $A$ from terminal $\text{id}$).
   • $B.val$: Synthesized (computed for LHS $B$ from RHS $A, C$).
   • $C.in$: Inherited (computed for RHS child $C$).
   • $C.val$: Synthesized (computed for LHS $C$ from $C.in$ and $\text{num}$).

2. Is it S-Attributed?

   • An SDD is S-Attributed if and only if all attributes are synthesized.
   • Attribute $C.in$ is an inherited attribute.
   • Therefore, the grammar is NOT S-Attributed.

3. Is it L-Attributed?

   • Inspect all semantic rules computing inherited attributes.

   • In production (3): $B \to A \ C$, the semantic rule is:

     $$C.in = B.val$$

   • Non-terminal $B$ is the parent (LHS) of the production.

   • For an SDD to be L-Attributed, an inherited attribute of a child $X_j$ can depend only on inherited attributes of the parent or on attributes of symbols to its left.

   • However, $B.val$ is a synthesized attribute of the parent!

   • Furthermore, $B.val$ itself depends on $C.val$ ($B.val = A.val \times C.val$), which in turn depends on $C.in$ ($C.val = C.in + \dots$).

   • This creates an immediate directed cycle in the dependency graph:

     $$B.val \longrightarrow C.in \longrightarrow C.val \longrightarrow B.val$$

4. Verdict: The SDD is Neither S-Attributed nor L-Attributed (it is circular).

---

Example 2: Type Declaration SDD & Dependency Tracing

Given the standard C-style variable declaration grammar:

$$\begin{array}{ll} \text{Production} & \text{Semantic Rules} \\ \hline D \to T \; L & L.in = T.type \\ T \to \textbf{int} & T.type = \text{integer} \\ T \to \textbf{float} & T.type = \text{real} \\ L \to L_1, \; \textbf{id} & L_1.in = L.in, \quad \text{addType}(\textbf{id}.entry, L.in) \\ L \to \textbf{id} & \text{addType}(\textbf{id}.entry, L.in) \\ \end{array}$$

Classify this SDD and trace the attribute evaluation order for the statement float x, y;.

Step-by-Step Analytical Trace:

1. Classification:

   • $T.type$: Synthesized attribute of $T$.
   • $L.in$: Inherited attribute of $L$.
   • In $D \to T \ L$, rule $L.in = T.type$: $T$ is the left sibling of $L$. This satisfies the L-Attributed rule.
   • In $L \to L_1, \textbf{id}$, rule $L_1.in = L.in$: $L_1$ depends on the inherited attribute of its parent $L$. This satisfies the L-Attributed rule.
   • Contains inherited attributes $\implies$ NOT S-Attributed.
   • All inherited attributes depend strictly on left siblings or parent inherited attributes $\implies$ Strictly L-Attributed.

2. Attribute Evaluation Sequence for float x, y;:

   • Step 1: $T \to \textbf{float} \implies T.type = \text{real}$.
   • Step 2: $D \to T \ L \implies L.in = T.type = \text{real}$.
   • Step 3: $L \to L_1, \textbf{id}_2 \implies L_1.in = L.in = \text{real}$.
   • Step 4: $L_1 \to \textbf{id}_1 \implies \text{addType}(\text{entry}(x), \text{real})$.
   • Step 5: $\text{addType}(\text{entry}(y), L.in = \text{real})$.

The information flow is: $T.type$ is synthesized bottom-up, passed horizontally to $L$, and then pushed top-down through $L$ to annotate both identifiers in the symbol table.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Can an L-Attributed SDD be evaluated during bottom-up parsing without modifications?"
Key Focus Points:

• General Case: Not directly, because inherited attributes require top-down information before the handle is completed.
• With Marker Non-Terminals: Any L-Attributed SDD with semantic actions embedded inside rules can be transformed into an S-Attributed equivalent on an LR parser by inserting empty marker non-terminals ($M \to \epsilon$) to execute actions at intermediate positions.

Question 2: "Why does an inherited attribute depending on a parent's synthesized attribute guarantee a circular deadlock?"
Key Focus Points:

• A parent node's synthesized attribute can only be computed after all of its children have finished evaluating.
• If a child requires that synthesized value to begin its own computation, a cyclic dependency is created: the parent waits for the child, while the child waits for the parent.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Assuming an SDD without cycles is always L-Attributed.
Answer: Classic trap. Consider $A \to B \ C$ with rule $B.in = C.val$. The dependency graph is a DAG with zero cycles. However, $B$ (left sibling) depends on $C$ (right sibling). This requires a right-to-left or multi-pass traversal, violating the single left-to-right pass definition of L-attributed grammars.

Trap 2: Believing S-Attributed and L-Attributed are disjoint classes.
Answer: False. S-Attributed is a strict subset of L-Attributed ($\text{S-Attributed} \subset \text{L-Attributed}$). Every S-Attributed SDD is automatically L-Attributed.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic6.1 Syntax-Directed Definitions & Translation SchemesNext Topic →6.3 Type Systems, Type Checking, Expressions & Coercions