6.1 Syntax-Directed Definitions (SDD) & Syntax-Directed Translation (SDT) Schemes

Back to DBMS Notes

📚Module 01Syntax-Directed Definitions & Translation Schemes⏱️5 min read

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

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Declarative Blueprint vs The Construction Trigger

A parser alone only checks grammar. It verifies that salary = hours * 50; is a syntactically valid sentence, but it has no understanding of what salary is, whether hours is an integer or string, or what machine instructions to generate.

Semantic Analysis attaches concrete meaning to syntax trees using two complementary formalisms:

1. Syntax-Directed Definition (SDD) — The Declarative Blueprint:
   • Associates mathematical quantities (Attributes) with grammar symbols.
   • For every production rule, it specifies mathematical equations (Semantic Rules) defining how attributes relate to each other.
   • It specifies what values to compute without specifying when or in what order to evaluate them.
2. Syntax-Directed Translation Scheme (SDT) — The Imperative Trigger:
   • Embeds explicit program code fragments (Semantic Actions inside { ... }) directly into the production bodies.
   • It specifies exact execution timing: "When the parser reaches this position during tree traversal or stack reduction, immediately execute this block of code!"

💻 Bridging to Computer Science: Synthesized and Inherited Attribute Propagation

In compiler syntax-directed translation:

• Attributes decorate the parse tree nodes.
• Synthesized Attributes flow strictly upward (from children to parent). They represent bottom-up computations, such as evaluating the numeric value of an expression.
• Inherited Attributes flow downward or laterally (from parent or left siblings to a node). They represent contextual information, such as passing a declared variable type down to a list of identifier names.

📑Table of Contents

• 🏗️ Architectural Foundations: The SDD & SDT Pipeline
  • ⚖️ SDD vs SDT: Declarative vs Imperative Formalisms
• 📐 Formal Mathematical Foundations: Attributes & Rules
  • 🏷️ What is an Attribute?
  • 🌳 Synthesized vs Inherited Attributes
• 🌲 The Annotated Parse Tree (Decorated Parse Tree)
  • Canonical Example: The Desk Calculator SDD
• ⚙️ Syntax-Directed Translation Schemes (SDT)
  • Infix to Postfix Translation via SDT
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Annotated Parse Tree Evaluation
  • Example 2: Type Distribution via Inherited Attributes
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: The SDD & SDT Pipeline

Architecture Flow

The Syntax-Directed Translation Lifecycle

From declarative grammar equations to deterministic attribute evaluation over parse trees

📜Grammar

Context-Free Syntax

Underlying CFG specifying valid syntactic sentences.

→

Decorated with

🏷️SDD

Semantic Rules

Declarative attribute definitions associated with productions.

→

Instantiates

🕸️Graph

Dependency Graph

Directed edges capture data dependencies between node attributes.

→

Topological Sort

⚡Execution

Annotated Tree

Evaluation order executes semantic actions and populates values.

⚖️ SDD vs SDT: Declarative vs Imperative Formalisms

SDD vs SDT: Declarative Specification vs Imperative Action

Contrasting pure attribute equations against parser-synchronized code execution

Declarative

Syntax-Directed Definition (SDD)

📜

Dominant Architecture / DomainTheoretical Formalism, Specification

• •High-level declarative specification; zero order-of-execution constraints.
• •Uses pure mathematical functions without arbitrary side effects.
• •Evaluated over an Annotated Parse Tree using topological sorting.
• •Ideal for formal reasoning and automated compiler generation.

"Specifies what the relationships are; the compiler figures out the evaluation order."

Imperative

Syntax-Directed Translation (SDT)

⚡

Dominant Architecture / DomainYacc, Bison, Production Compilers

• •Imperative execution scheme; embeds action code inside { }.
• •Order of execution is explicitly determined by parser tree traversal.
• •Can perform arbitrary side effects: emit assembly, modify symbol table.
• •Directly implemented during Shift/Reduce bottom-up reductions.

"Specifies exact code to execute at exact moments during parsing."

---

📐 Formal Mathematical Foundations: Attributes & Rules

🏷️ What is an Attribute?

An Attribute is any quantity associated with a grammar symbol $X$. Examples include:

• val: The numeric value of an expression.
• type: The data type of a variable (int, float, pointer).
• addr: The memory location or temporary register holding a value.
• name: The string lexeme of an identifier.

🌳 Synthesized vs Inherited Attributes

Attributes are categorized into two fundamental classes based on how their values flow through the parse tree:

1. Synthesized Attributes (Bottom-Up Flow ⬆️)

An attribute $a$ of non-terminal $A$ is Synthesized if its value at parse tree node $N$ is computed solely from:

