3.1 Context-Free Grammars in Compilers, Derivations & Parse Trees

Back to DBMS Notes

📚Module 01Context-Free Grammars, Derivations & Parse Trees⏱️5 min read

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

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Sentence Scaffolding vs Finished Meaning

Imagine a high school English teacher analyzing Shakespearean prose:

1. The Raw Words (Tokens): A linear sequence of words written on paper: ["The", "dog", "bit", "the", "mailman"].
2. The Sentence Diagramming Tree (Concrete Parse Tree): The student draws an elaborate grammatical tree breaking the sentence down into Subject Phrase, Determiner, Noun, Verb Phrase, Transitive Verb, Object Phrase. Every comma, auxiliary word, and article has its own branch.
3. The Semantic Core Meaning (Abstract Syntax Tree): The essential factual action extracted: Bite(Subject: Dog, Object: Mailman). The auxiliary grammar scaffolding has served its purpose and is set aside.

💻 Bridging to Computer Science: Linear Tokens to Hierarchical Derivation Trees

When the lexical analyzer delivers a flat stream of tokens:

[ID, "pos"], [ASSIGN, "="], [ID, "init"], [PLUS, "+"], [ID, "rate"], [STAR, "*"], [NUM, 60]

The CPU cannot execute this directly because a flat array does not convey precedence, associative grouping, or nested control flow. Syntax analysis solves this by applying a Context-Free Grammar (CFG) to construct a hierarchical derivation tree that explicitly determines operator precedence, nesting, and execution order.

📑Table of Contents

• 🏗️ Architectural Foundations: Tokens to Abstract Syntax Trees
  • ⚖️ Concrete Parse Tree vs Abstract Syntax Tree (AST)
• 📐 Formal Mathematical Foundations of Context-Free Grammars
  • 📜 Formal CFG 4-Tuple
  • 🔄 The Derivation Relations (⇒ and ⇒*)
  • 📄 Sentential Forms
• 🧭 Leftmost vs Rightmost Derivations & Sentential Forms
  • ⬅️ Leftmost Derivation (LMD) & LMDT
  • ➡️ Rightmost Derivation (RMD) & RMDT
• 🌳 The Parse Tree & Yield Equivalence Theorem
  • 🌟 Fundamental Equivalence Theorem
• 🔄 Recursive Productions & Grammar Taxonomies
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Arithmetic Derivation and Precedence Trace
  • Example 2: Derivation Steps in Chomsky Normal Form (CNF)
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: Tokens to Abstract Syntax Trees

The syntax analysis phase converts flat lexical streams into minimal semantic trees through four sequential stages:

Architecture Flow

The Syntax Analysis Transformation Pipeline

From a flat token stream to a clean, minimal semantic Abstract Syntax Tree

🔢Stage 1

Token Stream

Linear sequence of terminal tokens emitted by the lexical scanner via getNextToken().

→

CFG Rules

📜Stage 2

Derivation Sequence

Ordered substitution steps replacing non-terminals (Leftmost or Rightmost Derivation).

→

Generates

🌳Stage 3

Concrete Parse Tree

Full syntax tree with every grammatical rule, non-terminal, parenthesis, and delimiter.

→

Prunes Noise

⚡Stage 4

Abstract Syntax Tree

Compact semantic execution tree passed downstream to Type Checking and ICG.

⚖️ Concrete Parse Tree vs Abstract Syntax Tree (AST)

Concrete Parse Tree vs Abstract Syntax Tree (AST)

Contrasting grammatical verification scaffolding against semantic execution trees

Grammatical Scaffolding

Parse Tree (Concrete Syntax Tree)

🌳

Dominant Architecture / DomainSyntax Verification Phase

• •Represents the exact grammatical derivation sequence used by the grammar.
• •Contains every non-terminal, terminal, delimiter, and parenthesis.
• •Bloated with intermediate chain productions (E -> T -> F -> id).
• •Disposed of after syntax analysis to conserve compiler memory.

"Shows how the grammar derived the string down to every single punctuation mark."

Semantic Core

Abstract Syntax Tree (AST)

⚡

Dominant Architecture / DomainIntermediate Code & Optimization Phases

• •Retains only essential semantic operators and operands.
• •Operators form internal nodes; operands form leaf nodes.
• •Discards syntactic clutter like parentheses, semicolons, and commas.
• •Passed downstream to Semantic Analysis, Type Checking, and ICG.

"Retains only what is needed to compute the answer, eliminating syntax noise."

