Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 59 · Context-Free Grammars

Context-Free Grammars, Derivations and Parse Trees

Learn context-free grammars, leftmost and rightmost derivations, parse trees and how a grammar defines a language, with design patterns and Python code.

Regular languages cannot count or match nested structure, yet programming languages are full of nesting: parentheses, blocks, expressions inside expressions. Context-free grammars (CFGs) are the notation designed for such recursive structure. They are the foundation of parsers, and every programming-language specification you have read, from JSON to C, is written as a CFG in disguise (BNF).

Definition

A context-free grammar is a 4-tuple G = (V, T, P, S) like the grammars from the Chomsky hierarchy lesson, where every production has the form A → α: one variable on the left, and any string α of variables and terminals (possibly empty) on the right. "Context-free" means that A can be replaced by α wherever it appears, regardless of the symbols around it.

The language of G is L(G) = { w ∈ T* : S ⇒* w }. A language is context-free (a CFL) if some CFG generates it. Every regular language is context-free, but CFLs go further.

A first example: balanced parentheses

TEXT
S -> ( S ) S | ε

The rule says: a balanced string is either empty, or an opening parenthesis, a balanced string, a closing parenthesis, and then another balanced string. This single recursive definition generates (), (()), ()() and so on, a language that no finite automaton can recognize.

Derivations

A derivation applies productions one at a time. Two disciplined orders are especially useful:

  • Leftmost derivation: always replace the leftmost variable.
  • Rightmost derivation: always replace the rightmost variable.

For the grammar S → (S)S | ε, the leftmost derivation of ()() is

S ⇒ (S)S ⇒ ()S ⇒ ()(S)S ⇒ ()()S ⇒ ()()

Each intermediate string, a mix of terminals and variables, is a sentential form.

Parse trees

A parse tree (derivation tree) shows how a string was derived, ignoring the order in which independent variables were expanded. The root is the start variable; each internal node is a variable whose children, from left to right, are the right side of the production used; the leaves, read left to right, spell the derived string (the yield). A parse tree corresponds to exactly one leftmost derivation and exactly one rightmost derivation, which is why ambiguity (several trees for one string) is a property of the trees.

Here is the classic expression grammar:

TEXT
E -> E + T | T
T -> T * F | F
F -> ( E ) | id

It encodes operator precedence in its layering: * binds tighter than + because multiplication lives deeper in the grammar. The parse tree of id + id * id:

flowchart TB
    E0["E"] --> E1["E"]
    E0 --> P["+"]
    E0 --> T0["T"]
    E1 --> T1["T"]
    T1 --> F1["F"]
    F1 --> I1["id"]
    T0 --> T2["T"]
    T0 --> M["*"]
    T0 --> F3["F"]
    T2 --> F2["F"]
    F2 --> I2["id"]
    F3 --> I3["id"]

The multiplication (T → T * F) sits below the plus, so it is evaluated first. The grammar builds precedence into the tree.

Python Leftmost and rightmost derivations from one parse tree

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both derivations use the same productions and have the same tree; only the order differs. In compilers, a top-down parser builds the leftmost derivation, while a bottom-up parser traces a rightmost derivation in reverse.

Testing membership in code

To check whether a string is in L(G), a simple method (for grammars without left recursion) is to try each production and see which positions in the input the variable can consume. The function ends(symbol, i) returns every position where a derivation of symbol starting at position i could end.

Python A small recursive recognizer for a CFG

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The recognizer finds exactly the balanced strings, agrees with Python on every palindrome up to length 8, and for the a^n b^m c^m grammar accepts abc, aabbcc, bbcc and ε but not aabcc (the b's and c's must match). Because ends explores every alternative, the grammar can be ambiguous or nondeterministic with no problem; efficient general algorithms (CYK, Earley) improve on this basic idea.

Designing grammars: patterns

Grammar design is recursion design. These recipes cover most exercises.

  • Matched pairs / nesting. For a^n b^n use S → aSb | ε: each step adds a symbol on both ends. For a^n b^(2n) use S → aSbb | ε.
  • Union of languages. For L1 ∪ L2, add S → S1 | S2 with separate grammars for each. Example: {a^n b^n} ∪ {a^n b^(2n)} is S → S1 | S2, S1 → aS1b | ε, S2 → aS2bb | ε.
  • Concatenation. For L1 L2 use S → S1 S2. Example: a^n b^m c^m is S → A B with A for a's and B for the matched b^m c^m.
  • Star. For L1* use S → S1 S | ε.
  • Palindromes. Build from the outside in: S → aSa | bSb, with middle choices a, b or ε.
  • Equal counts, any order. S → aSbS | bSaS | ε generates every string with the same number of a's and b's.
  • Independent counts joined by a constraint, like a^i b^j c^k with i = j or j = k. Use a union of two grammars, one for each condition.

A language like {a^n b^n c^n} cannot be handled this way: it needs three matched counts, which a CFG cannot track (it is context-sensitive; see the pumping lemma for CFLs).

Grammar versus language

A language can have many grammars. The grammar S → aSb | ε and the grammar S → aSb | ab | ε generate the same language. When two grammars generate the same language we call them equivalent. Some are better than others: shorter, unambiguous, free of useless rules. The next lessons show how to detect ambiguity, clean up grammars with simplification and standardize them with normal forms.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What makes a grammar context-free?

    A production A → α may replace A wherever it occurs, regardless of context. That requires a single variable on the left.
  2. 2. What does the yield of a parse tree represent?

    The leaves, read in order, spell the derived string of terminals.
  3. 3. Which grammar generates {a^n b^(2n) : n ≥ 0}?

    Each use of S → aSbb adds one a and two b's, keeping the ratio 1 to 2.
  4. 4. In a leftmost derivation, which variable is replaced at every step?

    That is the definition. Different orders give different derivations but can share the same parse tree.
  5. 5. Why is a^n b^n c^n not generated by any CFG?

    CFG derivations nest like a stack, so they can match two counts at a time but not three independent ones. The pumping lemma for CFLs proves this.

Summary

  • A CFG has productions A → α with one variable on the left; it can express recursive and nested structure that regular languages cannot.
  • Leftmost and rightmost derivations give the order of replacement; a parse tree shows the structure and its leaves spell the string.
  • Grammar layers (E, T, F) encode operator precedence.
  • Design with recursion patterns: matched pairs, union, concatenation, star, palindromes.
  • A language has many equivalent grammars; the following lessons make them unambiguous, simple and standard.

Next: Ambiguity in Context-Free Grammars