• Attribute values of the children of $N$.
• Other attributes of $N$ itself.

For production $A \to X_1 X_2 \dots X_k$:

$$A.a = f(X_1.b, X_2.c, \dots, X_k.d)$$

The Terminal Invariant: Terminals can ONLY possess synthesized attributes! Their values are computed by the lexical analyzer (e.g. NUM.lexval = 42) and supplied directly to the parse tree. Terminals can NEVER have inherited attributes.

2. Inherited Attributes (Top-Down & Sibling Flow ⬇️➡️)

An attribute $b$ of non-terminal $B$ is Inherited if its value at parse tree node $N$ is computed from:

• Attribute values of the parent of $N$.
• Attribute values of the siblings of $N$.
• Other attributes of $N$ itself.

For production $A \to X_1 X_2 \dots B \dots X_k$:

$$B.b = f(A.a, X_1.c, X_2.d)$$

Inherited attributes pass contextual information downward, such as:

• Passing declared variable types from a declaration header down into a list of identifier names.
• Passing base register addresses down into array index offsets.

Attribute Data Flow Topology

Comparing the directional propagation models of Synthesized vs Inherited attributes

Top Tier

Synthesized Attributes (Bottom-Up: ⬆️ Children → Parent)

🌳

A.a = f(X1, X2, ... Xk). Children calculate sub-results and pass them upward to the parent node.

Terminals ONLY possess synthesized attributesComputed naturally during Post-Order reductionsCanonical: Expression values (E.val)

↓Natural match for Shift-Reduce bottom-up parsing

Bottom Tier

Inherited Attributes (Top-Down / Lateral: ⬇️ Parent / ➡️ Siblings → Child)

🌿

B.b = f(Parent.a, LeftSiblings.c). Contextual information passed down from enclosing scope or left siblings.

Terminals CANNOT have inherited attributesComputed during Pre-Order traversalsCanonical: Type distribution (T.type → L.in)

---

🌲 The Annotated Parse Tree (Decorated Parse Tree)

An Annotated Parse Tree (or Decorated Parse Tree) is a standard parse tree where each node displays the concrete values of its associated attributes.

Canonical Example: The Desk Calculator SDD

Consider an SDD that computes the numeric values of arithmetic expressions:

Production	Semantic Rule	Attribute Nature
$L \to E \ \text{n}$	$L.val = E.val$	Synthesized
$E \to E_1 + T$	$E.val = E_1.val + T.val$	Synthesized
$E \to T$	$E.val = T.val$	Synthesized
$T \to T_1 \times F$	$T.val = T_1.val \times F.val$	Synthesized
$T \to F$	$T.val = F.val$	Synthesized
$F \to ( E )$	$F.val = E.val$	Synthesized
$F \to \text{digit}$	$F.val = \text{digit}.lexval$	Synthesized

(Subscripts $E_1$ and $T_1$ are used solely to distinguish production occurrences).

---

⚙️ Syntax-Directed Translation Schemes (SDT)

An SDT embeds semantic action blocks $\{ \dots \}$ within production right-hand sides:

E -> E '+' T    { printf("+"); }
   | T
T -> T '*' F    { printf("*"); }
   | F
F -> ID         { printf("%s", $1); }

Infix to Postfix Translation via SDT

When parsing input a + b * c with the SDT above:

1. F -> ID matches a $\implies$ prints a.
2. F -> ID matches b $\implies$ prints b.
3. F -> ID matches c $\implies$ prints c.
4. T -> T * F reduces $\implies$ prints *.
5. E -> E + T reduces $\implies$ prints +.

Output Stream: a b c * + (Standard Reverse Polish / Postfix Notation!).

---

🏭 Real-World Production Context: How Industry Builds This

In industrial bottom-up compiler generators (such as Yacc, GNU Bison, and Tree-sitter):

Industrial bottom-up parsers do not construct full parse trees in RAM to evaluate synthesized attributes!

• Alongside the state stack, the engine maintains a parallel Value Stack (yyvsp).
• In a semantic action:
  • $$ represents the synthesized attribute of the left-hand side non-terminal ($A$).
  • $1 represents the attribute of the first symbol on the RHS ($X_1$).
  • $2 represents the attribute of the second symbol on the RHS ($X_2$), and so on.
• During reduction by $A \to X_1 X_2 X_3$:

  $$ = $1 + $3;  /* Pops 3 values from value stack, computes sum, pushes result */

• This enables $O(1)$ attribute evaluation on-the-fly during parsing with zero tree allocation!

In production parsers, semantic actions can emit intermediate code, insert records into the global symbol table, or print debug AST dumps directly during the reduction step.