---

📐 Formal Mathematical Foundations of Context-Free Grammars

📜 Formal CFG 4-Tuple

A Context-Free Grammar $G$ is formally defined as a 4-tuple:

$$G = (V, \Sigma, P, S)$$

Where:

• $V$ is a finite set of Non-Terminal symbols (syntactic variables representing language constructs).
• $\Sigma$ is a finite set of Terminal symbols (the tokens delivered by the scanner, where $\Sigma \cap V = \emptyset$).
• $P$ is a finite set of Production rules of the form: $A \to \alpha \quad \text{where } A \in V \text{ and } \alpha \in (V \cup \Sigma)^*$
• $S \in V$ is the designated Start symbol.

🔄 The Derivation Relations (⇒ and ⇒*)

• Derivation: The formal process of deriving a target string from the start symbol by repeatedly applying production rules.
• If $A \to \gamma$ is a production in $P$, and $\alpha, \beta \in (V \cup \Sigma)^*$, we say that $\alpha A \beta$ directly derives $\alpha \gamma \beta$:

$$\alpha A \beta \Rightarrow \alpha \gamma \beta$$

The reflexive and transitive closure of $\Rightarrow$ is denoted as $\Rightarrow^*$, representing zero or more derivation steps:

$$\alpha_0 \Rightarrow \alpha_1 \Rightarrow \alpha_2 \dots \Rightarrow \alpha_n \iff \alpha_0 \Rightarrow^* \alpha_n$$

The language generated by grammar $G$ is the set of all terminal strings derived from start symbol $S$:

$$\mathcal{L}(G) = \{ w \in \Sigma^* \mid S \Rightarrow^* w \}$$

📄 Sentential Forms

• Sentential Form: Any string $\alpha \in (V \cup \Sigma)^*$ that appears at any intermediate step in a derivation from start symbol $S$ ($S \Rightarrow^* \alpha$).
• Left-Sentential Form: An intermediate sentential form appearing in a Leftmost Derivation.
• Right-Sentential Form: An intermediate sentential form appearing in a Rightmost Derivation.
• Sentence: A sentential form containing exclusively terminal symbols ($w \in \Sigma^*$).

---

🧭 Leftmost vs Rightmost Derivations & Sentential Forms

At any step in a derivation containing multiple non-terminals, the compiler must decide which non-terminal to expand next:

⬅️ Leftmost Derivation (LMD) & LMDT

• Definition: The derivation process where at every step, the leftmost non-terminal is expanded first.
• LMDT (Leftmost Derivation Tree): The graphical representation of an LMD.
• Top-down parsers (e.g. LL(1) predictive parsers) construct derivations in Leftmost order.

➡️ Rightmost Derivation (RMD) & RMDT

• Definition: The derivation process where at every step, the rightmost non-terminal is expanded first.
• Canonical Derivation: Rightmost derivation is also formally known as the canonical derivation.
• RMDT (Rightmost Derivation Tree): The graphical representation of an RMD.
• Bottom-up parsers (e.g. LR(0), SLR(1), LALR(1), CLR(1)) construct the reverse of a Rightmost Derivation (bottom-up reductions).

---

🌳 The Parse Tree & Yield Equivalence Theorem

A Parse Tree (or Derivation Tree) is the graphical visualization of a derivation:

• The root node is labeled with the grammar start symbol $S$.
• Each interior node is labeled with a non-terminal $A \in V$.
• If an interior node $A$ has children $X_1, X_2, \dots, X_k$, then $A \to X_1 X_2 \dots X_k$ must be a valid production in $P$.
• The leaf nodes are labeled with terminals, non-terminals, or $\epsilon$.
• Yield of the Tree: The string formed by concatenating all leaf nodes from left to right.

🌟 Fundamental Equivalence Theorem

For any context-free grammar $G$ and any terminal string $w \in \mathcal{L}(G)$:

1. Every distinct parse tree corresponds to exactly one unique Leftmost Derivation.
2. Every distinct parse tree corresponds to exactly one unique Rightmost Derivation.
3. Therefore: $\text{Number of Parse Trees} = \text{Number of LMDs} = \text{Number of RMDs}$

If a string $w$ can be derived by two or more distinct parse trees (or equivalently, two or more distinct LMDs/RMDs), the grammar is Ambiguous.

---

🔄 Recursive Productions & Grammar Taxonomies

A production is recursive if the non-terminal on the LHS also appears on the RHS:

