The previous chapter ended with a proof that the language 0^n 1^n, a language that looks almost embarrassingly simple, cannot be recognized by any finite automaton and cannot be generated by any regular grammar. This result is not a dead end; it is an invitation to a more powerful family of grammars, ones capable of describing exactly the kind of counting and nesting behavior that regular languages fundamentally lack. That more powerful family is the subject of this chapter: context-free grammars.
Context-free grammars are everywhere in practical computer science, even if the name sounds academic. Every programming language you have ever used, including C from earlier chapters on this site, has its syntax defined using a context-free grammar. When a compiler reports a syntax error, it is essentially saying that your code does not match any valid derivation of the language's grammar. Understanding CFGs is therefore not just a theoretical exercise; it is the doorway into understanding how compilers, interpreters, and even markup languages like HTML actually parse structured text.
In this tutorial, you will learn the formal definition of a context-free grammar, how derivations work, the difference between leftmost and rightmost derivations, how to build a parse tree from a derivation, what it means for a grammar to be ambiguous, and how CFGs relate back to the regular languages studied in earlier chapters. Several fully worked examples are included throughout.
A context-free grammar, commonly abbreviated as CFG, is a formal grammar in which every production rule has a single non-terminal on its left-hand side, with no restriction whatsoever on what appears on the right-hand side, aside from it being built from terminals and non-terminals. This is a significant relaxation compared to the strict right-linear or left-linear format required by regular grammars in the previous chapter.
Formally, a CFG is defined as a 4-tuple (V, Σ, P, S), exactly like the regular grammars studied earlier, where V is the set of non-terminal symbols, Σ is the set of terminal symbols, P is the set of production rules, and S is the start symbol. The key difference lies entirely in P: every rule in P must have the general form A → α, where A is a single non-terminal and α is any string built from terminals and non-terminals, including the empty string.
| Grammar Type | Allowed Right-Hand Side |
|---|---|
| Regular Grammar | A single terminal, optionally followed by a single non-terminal (or the mirror image). |
| Context-Free Grammar | Any combination of terminals and non-terminals, in any order, of any length. |
This added freedom is precisely what allows a CFG to place a non-terminal in the middle of a rule, or to use the same non-terminal on both sides of a rule in a way that creates recursive, nested structure, something a regular grammar's strict format simply does not permit.
Recall from an earlier chapter that no regular expression or finite automaton can correctly recognize the language of balanced parentheses, since doing so requires counting how many opening parentheses remain unmatched. A context-free grammar handles this effortlessly, using recursion.
Non-terminals: { S }
Terminals: { (, ) }
Start symbol: S
Production rules:
S → (S)
S → SS
S → ε
S → (S) (using S → (S)) → ((S)) (using S → (S)) → (()) (using S → ε) Final string: (())
The rule S → (S) is what makes counting possible. Each application wraps the current derivation in one more pair of matching parentheses, and because the same non-terminal S appears on both sides of this rule, the grammar can apply it as many times as needed before finally closing off the recursion with S → ε. This recursive self-reference is exactly the tool that regular grammars are structurally forbidden from using.
The classic language proven non-regular in the previous chapter, L = { 0^n 1^n | n ≥ 0 }, can be generated effortlessly by a small context-free grammar.
Non-terminals: { S }
Terminals: { 0, 1 }
Start symbol: S
Production rules:
S → 0S1
S → ε
S → 0S1 → 00S11 → 000S111 → 000111 (using S → ε) Final string: 000111
Every application of S → 0S1 adds exactly one 0 to the left side and exactly one 1 to the right side simultaneously, guaranteeing that the counts always stay balanced no matter how many times the rule is applied. This is the key structural trick behind almost every CFG designed to enforce a matching count between two symbols.
When a string being derived contains more than one non-terminal at some intermediate step, there is a choice about which non-terminal to expand next. Two standard conventions exist for making this choice consistently: a leftmost derivation always expands the leftmost non-terminal first, while a rightmost derivation always expands the rightmost non-terminal first.
Non-terminals: { S }
Terminals: { a, b }
Start symbol: S
Production rules:
S → SS
S → a
S → b
S → SS → aS (expand the leftmost S first) → ab (expand the remaining S)
S → SS → Sb (expand the rightmost S first) → ab (expand the remaining S)
Both derivations reach exactly the same final string, "ab", but they take a different order of steps to get there. This distinction becomes especially important in compiler design, where leftmost derivations correspond closely to how a top-down parser processes source code, while rightmost derivations correspond closely to how a bottom-up parser operates.
A parse tree, sometimes called a derivation tree, is a visual representation of a derivation, showing exactly how the start symbol was expanded step by step into a final string. The root of the tree is always the start symbol, each internal node represents a non-terminal that was expanded, and the leaves of the tree, read from left to right, spell out the final terminal string.
Using the earlier grammar S → SS | a | b, the parse tree for the string "ab" has the start symbol S at the root, branching into two children, S and S, since the rule S → SS was applied first. The left child S then branches into a single leaf labeled a, and the right child S branches into a single leaf labeled b. Reading the leaves from left to right produces exactly "ab", matching the derived string.
S
/ \
S S
| |
a b
An important property of parse trees is that both the leftmost and rightmost derivations shown earlier for "ab" produce this exact same tree, despite expanding non-terminals in a different order. This is not a coincidence; leftmost and rightmost derivations always agree on the resulting parse tree, since they merely represent two different, equally valid orders of exploring the very same tree structure.
A grammar is considered ambiguous if at least one string in its language can be produced by two or more genuinely different parse trees. Ambiguity is a serious practical concern, since a compiler relying on an ambiguous grammar may not be able to determine a single, consistent meaning for certain valid programs.
Non-terminals: { E }
Terminals: { +, *, id }
Start symbol: E
Production rules:
E → E + E
E → E * E
E → id
Consider deriving the string "id + id * id" using this grammar. There are two structurally different parse trees possible, one where the + is applied at the outermost level of the tree, treating the expression as id + (id * id), and another where the * is applied at the outermost level, treating the expression as (id + id) * id. Since both trees are valid derivations of the exact same string under the exact same grammar, this grammar is ambiguous.
Tree 1 (matches standard math precedence):
E
/|\
E + E
| /|\
id E * E
| |
id id
Tree 2 (does not match standard math precedence):
E
/|\
E * E
/|\ |
E + E id
| |
id id
This ambiguity can be resolved by rewriting the grammar to explicitly encode operator precedence, introducing additional non-terminals so that multiplication is forced to bind tighter than addition, mirroring exactly the kind of precedence rules seen earlier in the chapter on regular expressions. Removing ambiguity, when possible, is an important and recurring theme in the practical use of context-free grammars, especially in compiler construction.
Every regular grammar studied in the previous chapter is automatically a context-free grammar as well, since the restricted right-linear or left-linear format is simply a special case of the more general "single non-terminal on the left, anything on the right" rule that defines CFGs. This means every regular language is also a context-free language, but the reverse is not true.
Languages like balanced parentheses and 0^n 1^n, both demonstrated in this chapter, are context-free but not regular, proving that context-free grammars are strictly more powerful than regular grammars. This relationship, where one class of languages sits entirely inside a larger class, is formalized in the next chapter through the Chomsky hierarchy, which organizes every grammar type studied in this course, and a few more powerful ones, into a clear, nested structure.
| Mistake | Correct Understanding |
|---|---|
| Assuming every CFG rule must have only one symbol on the right-hand side. | A CFG rule can have any combination of terminals and non-terminals on the right-hand side, of any length. |
| Believing leftmost and rightmost derivations produce different parse trees. | Both derivation orders always produce the exact same parse tree for a given string; only the order of expansion steps differs. |
| Assuming every context-free grammar is ambiguous. | Many CFGs are unambiguous, and even an ambiguous grammar can often be rewritten into an equivalent unambiguous one. |
| Confusing context-free grammars with regular grammars. | Every regular grammar is context-free, but context-free grammars allow far more flexible rules and can describe languages regular grammars cannot. |
Context-free grammars significantly extend what formal grammars can describe, dropping the strict positional restrictions of regular grammars in exchange for the ability to express recursive, nested, and counting structures. Through derivations, parse trees, and the important concept of ambiguity, this chapter showed how CFGs generate languages like balanced parentheses and 0^n 1^n that sit entirely beyond the reach of regular languages, while still fully containing every regular language as a special case.
In this tutorial, you learned the formal definition of a CFG, worked through derivations for balanced parentheses and matching symbol counts, explored leftmost versus rightmost derivations and parse trees, and examined what makes a grammar ambiguous. With this foundation, you are ready to move on to the Chomsky hierarchy, which organizes context-free grammars alongside regular grammars and more powerful grammar types into one unified classification.