Context-free grammars and derivations
Context-free grammars (CFGs) define programming-language-like structures using productions; understanding formal definitions, derivations (leftmost/rightmost), and parse trees is essential for parsing, compiler front-ends and designing pushdown automata.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Context-free grammars are the mathematical way to describe hierarchical, nested structures such as expressions, balanced parentheses, and programming-language syntax. Engineers use CFGs when designing parsers, compiler front-ends, interpreters, and when proving properties about languages that require a stack (pushdown automata).
Key ideas
Start with definitions from first principles and build up.
Alphabet: a finite set of symbols. Usually written
Σ. Elements are called terminals.Nonterminal (variable): a symbol that can be replaced during derivation. Usually a finite set
VwhereV ∩ Σ = ∅.Production (rule): a pair that describes replacement. Written
A → αwhereA ∈ Vandα ∈ (V ∪ Σ)*.Start symbol: a distinguished nonterminal
S ∈ Vfrom which derivations begin.Context-free grammar (CFG): a 4-tuple G = (V, Σ, R, S) where (1)
Vis a finite set of nonterminals, (2)Σis a finite set of terminals, (3)Ris a finite set of productions of the formA → αwithA ∈ Vandα ∈ (V ∪ Σ)*, and (4)S ∈ Vis the start symbol. Emphasise: left-hand side is a single nonterminal (this makes it context-free).Sentential form: any string in
(V ∪ Σ)*that can appear during derivation.Terminal string (sentence): a string in
Σ*(contains no nonterminals).Derivation step (single-step): For
α, β ∈ (V ∪ Σ)*, we sayα ⇒ βif there existx, y ∈ (V ∪ Σ)*, a nonterminalA ∈ Vand a productionA → γ ∈ Rsuch thatα = x A yandβ = x γ y. That is, replace one occurrence of a nonterminal by the right-hand side of a production.k-step derivation:
α ⇒^k βif there is a sequence of k single-step derivations fromαtoβ.Reflexive transitive closure:
α ⇒* βmeansαderivesβin zero or more steps.α ⇒+ βmeans in one or more steps.Leftmost derivation: in each single-step, always replace the leftmost nonterminal in the current sentential form. Notation:
α ⇒_l βfor a single leftmost step,⇒_l*for its reflexive-transitive closure.Rightmost derivation: similarly, always replace the rightmost nonterminal. Notation:
⇒_rand⇒_r*.Left-/right-sentential form: a left-sentential form is any sentential form that can appear in some leftmost derivation from
S; a right-sentential form is defined analogously for rightmost derivations.Language generated by a grammar:
L(G) = { w ∈ Σ* | S ⇒* w }.Parse tree (derivation tree): a rooted, ordered tree with
- root labelled by
S, - each interior node labelled by a nonterminal
A, and ifA → X1 X2 ... Xkis a production then the node has k ordered children labelledX1, X2, ..., Xk(each child either terminal or nonterminal), - leaves read left-to-right give a string (the yield). If the yield is
w ∈ Σ*then the tree is a parse tree forw. If a productionA → εis used, you may drawAas a leaf or include a leaf labelledε;εcontributes nothing to the yield.
To draw a parse tree in an exam: draw a root node labelled
S; for each production used, draw the children left-to-right and label each node; put terminals as leaf nodes; finally write the left-to-right sequence of leaves and underline it as the derived string.- root labelled by
Exact relation between derivations and trees (standard theorem): For CFG
Gandw ∈ Σ*,S ⇒* wiff there exists a parse tree with rootSwhose yield isw. Also every leftmost (or rightmost) derivation corresponds to a unique parse tree and vice versa (leftmost/rightmost derivations can be read off the parse tree).Ambiguous grammar: A grammar
Gis ambiguous if there exists at least one stringw ∈ L(G)that has two distinct parse trees (equivalently two distinct leftmost derivations). If everyw ∈ L(G)has at most one parse tree,Gis unambiguous. Note: a language can have both ambiguous and unambiguous grammars; some languages are inherently ambiguous (proofs are nontrivial).
Assumptions to state in solutions: productions are applied one at a time; derivations are finite sequences; ε (epsilon) denotes the empty string and may appear on the right-hand side of productions.
Common derivations professors ask for: show S ⇒* w by giving a leftmost derivation step-by-step, then draw the parse tree whose leaves form w; or prove ambiguity by producing two different leftmost derivations or parse trees for the same terminal string.
Formulas
G = (V, Σ, R, S) — G is a context-free grammar where V (nonterminals), Σ (terminals), R (productions), S (start symbol); applies to the formal definition of a CFG.
α ⇒ β — single-step derivation: replace one nonterminal in α using a production; α,β ∈ (V ∪ Σ)*; explains the atomic rewrite operation.
α ⇒* β — reflexive transitive closure: α derives β in zero or more steps; used to define the language L(G).
L(G) = { w ∈ Σ* | S ⇒* w } — language generated by grammar G; used when asked to prove membership or construct grammars.
A ⇒_l B — leftmost derivation single-step; used when constructing leftmost derivations or proving uniqueness (unambiguity).
A ⇒_r B — rightmost derivation single-step; analogous use for rightmost derivations.
yield(T) = w — if T is a parse tree then the left-to-right concatenation of leaves is w; used to connect parse trees to derivations.
(Units: not applicable; these are formal notations. Use when building proofs or showing parses.)
Worked examples
Example 1 — Balanced parentheses (classic):
Grammar: G1 with V = {S}, Σ = {(, )}, R = {S → SS, S → (S), S → ε}, S start.
Task: derive (()) and draw parse tree.
Solution (leftmost derivation):
S(start)S ⇒ (S)usingS → (S)(S) ⇒ ((S))usingS → (S)inside((S)) ⇒ ((ε))usingS → ε((ε)) = (())(since concatenation withεyields the same string)
Write each step with underlined nonterminal replaced each time; final answer: (()).
Parse tree instructions: draw root labelled S; its child labels correspond to the productions used. For step 2 root S has children ( , S, ); then the inner S again expands similarly; leaves left-to-right are (, (, ), ) which is (()).
Example 2 — Ambiguity in expression grammar:
Grammar G2: V={E}, Σ={id,+,*,(,)}, R={E→E+E, E→E*E, E→(E), E→id}.
Show id+id*id has two parse trees.
Two distinct leftmost derivations (fully spelled out):
Parse with + at the root (groups as id + (id * id)):
E ⇒ E + EE + E ⇒ id + Eid + E ⇒ id + E * Eid + E * E ⇒ id + id * Eid + id * E ⇒ id + id * id
Parse with * at the root (groups as (id + id) * id):
E ⇒ E * EE * E ⇒ E + E * EE + E * E ⇒ id + E * Eid + E * E ⇒ id + id * Eid + id * E ⇒ id + id * id
These two derivations yield the same string id + id * id but have different parse trees, so G2 is ambiguous.
Therefore two distinct parse trees (draw both) show grammar is ambiguous.
To fix ambiguity, give unambiguous grammar with precedence:
E → E + T | T
T → T * F | F
F → (E) | id
Derive id + id * id with leftmost derivation under this grammar to show unique parse tree where * binds tighter than +.
Example 3 — Language { a^n b^n | n ≥ 0 } is context-free.
Grammar: G3 with V={S}, Σ={a,b}, R={S → a S b | ε}.
Derivation for aaabbb (n=3):
S ⇒ a S ba S b ⇒ a a S b ba a S b b ⇒ a a a S b b ba a a S b b b ⇒ a a a ε b b b = aaabbb
Show parse tree: root S expands to a S b three times and last S → ε; leaves left-to-right give aaabbb.
Common mistakes
- Not distinguishing between
⇒(one step) and⇒*(many or zero steps). - Giving two derivations that are actually the same parse (e.g., only different order of showing unrelated steps) when attempting to prove ambiguity.
- Forgetting to show the parse tree when asked — many exam answers require both derivation and tree.
- Using ambiguous grammar for parsing without resolving precedence; professors expect either detection of ambiguity or use of precedence-unambiguous grammar.
- Dropping ε improperly: show where and how ε is used in derivation (explicitly write ε when expanding a nonterminal to empty).
For your exam
Types of questions you will get on this topic:
- Definitions: define CFG, derivation, parse tree, ambiguous grammar. A full-marks answer writes the formal 4-tuple, explains each component, and gives a small example.
- Short notes: leftmost vs rightmost derivations, relation between parse trees and derivations; include a clear statement of equivalence (S ⇒* w iff parse tree with yield w).
- Derivations: given grammar G and string w, show S ⇒* w (provide leftmost derivation step-by-step) and draw the parse tree. Include explicit steps and indicate which production used at each step.
- Ambiguity: show a grammar is ambiguous by producing two different leftmost derivations or two parse trees for the same string; or give an unambiguous grammar for a language with precedence.
- Design problems: construct a CFG for a language (balanced parentheses, a^n b^n, simple arithmetic) and prove correctness by describing derivation for general n or demonstrating closure properties.
What full-marks answers include: precise definitions (bold the terms if asked), symbolically correct derivations (use ⇒, ⇒*), a correctly drawn parse tree (describe node labels and leaves), and clear explanation of why two parse trees are distinct for ambiguity.
Quick check
- Write the formal definition of a context-free grammar.
- What is the difference between
⇒and⇒*? - Give a simple ambiguous grammar and a string it ambiguously derives.
Answers: 1. G = (V, Σ, R, S) with productions of form A → α where A ∈ V, α ∈ (V ∪ Σ). 2. ⇒ is a single-step derivation; ⇒* is zero or more steps (reflexive transitive closure). 3. E → E+E | EE | id is ambiguous; string id+id*id has two parse trees (grouped as id+(id*id) and (id+id)*id).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?