Context-free grammar primer: productions, derivations (leftmost/rightmost), parse trees

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• In Lex, how is a conflict between two matching rules resolved? from Lesson 1.3
• Write the pattern for an identifier as a regular definition. from Lesson 1.2.1
• Which language can a regular expression not describe: all identifiers, or all strings of n opening brackets followed by n closing brackets? from Lesson 0.2.2

1 · The Story

📖

The Sentence Desk rulebook

Kabir at the Sentence Desk receives stamped words and must decide whether they form a proper sentence. He keeps a rulebook of shapes, each written as a rewrite rule:

Sentence → Subject Verb
Subject → Article Noun | Name
Article → the
Noun → price | milk
Verb → rose | fell
Name → Ramesh

To check “the price rose”, Kabir starts from Sentence and keeps replacing one category by one of its shapes until only real words are left: Sentence, then Subject Verb, then Article Noun Verb, then the Noun Verb, then the price Verb, then the price rose. It matches, so the sentence is proper.

He draws the same work as a family chart: Sentence at the top, its parts below it, real words at the bottom. Reading the bottom row from left to right gives back the sentence. And unlike Mira’s pattern cards, his rules can nest: a Subject could itself contain a whole clause, as deep as needed.

2 · Predict First

🤔

Kabir always replaced the leftmost category first. If he always replaced the rightmost one instead, would he reach a different family chart for “the price rose”? Write your guess down. The answer is in the vault.

3 · Core Concept

Context-free grammar

A context-free grammar (CFG) has four parts:

• terminals: the actual tokens (id, +, (, if, …);
• nonterminals: categories such as E, Stmt, that stand for sets of token strings;
• productions: rules A → α, where A is one nonterminal and α a string of terminals and nonterminals (α may be ε);
• a start symbol, one nonterminal (by convention the left side of the first production).

Notation: A → α | β is shorthand for two productions with the same left side. Upper-case letters are nonterminals; lower-case letters, digits, operators and bold words are terminals.

Derivations

One derivation step αAβ ⇒ αγβ replaces one nonterminal A by the right side of one of its productions A → γ. ⇒* means zero or more steps, ⇒⁺ one or more.

A string of grammar symbols derivable from the start symbol is a sentential form; a sentential form with only terminals is a sentence. The language L(G) is the set of all sentences.

• Leftmost derivation: always replace the leftmost nonterminal (⇒lm).
• Rightmost derivation: always replace the rightmost nonterminal (⇒rm), also called canonical derivation.

Parse tree

A parse tree shows a derivation without the order of steps:

• the root is the start symbol;
• each interior node is a nonterminal A whose children, left to right, are the right side of a production A → X₁ … Xₙ (a single ε leaf for A → ε);
• leaves are terminals (or ε); read left to right, they give the derived string, the yield.

Every parse tree has exactly one leftmost and one rightmost derivation, and they always have the same number of steps (one step per interior node).

Grammars are stronger than regular expressions

S → a S b | ε generates exactly {aⁿbⁿ : n ≥ 0}, which no regular expression can describe. S → ( S ) S | ε generates all balanced bracket strings. Every language described by a regular expression also has a grammar, so grammars are strictly more powerful. That is why the lexer uses regular expressions for words and the parser uses a grammar for structure.

Story → compiler term

4 · Visual

E → E + T | T
T → T * F | F
F → ( E ) | id

Parse tree of id + id * id in the expression grammar. Green leaves are terminals; blue nodes are nonterminals. The * subtree sits lower, so it is grouped first.

5 · Worked Examples

Example 1 Easy

Derive a a b b from S → a S b | ε and draw its parse tree.

Solution

S ⇒ a S b ⇒ a a S b b ⇒ a a b b (the last step uses S → ε). Like Kabir unfolding “Sentence”, each step replaces one S.

Parse tree of aabb; the ε leaf marks S → ε.

Example 2 Medium

Give the leftmost and rightmost derivations of id + id * id in the expression grammar above. How many steps does each take?

Solution

Both are in the table above: 8 steps each, one per interior node of the tree. The leftmost one expands the first E, T, F on the left before touching the right part; the rightmost one finishes T * F first.

Example 3 GATE

For S → a S a | b S b | a | b | ε, which of abba, aab, baaab, abab are in L(G)?

Solution

This grammar generates exactly the palindromes over {a, b}: each step adds the same symbol at both ends. abba ✔ (S ⇒ aSa ⇒ abSba ⇒ abba), baaab ✔ (S ⇒ bSb ⇒ baSab ⇒ baaab), aab ✘ and abab ✘ (not palindromes). Verified by counting parse trees for each string.

6 · Shortcuts

⚡

Number of derivation steps = number of interior nodes of the parse tree, in any order (leftmost, rightmost or mixed). Valid when: any derivation of a sentence.

⚡

Spot the language: rules that add matching symbols at both ends (aSb, aSa) count or mirror; rules like A → aA | ε repeat. Valid when: questions asking what L(G) is.

7 · GATE Traps

⚠️

• A sentential form may contain nonterminals; a sentence may not.
• Leftmost and rightmost derivations of one tree have the same number of steps, but different intermediate forms.
• ε is not a terminal; an ε-production A → ε still counts as a production and as one step.
• The start symbol is the left side of the first production unless the question says otherwise.
• A parse tree’s leaves are terminals or ε, never nonterminals (for a complete tree).

8 · Memory Hook

🧠

Grammar = recipe that rewrites names into words. Leftmost or rightmost is only the order you follow the recipe; the tree is the dish.

9 · Connect the Dots

Kabir’s rulebook can describe nested structure. But what if one sentence fits the rulebook in two different ways? The next lesson studies grammars that allow two parse trees for one string, and how to rewrite them.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markGrammar parts

In the production E → E + T, the symbol + is:

• (A) a nonterminal
• (B) a terminal
• (C) the start symbol
• (D) a sentential form

Q2NAT1 markDerivation steps

In the grammar E → E + T | T, T → T * F | F, F → ( E ) | id, how many steps does the leftmost derivation of id * id take?

Numerical answer: ________

Q3MSQ1 markLanguage

Which strings are generated by S → ( S ) S | ε?

• (A) (())()
• (B) (()
• (C) ()()()
• (D) ε

Q4MCQ1 markDerivations

For a given parse tree, the leftmost and rightmost derivations:

• (A) have the same number of steps
• (B) always have the same intermediate sentential forms
• (C) exist only when the grammar has ε-productions
• (D) differ in the final string

Q5MCQ1 markPower

Which language needs a grammar and cannot be described by a regular expression?

• (A) all identifiers
• (B) { aⁿbⁿ : n ≥ 0 }
• (C) all strings over {a, b} ending in ab
• (D) all unsigned integers

11 · Rule Card

• CFG = terminals, nonterminals, productions A → α, start symbol.
• Derivation step: replace one nonterminal by a right side. Leftmost (⇒lm) / rightmost (⇒rm = canonical).
• Sentential form: derivable string; sentence: all terminals; L(G) = all sentences.
• Parse tree: root = start symbol, interior = nonterminals, leaves = terminals/ε; yield = leaves left to right.
• Steps in any derivation of a tree = number of interior nodes.
• Grammars ⊃ regular expressions (aⁿbⁿ, balanced brackets).

12 · Concept Ledger

context-free grammar (CFG)terminalnonterminalproductionstart symbolderivation ⇒, ⇒*sentential formsentenceL(G)leftmost derivationrightmost (canonical) derivationparse treeyield

13 · Answer Vault