Classification	Formal Structure	Concrete Example	Compiler Significance
Left Recursive	$A \to A\alpha \mid \beta$	$E \to E + T \mid T$	Causes Top-Down (LL) parsers to loop infinitely; easily parsed by Bottom-Up (LR) parsers.
Right Recursive	$A \to \alpha A \mid \beta$	$S \to aS \mid b$	Ideal for Top-Down (LL) parsers; requires deep stack recursion in Bottom-Up parsers.
General Recursive	$A \to \alpha A \beta$	$S \to aSb \mid ab$	Recursion is neither strictly left nor right; enforces matched balanced delimiters.
Non-Recursive	No production contains $A \Rightarrow^+ \dots A \dots$	$S \to aB, B \to b$	Generates only a finite number of strings.

Fundamental Theorem: If a Context-Free Grammar generates an infinite number of strings, it must contain at least one recursive production (or a cycle of mutually recursive productions).

---

🏭 Real-World Production Context: How Industry Builds This

Production compilers like Clang/LLVM and Rustc build Abstract Syntax Trees directly during parsing rather than constructing physical parse trees:

In Clang, every AST node inherits from clang::Stmt or clang::Decl:

// Expression representation for a + b * c:
BinaryOperator '+'
|-- DeclRefExpr 'a'
`-- BinaryOperator '*'
    |-- DeclRefExpr 'b'
    `-- DeclRefExpr 'c'

• Punctuation, parentheses, and intermediate non-terminals (E -> T -> F) are eliminated completely.
• Memory consumption is reduced by over 85% compared to a raw parse tree, improving CPU L1/L2 cache locality during downstream semantic analysis.

---

📐 Numerical Applications & Worked Examples

Example 1: Arithmetic Derivation and Precedence Trace

Consider the standard unambiguous arithmetic expression grammar:

$$\begin{aligned} E &\to E + T \mid T \\ T &\to T \times F \mid F \\ F &\to ( E ) \mid \text{id} \end{aligned}$$

For the input string $w = \text{id} + \text{id} \times \text{id}$:

1. Construct the step-by-step Leftmost Derivation (LMD).
2. Construct the step-by-step Rightmost Derivation (RMD).
3. Verify that both derivations produce the exact same Parse Tree.
4. Explain how this grammar enforces operator precedence ($\times$ over $+$).

Mathematical Formulation & Step-by-Step Solution:

Step 1: Leftmost Derivation (LMD) At each step, expand the leftmost non-terminal:

$$\begin{aligned} E &\Rightarrow_{\text{lm}} E + T && (\text{using } E \to E + T) \\ &\Rightarrow_{\text{lm}} T + T && (\text{using } E \to T) \\ &\Rightarrow_{\text{lm}} F + T && (\text{using } T \to F) \\ &\Rightarrow_{\text{lm}} \text{id} + T && (\text{using } F \to \text{id}) \\ &\Rightarrow_{\text{lm}} \text{id} + T \times F && (\text{using } T \to T \times F) \\ &\Rightarrow_{\text{lm}} \text{id} + F \times F && (\text{using } T \to F) \\ &\Rightarrow_{\text{lm}} \text{id} + \text{id} \times F && (\text{using } F \to \text{id}) \\ &\Rightarrow_{\text{lm}} \text{id} + \text{id} \times \text{id} && (\text{using } F \to \text{id}) \end{aligned}$$

Total steps = 8.

Step 2: Rightmost Derivation (RMD) At each step, expand the rightmost non-terminal:

$$\begin{aligned} E &\Rightarrow_{\text{rm}} E + T && (\text{using } E \to E + T) \\ &\Rightarrow_{\text{rm}} E + T \times F && (\text{using } T \to T \times F) \\ &\Rightarrow_{\text{rm}} E + T \times \text{id} && (\text{using } F \to \text{id}) \\ &\Rightarrow_{\text{rm}} E + F \times \text{id} && (\text{using } T \to F) \\ &\Rightarrow_{\text{rm}} E + \text{id} \times \text{id} && (\text{using } F \to \text{id}) \\ &\Rightarrow_{\text{rm}} T + \text{id} \times \text{id} && (\text{using } E \to T) \\ &\Rightarrow_{\text{rm}} F + \text{id} \times \text{id} && (\text{using } T \to F) \\ &\Rightarrow_{\text{rm}} \text{id} + \text{id} \times \text{id} && (\text{using } F \to \text{id}) \end{aligned}$$

Total steps = 8.

Parse Tree Structural Levels: id + id × id

