Context-Free Grammars
A lexer
hands the parser a flat river of tokens: id, +, id,
*, id. But a program is not flat. a + b * c has a
shape — the multiplication huddles together, then the sum wraps around it — and that shape is
the whole point. Regular expressions, the tool that ruled lexing, are helpless here: they have finite
memory, so they can count neither nesting depth nor matched brackets. Ask a regex to accept exactly the
strings of balanced parentheses (\,()\,) and it simply cannot; the language
\{\,(^n)^n \mid n \ge 0\,\} is the textbook proof, by the pumping lemma, that
regular languages stop short of nesting.
The context-free grammar (CFG) is the machine that captures nesting. It is the single
most important formal object in a compiler's front end: it defines, precisely and finitely, the infinite
set of well-formed programs, and its structure becomes the blueprint for the
parse tree
the parser builds. Where a regular grammar could only chain symbols in a line, a CFG lets a symbol
expand into a pattern that contains itself — recursion — and recursion is exactly what
arithmetic, block structure, and nested function calls demand.
The formal object: a four-tuple
A context-free grammar is a quadruple G = (V, T, P, S). Four ingredients,
nothing more:
-
T — a finite set of terminals: the
atomic tokens the language is built from (here
id, +, *,
(, )). They are the leaves; nothing rewrites them.
-
V — a finite set of nonterminals
(or variables): syntactic categories that stand for sets of strings, such as
E ("an expression") or T ("a term"). Disjoint
from T.
-
P — a finite set of productions, each
of the form A \to \alpha where A \in V is a
single nonterminal and \alpha \in (V \cup T)^{*} is any string of
terminals and nonterminals (possibly empty, written \varepsilon). This
"single symbol on the left" is exactly what "context-free" means.
-
S \in V — the distinguished start symbol;
the whole language is what S can generate.
"Context-free" is a promise about the left-hand side: a production may replace
A by \alpha no matter what surrounds
A. A context-sensitive rule, by contrast, could say "replace
A by \alpha only when a b
sits to its left". Forbidding that context is what keeps parsing tractable.
Notation you will see everywhere
The Dragon Book's conventions are worth memorising, because every paper and tool leans on them:
| Symbol class | Convention | Examples |
|---|
| Terminals | lowercase letters early in the alphabet, digits, operators, boldface keywords | a, b, c, id, +, if |
| Nonterminals | uppercase letters early in the alphabet; S is usually the start | A, B, C, E, T, F |
| Grammar symbols (either) | uppercase letters late in the alphabet | X, Y, Z |
| Strings of terminals | lowercase letters late in the alphabet | u, v, w, x |
| Strings of grammar symbols | lowercase Greek letters | \alpha, \beta, \gamma |
Several productions sharing a left-hand side are collapsed with a vertical bar: the two rules
E \to E + T and E \to T are written together as
E \to E + T \mid T. Each alternative between bars is one production.
The running example: an expression grammar
This four-line grammar for arithmetic expressions will follow you through the entire parsing course. Learn
it now:
\begin{aligned}
E &\;\to\; E + T \;\mid\; T \\
T &\;\to\; T * F \;\mid\; F \\
F &\;\to\; (\,E\,) \;\mid\; \mathbf{id}
\end{aligned}
Read it as three syntactic layers. An expression E is a sum of
terms; a term T is a product of
factors; a factor F is either a
parenthesised expression or a bare identifier. The self-reference in
F \to (\,E\,) — E reappearing inside
F, which sits inside T, which sits inside
E — is the recursion that no regular expression could ever supply, and it is
what lets the grammar nest parentheses to any depth. The layering is not accidental: it silently encodes
that * binds tighter than +, a point the
precedence
page makes explicit.
Here is the parse tree the grammar assigns to \mathbf{id} + \mathbf{id} * \mathbf{id}.
Reveal it top-down and watch the three layers appear:
Notice how \mathbf{id} * \mathbf{id} is gathered into a single
T before the + ever combines it with the left
operand. The tree's shape is the meaning: multiply first, then add. That is the payoff of a
grammar over a plain list of tokens.
Where CFGs sit in the Chomsky hierarchy
Noam Chomsky's 1956 hierarchy nests four families of grammars, each strictly more powerful than the last,
distinguished purely by the shape of the productions they allow:
| Type | Grammar class | Production form | Recogniser |
|---|
| 3 | Regular | A \to aB or A \to a | finite automaton |
| 2 | Context-free | A \to \alpha (single nonterminal on the left) | pushdown automaton |
| 1 | Context-sensitive | \alpha A \beta \to \alpha \gamma \beta | linear-bounded automaton |
| 0 | Unrestricted | any \alpha \to \beta | Turing machine |
The jump from Type 3 to Type 2 is precisely the jump from finite memory to a stack. A
pushdown automaton is a finite automaton plus an unbounded stack, and that stack is exactly what lets it
match arbitrarily deep nesting — remember an open bracket, pop it on the matching close. CFGs and
pushdown automata recognise the same class of languages, which is why a stack-driven parser is the
natural machine for a grammar. Regular languages are a strict subset: every regular language is
context-free, but \{\,(^n)^n\,\} is context-free and not regular.
A grammar is data — so membership is computable
Because a CFG is a finite pile of productions, we can hand it to a program. Below, a grammar is a map from
each nonterminal to its list of alternatives, where each alternative is a list of symbols. A crude but
honest membership test does a bounded breadth-first search over sentential forms: repeatedly expand the
leftmost nonterminal every possible way, and see whether the exact target string of terminals ever falls
out. (Real parsers are vastly smarter — this is just to make "the grammar generates the string" tangible.)
// A production alternative is a list of symbols; a symbol is a string.
// Nonterminals are the map's keys; anything else is a terminal.
type Grammar = Record<string, string[][]>;
const G: Grammar = {
E: [["E", "+", "T"], ["T"]],
T: [["T", "*", "F"], ["F"]],
F: [["(", "E", ")"], ["id"]],
};
const isNonterminal = (s: string) => s in G;
// Does grammar G, from start symbol, derive exactly `target`?
// Bounded BFS over sentential forms, expanding the leftmost nonterminal.
function generates(G: Grammar, start: string, target: string[]): boolean {
const key = (f: string[]) => f.join(" ");
const seen = new Set<string>();
let frontier: string[][] = [[start]];
const maxLen = target.length;
for (let round = 0; round < 40 && frontier.length; round++) {
const next: string[][] = [];
for (const form of frontier) {
if (key(form) === key(target)) return true;
// Prune: a form with no nonterminals can no longer change;
// a form already longer than the target can never shrink.
if (form.length > maxLen) continue;
const i = form.findIndex(isNonterminal);
if (i === -1) continue; // all terminals, but not equal to target
for (const alt of G[form[i]]) {
const grown = [...form.slice(0, i), ...alt, ...form.slice(i + 1)];
const k = key(grown);
if (!seen.has(k)) { seen.add(k); next.push(grown); }
}
}
frontier = next;
}
return false;
}
console.log("id + id * id ->", generates(G, "E", ["id", "+", "id", "*", "id"]));
console.log("( id ) ->", generates(G, "E", ["(", "id", ")"]));
console.log("id + ->", generates(G, "E", ["id", "+"])); // malformed
console.log("+ id ->", generates(G, "E", ["+", "id"])); // malformed
The first two strings are generated; the last two are not. The parsers built later in this course reach
the same verdict, but in linear time and while constructing the tree rather than merely
answering yes or no.
The name is a statement about the left-hand side of productions. In a context-free rule the left side is
a single nonterminal A, so wherever A
appears in a sentential form you may rewrite it — the surrounding symbols, its "context", place no
conditions on the move. A context-sensitive rule
\alpha A \beta \to \alpha \gamma \beta instead demands that
A be flanked by \alpha and
\beta before it may become \gamma. Human languages
really are context-sensitive in places (subject–verb agreement is a long-range constraint), which is one
reason natural-language parsing is so much harder than parsing C. Programming languages are deliberately
kept context-free at the syntactic level, pushing the context-sensitive parts (was this variable
declared? do the types match?) into a later semantic-analysis phase.
Two confusions trip up almost everyone. First, keep grammar and
language apart: a language is the (usually infinite) set of strings; a
grammar is one finite description of that set. Many different grammars can describe the very same
language — for instance E \to E + E \mid \mathbf{id} and our layered grammar
both generate all sums of ids, yet they are different grammars with different (and, as the
ambiguity page shows, differently-behaved) parse trees. The language is what you mean; the grammar is how
you say it.
Second, a grammar is a generative device: reading the productions forwards,
starting from S, produces (generates) every valid string. The dual task —
given a string, decide whether it belongs and recover its structure — is recognition,
and that is the job of an automaton (a pushdown automaton for CFGs) or a parser. Grammar and
automaton are two sides of one coin: one builds strings, the other tears them apart. Do not say "the
grammar parses the input" — the grammar defines what is valid; the parser does the parsing.