---

📐 Numerical Applications & Worked Examples

Example 1: Annotated Parse Tree Evaluation

Evaluate the annotated parse tree for the input expression:

$$w = 3 \times 5 + 4 \ \text{n}$$

Using the Desk Calculator SDD. Determine the computed val attribute at every node.

Step-by-Step Analytical Trace:

1. Leaf Lexical Values:

   • $\text{digit}_1 (3)$: $lexval = 3$
   • $\text{digit}_2 (5)$: $lexval = 5$
   • $\text{digit}_3 (4)$: $lexval = 4$

2. Evaluate Subtree $3 \times 5$:

   • $F_1 \to \text{digit}_1 \implies F_1.val = 3$.
   • $T_1 \to F_1 \implies T_1.val = 3$.
   • $F_2 \to \text{digit}_2 \implies F_2.val = 5$.
   • $T \to T_1 \times F_2 \implies T.val = T_1.val \times F_2.val = 3 \times 5 = 15$.
   • $E_1 \to T \implies E_1.val = 15$.

3. Evaluate Subtree $+ \ 4$:

   • $F_3 \to \text{digit}_3 \implies F_3.val = 4$.
   • $T_2 \to F_3 \implies T_2.val = 4$.

4. Evaluate Root Expression $E$:

   • $E \to E_1 + T_2 \implies E.val = E_1.val + T_2.val = 15 + 4 = 19$.

5. Top-Level Goal:

   • $L \to E \ \text{n} \implies L.val = E.val = 19$.

Final Result: $L.val = 19$. The semantic evaluation respects operator precedence automatically through tree depth!

---

Example 2: Type Distribution via Inherited Attributes

Consider the variable declaration grammar:

$$\begin{aligned} D &\to T \ L \\ T &\to \text{int} \mid \text{float} \\ L &\to L_1, \ \text{id} \mid \text{id} \end{aligned}$$

Design an SDD using an inherited attribute in_type to propagate the type from $T$ down to all identifiers in list $L$, and insert each identifier with its type into the symbol table.

Step-by-Step Semantic Rules:

Production	Semantic Rule	Attribute Classification
$D \to T \ L$	$L.in\_type = T.type$	$L.in\_type$ is Inherited (from sibling $T$)
$T \to \text{int}$	$T.type = \text{integer}$	$T.type$ is Synthesized
$T \to \text{float}$	$T.type = \text{real}$	$T.type$ is Synthesized
$L \to L_1, \ \text{id}$	$L_1.in\_type = L.in\_type$ $\text{addType}(\text{id}.entry, L.in\_type)$	$L_1.in\_type$ is Inherited (from parent $L$)
$L \to \text{id}$	$\text{addType}(\text{id}.entry, L.in\_type)$	Semantic Action

For input int x, y, z;:

• $T.type = \text{integer}$ is synthesized at $T$.
• $L.in\_type$ inherits $\text{integer}$ from its left sibling $T$.
• As $L$ expands downward, $L_1.in\_type$ inherits $\text{integer}$ from parent $L$.
• Each identifier x, y, z receives type $\text{integer}$ and records it in the symbol table!

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Can terminal symbols ever possess inherited attributes in an SDD?"
Key Focus Points:

• Strict Rule: Never. Terminal symbols can ONLY possess synthesized attributes.
• Reason: Terminal symbols are generated and recognized by the lexical analyzer (scanner). Their attributes (such as lexval or lexeme) are supplied by the lexer before parsing begins and flow upward into the parse tree.

Question 2: "What is the primary difference between an SDD and an SDT?"
Key Focus Points:

• SDD (Syntax-Directed Definition): High-level declarative specification. Uses mathematical equations without evaluation order constraints or arbitrary side effects.
• SDT (Syntax-Directed Translation Scheme): Imperative implementation scheme. Embeds program fragments { actions } directly inside production right-hand sides with explicit execution timing.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Assuming circular dependencies can be evaluated by top-down parsers.
Answer: Impossible. If an SDD has a directed cycle in its dependency graph (e.g. $A.s = B.i + 1$ and $B.i = A.s + 2$), no topological sort exists. The definition is ill-formed, and no parser can evaluate it.

Trap 2: Believing inherited attributes can only flow from parent to child.
Answer: Incomplete. An inherited attribute at node $N$ can receive values from its parent AND from its sibling nodes (specifically its left siblings in L-attributed SDDs).

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic5.4 CLR(1) & LALR(1) Parsing: LR(1) Items, State Merging & Parser HierarchyNext Topic →6.2 S-Attributed vs L-Attributed SDDs & Evaluation Orders