JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Designing Context-Free Grammars

Guides 1 and 2 showed you what grammars are and how derivations and parse trees work. Now we flip from reading to writing: given a language you want, how do you actually invent the rules? This is a craft with a handful of reliable moves, and by the end you will design grammars for a^n b^n, balanced brackets, and real arithmetic expressions — precedence and all.

From reading rules to writing them

So far in this rung you have been a reader of grammars: given a context-free grammar and a string, you traced a derivation and drew the parse tree. Designing is the reverse craft. You start with a target — a language you want to generate, every string in it and not one string outside it — and you must invent the variables, the production rules, and the start symbol that hit exactly that target. There is no mechanical algorithm that hands you a grammar from a language description; design is genuinely creative. But it is not guesswork either. A small kit of recurring moves covers an enormous fraction of the languages you will ever meet.

The single most useful habit is to read each variable as a promise about a sub-language. Pick a name, then write down in plain words exactly what set of strings you intend that variable to generate. For example, 'S generates every balanced bracket string' or 'E generates every well-formed arithmetic expression'. Once a variable has such a contract, every rule with that variable on the left must keep the promise: the right-hand side may only mention pieces that are themselves consistent with their own contracts. Design then becomes filling in rules that honor a small set of promises — recursion does the heavy lifting.

Move one: recursion that matches a count

Recall the canary from the regular-languages rung: a^n b^n, the strings of some number of a's followed by exactly that many b's. The pumping lemma proved finite memory cannot count like this, so no regular grammar reaches it. A context-free grammar can, and the trick is the move that makes grammars more powerful than finite automata: a rule that adds matching pieces to both ends at once. Wrap one a and one b around a smaller copy of the same structure, and let the base case stop the recursion at the empty string.

The whole grammar is two rules: S -> a S b | epsilon. The first rule is the wrap, the second is the base case that stops at the empty string (epsilon). Watch a leftmost derivation of aabb fall out: S => a S b (apply the wrap), => a a S b b (wrap again), => a a b b (apply S -> epsilon). The matching parse tree has an S at the root with children a, S, b; that inner S again has children a, S, b; and the innermost S goes to epsilon. Read the leaves left to right and the yield is exactly aabb. Every single rule application contributed one a and one b, so by construction the counts can never differ.

Why does this work where finite memory failed? The recursion is not counting with a number — it is matching with structure. Every a produced by a rule is born paired with its own b in the very same rule application, so they cannot drift out of balance no matter how deep the nesting goes. This is the seed of the pushdown automaton you will meet later in this ladder: the same balance can be enforced by a stack of plates, pushing one per a and popping one per b. Grammar and stack are two faces of the same extra power over finite automata.

Move two: nesting and the language of balanced brackets

Now generalize from one matched pair to arbitrary nesting. The language of balanced brackets contains the empty string, '()', '(())', '()()', '(()())', and every string of parentheses that opens and closes correctly — but not ')(' or '(()'. Two design moves combine here. First, the wrap move from before: a balanced string can be a smaller balanced string surrounded by a fresh pair of brackets. Second, a concatenation move: two balanced strings glued side by side are still balanced. Give the variable S the promise 'S generates exactly the balanced bracket strings', and both moves become rules.

The result is three rules: S -> ( S ) | S S | epsilon. The first wraps a pair around a balanced inside; the second places two balanced strings side by side; the third stops at the empty string. To see them generate (())(), derive S => S S (split into two balanced halves), => ( S ) S (wrap the left half), => ( ( S ) ) S (wrap once more, inside), => ( ( ) ) S (close that inner with epsilon), => ( ( ) ) ( S ) (wrap the right half), => ( ( ) ) ( ) (epsilon). Every '(' is closed by a ')' introduced in the same wrap, so the string can never go unbalanced.

Watch the kit at work. The single recursive variable S, plus a base case, plus self-concatenation, is a pattern you will reuse constantly: it is the skeleton of nested lists, matched HTML or XML tags, block-structured code, and JSON. One honest warning, though: the grammar S -> ( S ) | S S | epsilon is correct but ambiguous — the empty string and even 'SS' admit more than one parse tree, because S S can group left or right. Correctness of the language and uniqueness of the parse are two different goals, and the next move and the whole next guide are about closing that second gap.

Move three: arithmetic expressions with precedence baked in

Now the move that turns toy grammars into the front end of a real compiler: arithmetic expressions like 'a + b * c'. The naive grammar E -> E + E | E * E | ( E ) | a writes the language correctly but is hopelessly ambiguous — 'a + b * c' can parse as '(a + b) * c' or 'a + (b * c)', and only one matches what mathematics means. The fix is not to throw rules away but to encode precedence in the layering of variables. We invent one variable per precedence level and let the levels descend from loosest to tightest binding.

  1. Rank the operators by precedence. Lowest binds loosest (+ and -), then multiplication and division, then the tightest pieces: numbers, names, and anything in parentheses. One variable per rank: E for expressions, T for terms, F for factors.
  2. Make each level build out of the next-tighter level. E is a sum of T's; T is a product of F's; F is the atomic stuff. Because '+' lives only at the E level and '*' only at the T level, a '*' can never accidentally sit above a '+' in the tree.
  3. Encode associativity by which side recurses. Writing E -> E + T (recursion on the LEFT) forces left-associative grouping, so 'a - b - c' parses as '(a - b) - c' — the way subtraction actually works.
  4. Let parentheses re-enter at the bottom: F -> ( E ). This lets a parenthesized expression act as a single tight factor, which is exactly how brackets override precedence in real arithmetic.
Unambiguous expression grammar (precedence + associativity built in)

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

Parse of  a + b * c  is now FORCED:

            E
          / | \
         E  +  T
         |    /|\
         T   T * F
         |   |   |
         F   F   c
         |   |
         a   b

The '*' node sits BELOW the '+' node, so b * c is grouped
first -- i.e. a + (b * c), the mathematically correct reading.
One variable per precedence level (E, T, F) makes the single correct parse tree the only possible one. Multiplication binds tighter because it is generated deeper in the grammar.

Sit with what just happened, because it is the crux of practical grammar design. We did not change the language — the new grammar generates exactly the same set of strings as the naive one. What changed is the shape of the trees, and since the tree is what a compiler walks to compute meaning, shaping the tree is shaping the semantics. Precedence and associativity are not separate features bolted on afterward; they are consequences of how you layer variables and which side you recurse on. This single technique reappears every time you write a grammar for a programming language.

What design cannot reach, and honest limits

Two honesty points keep your expectations calibrated. First, removing ambiguity from a grammar is a craft you can often pull off — but some languages are inherently ambiguous: every context-free grammar for them is ambiguous, and no rewrite can fix it. The standard example is the language of strings a^i b^j c^k where i = j OR j = k. Inherent ambiguity is a property of the language itself, not a failure of your cleverness, so do not waste hours hunting for an unambiguous grammar that provably cannot exist.

Second, context-free grammars are powerful but not all-powerful. The wrap move matches one pair of counts, and nesting handles arbitrary depth — but a grammar cannot enforce two independent matched counts at once. The language a^n b^n c^n (equal numbers of all three) is not context-free; you will prove this later with the pumping lemma for context-free languages. As a rule of thumb, grammars excel at one layer of nesting or matching but cannot keep two unrelated tallies in sync. That boundary is exactly the Chomsky hierarchy rung above context-free, where you need a more powerful machine.