Hierarchical level-order decomposition proving operator precedence (multiplication binds deeper than addition)

Level 0 (Root)

Start Symbol: E

🌳

Root of the parse tree expanding via E → E + T.

Left Child: EOperator: +Right Child: T

↓Top-level addition operator (+)

Level 1 (Subtree)

Left Term: T | Right Subtree: T × F

🌿

Left E reduces to T; Right T expands via T → T × F enforcing higher precedence.

Left Term T → FRight Operator: ×Right Factor F

↓Deeper subtree forces multiplication (*) to evaluate first

Level 2 (Factors)

Factor Reductions: F → id

🍃

All factors reduce directly to identifier terminal tokens.

id (first)id (second)id (third)

↓Terminal frontier evaluation

Level 3 (Yield)

Sentence Yield: id + id × id

📜

Left-to-right concatenation of all leaf nodes matches target input string exactly.

Token 1: idToken 2: +Token 3: idToken 4: ×Token 5: id

Step 4: Precedence Enforcement Mechanics Notice that the multiplication node $T \times F$ is located deeper in the tree than the addition node $E + T$. In any bottom-up post-order evaluation, the deeper subtree ($T \times F$) must be reduced and computed first. Its result is subsequently added to $E$. Therefore, placing an operator deeper in the grammar hierarchy automatically enforces higher operator precedence.

---

Example 2: Derivation Steps in Chomsky Normal Form (CNF)

Let $G$ be a Context-Free Grammar where every production rule is in Chomsky Normal Form:

• $A \to B C$ (binary non-terminal branch)
• $A \to a$ (terminal leaf)

If a terminal string $w$ has length $n = |w|$, determine:

1. The exact number of derivation steps required to derive $w$.
2. The exact total number of nodes (internal + leaf nodes) in the parse tree of $w$.

Step-by-Step Analytical Solution:

Step 1: Derivation Steps

• We start with $1$ non-terminal ($S$).
• Each application of $A \to B C$ consumes 1 non-terminal and produces 2 non-terminals, increasing the total count of non-terminals by $+1$.
• To obtain a string with $n$ non-terminals from $1$ non-terminal requires exactly: $n - 1 \text{ applications of } A \to B C$
• Each of the $n$ non-terminals must then be converted into a terminal character via $A \to a$, which requires: $n \text{ applications of } A \to a$
• Total derivation steps:

$$\text{Total Steps} = (n - 1) + n = 2n - 1$$

Step 2: Parse Tree Nodes

• Leaf nodes: Exactly $n$ leaves (one for each terminal in $w$).
• Internal nodes: In a strictly binary tree with $n$ leaves, there are exactly $n - 1$ internal nodes.
• Total nodes:

$$\text{Total Nodes} = \text{Internal} + \text{Leaves} = (n - 1) + n = 2n - 1$$

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Does a string having multiple different derivations mean the grammar is ambiguous?"
Key Focus Points:

• No: In any non-trivial unambiguous grammar, every string with more than one non-terminal has at least two distinct derivations: a Leftmost Derivation (LMD) and a Rightmost Derivation (RMD).
• True Ambiguity Criterion: Ambiguity requires that a string has two or more distinct Leftmost Derivations, two or more distinct Rightmost Derivations, or two or more distinct Parse Trees.

Question 2: "What is the formal relationship between the Yield of a parse tree and the derived string?"
Key Focus Points:

• Yield Definition: The yield of a parse tree is the string formed by reading its leaf nodes strictly from left to right.
• Invariant: For any valid parse tree derived from start symbol $S$, its yield must be an exact terminal sentence in the language $\mathcal{L}(G)$.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Is a sentence the same thing as a sentential form?
Answer: No. A sentential form is any intermediate string $\alpha \in (V \cup \Sigma)^*$ derived from $S$ ($S \Rightarrow^* \alpha$), which may contain non-terminals. A sentence is a sentential form that contains strictly terminal symbols ($w \in \Sigma^*$). All sentences are sentential forms, but not all sentential forms are sentences.

Trap 2: Can Top-Down parsers construct Rightmost Derivations?
Answer: No. Top-down parsers (LL) construct derivations from the root down to the leaves in Leftmost order (LMD). Bottom-up parsers (LR) construct the reverse of a Rightmost Derivation (RMD) from leaves up to root.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic2.3 Lex / Flex & Conflict ResolutionNext Topic →3.2 Grammar Ambiguity, Left Recursion & Left Factoring