Information Technology is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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 V where V ∩ Σ = ∅.

  • Production (rule): a pair that describes replacement. Written A → α where A ∈ V and α ∈ (V ∪ Σ)*.

  • Start symbol: a distinguished nonterminal S ∈ V from which derivations begin.

  • Context-free grammar (CFG): a 4-tuple G = (V, Σ, R, S) where (1) V is a finite set of nonterminals, (2) Σ is a finite set of terminals, (3) R is a finite set of productions of the form A → α with A ∈ V and α ∈ (V ∪ Σ)*, and (4) S ∈ V is 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 exist x, y ∈ (V ∪ Σ)*, a nonterminal A ∈ V and a production A → γ ∈ R such that α = x A y and β = 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: ⇒_r and ⇒_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 if A → X1 X2 ... Xk is a production then the node has k ordered children labelled X1, 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 for w. If a production A → ε is used, you may draw A as 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.

  • Exact relation between derivations and trees (standard theorem): For CFG G and w ∈ Σ*, S ⇒* w iff there exists a parse tree with root S whose yield is w. 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 G is ambiguous if there exists at least one string w ∈ L(G) that has two distinct parse trees (equivalently two distinct leftmost derivations). If every w ∈ L(G) has at most one parse tree, G is 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):

  1. S (start)
  2. S ⇒ (S) using S → (S)
  3. (S) ⇒ ((S)) using S → (S) inside
  4. ((S)) ⇒ ((ε)) using S → ε
  5. ((ε)) = (()) (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)):

  1. E ⇒ E + E
  2. E + E ⇒ id + E
  3. id + E ⇒ id + E * E
  4. id + E * E ⇒ id + id * E
  5. id + id * E ⇒ id + id * id

Parse with * at the root (groups as (id + id) * id):

  1. E ⇒ E * E
  2. E * E ⇒ E + E * E
  3. E + E * E ⇒ id + E * E
  4. id + E * E ⇒ id + id * E
  5. id + 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):

  1. S ⇒ a S b
  2. a S b ⇒ a a S b b
  3. a a S b b ⇒ a a a S b b b
  4. a 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

  1. Write the formal definition of a context-free grammar.
  2. What is the difference between ⇒ and ⇒*?
  3. 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?