Context-Free Grammars
One nonterminal on the left-hand side, and no ability to look at the surroundings. That single restriction is what makes efficient parsing possible — and what makes "declared before use" someone else's problem.
What can a context-free grammar express that a regular expression cannot, and where does it run out?
A token sequence together with the *derivation tree* a context-free grammar can build over it. The defining property of that tree is that a subtree's shape depends only on the nonterminal at its root — never on its siblings or its parent. That is what "context-free" means, and it is what makes the tree decomposable, memoisable and parseable in cubic time in the worst case.
A grammar is context-free only if every production has exactly one nonterminal and nothing else on its left-hand side. A rule such as a A b → a x b — legal in a context-sensitive grammar — is forbidden, and forbidding it is what buys the parsing algorithms. Any language rule that genuinely needs the surroundings must therefore be enforced after parsing, by [[semantic-analysis]].
Key points
- Context-free means exactly one nonterminal on a production's left-hand side, so a subtree's shape depends only on its root.
- That locality is what every efficient parsing algorithm depends on; adding context to the grammar breaks all of them.
- The added power over regular languages is one unbounded stack, and one stack is exactly what nesting needs.
- A context-free grammar can enforce one unbounded agreement, not two, which is why
a^n b^n c^nand argument-count checking are both out of reach. - C and C++ are not context-free at the syntax level; Python sidesteps indentation by moving it into the lexer.
- Whether an arbitrary context-free grammar is ambiguous is undecidable, so tools report conflicts — a conservative approximation — instead.
The restriction, and what it buys
Chomsky's hierarchy has four levels, and only two of them matter to a compiler engineer. Type 3, regular: recognised by a finite automaton, no memory beyond a bounded state. Type 2, context-free: recognised by a pushdown automaton, which is a finite automaton plus one unbounded stack. Types 1 and 0 — context-sensitive and unrestricted — are where parsing stops being efficient and, in the type 0 case, stops being decidable.
The single structural difference at type 2 is that the left-hand side of a production is one nonterminal, full stop. Because a nonterminal can be expanded without consulting anything around it, a parser can decide the shape of a subtree locally, and can cache the result. Every efficient parsing algorithm — LL, LR, Earley, GLR, packrat — exists because of that locality. Give the grammar surrounding context and all of them stop working.
The stack is what the extra power actually is. A regular language cannot count unboundedly; a context-free one can, because a pushdown automaton pushes on the way in and pops on the way out. That is exactly the shape of nesting, and nesting is exactly what programming languages are made of.
| Regular (type 3) | Context-free (type 2) | |
|---|---|---|
| Recognised by | A finite automaton | A finite automaton plus one stack |
| Memory | Bounded — a fixed number of states | Unbounded, but only stack-shaped |
| Can express | Identifiers, numbers, string literals, comments without nesting | Balanced brackets, nested expressions, block structure |
| Cannot express | Matched parentheses to any depth | Declare-before-use, argument-count agreement, a^n b^n c^n |
| Used in a compiler for | The lexer | The parser |
| Recognition costtypical | Linear, constant memory | Linear for LL/LR grammars, cubic in general |
Nesting is the whole reason
The canonical proof that programming languages are not regular is balanced parentheses. A finite automaton has a fixed number of states, so it can only remember a bounded nesting depth; feed it more open parentheses than it has states and, by the pigeonhole principle, it must revisit a state and lose count. The pumping lemma for regular languages is that argument made rigorous.
A context-free grammar handles it in two productions. The tree it builds *is* the nesting, and the parser's stack is the depth counter the finite automaton did not have. This is why the lexer/parser split falls exactly where it does: everything with bounded structure goes in the lexer, everything with nesting goes in the parser — see [[regular-languages]] for the other half of that argument.
It is also why nested block comments are a lexer design decision rather than a lexer feature. /* /* */ */ is a nesting problem, so a purely regular lexer cannot handle it; implementations that support nested comments — Rust, Swift, D — special-case them with an explicit depth counter in the scanner, which is a small pushdown automaton hiding inside the lexer.
| S | ::= | "(" S ")" S | The nesting case. Each expansion pushes one level; the parse stack is the depth counter. |
| S | ::= | ε | The empty alternative. Without it the grammar generates nothing at all. |
- 1.Sapplying start symbol
- 2."(" S ")" Sapplying S → ( S ) S — depth 1
- 3."(" "(" S ")" S ")" Sapplying S → ( S ) S on the inner S — depth 2
- 4."(" "(" ")" S ")" Sapplying S → ε at depth 2
- 5."(" "(" ")" "(" S ")" S ")" Sapplying S → ( S ) S — the second pair at depth 2
- 6.(()())applying S → ε three times. No finite automaton can do this, because nothing bounds the depth.
Where context-free runs out
a^n b^n c^n is not context-free, and that declare-before-use cannot be expressed context-freely, are theorems, not implementation limitations. No parser generator will ever gain the ability. What varies is the workaround: C uses lexer feedback, Python moves indentation into the lexer, and C++ uses prose disambiguation rules in the standard.The classic non-context-free language is a^n b^n c^n — equal numbers of three symbols. One stack can match two counts against each other; it cannot match three. The pumping lemma for context-free languages is the proof, and the practical translation is: a context-free grammar can enforce one agreement at a time, not two.
Real language rules that fall over this line are everywhere once you look. "Every identifier must be declared" requires an unbounded set of remembered names, not a stack. "A call must have as many arguments as the declaration has parameters" is a second agreement layered on the first. "The types of both operands must match" needs computed information, not matched structure. All of these are why a compiler has phases after the parser at all, and it is not a design preference — it is a formal-language result.
Two well-known languages are not context-free even at the syntax level, and both are worth knowing by name because they explain otherwise inexplicable compiler behaviour.
- C.
A * B;is a multiplication statement ifAis a variable and a pointer declaration ifAis atypedefname. No context-free grammar can tell them apart, so C compilers feed the symbol table back into the lexer — the "lexer hack", covered in[[lexer-hazards]]. - C++. Worse:
A<B>C;is a template instantiation or a chain of comparisons depending on whetherAis a template. The standard resolves several of these with prose rules ("if it can be a declaration, it is a declaration") rather than with grammar, which is where the "most vexing parse" comes from. - Python. Indentation is not context-free either, but Python moves the problem: the lexer emits explicit
INDENTandDEDENTtokens, after which the grammar is ordinary. Relocating the hard part into the lexer is a real design technique. - Rust and Swift. Both keep the grammar context-free and pay for it with syntax that is deliberately unambiguous —
fnandletkeywords, mandatory braces, turbofish::<>for generic arguments in expression position.
Ambiguity is undecidable, and that has consequences
There is no algorithm that takes an arbitrary context-free grammar and reports whether it is ambiguous. This is not "no efficient algorithm" — it is undecidable in the same sense as the halting problem. It follows that no tool can promise "your grammar is unambiguous", and that is why parser generators report *conflicts* instead.
A conflict is a decidable, conservative approximation: Bison can tell you that its LALR construction could not decide between shifting and reducing in some state. That is a genuine defect of the grammar-plus-algorithm pair, but it does not mean the grammar is ambiguous, and an unambiguous grammar can still produce conflicts. Reading a conflict report as "my grammar is ambiguous" leads to the wrong fix roughly half the time — see [[ambiguous-grammars]] for both cases side by side.
How it works
The steps, in the order the compiler takes them.
- Confirm every production has a single nonterminal on the left; if not, the rule belongs in a later phase, not in the grammar.
- Model nesting with a recursive production that consumes the opening token, recurses, and consumes the closing one.
- Push the constructs with bounded structure — identifiers, numbers, strings — down into the lexer, where a finite automaton suffices.
- For any rule that requires remembering an unbounded set of facts, such as declared names, allocate it to name resolution and record it in the symbol table.
- Where a language rule genuinely needs context at parse time, choose a workaround explicitly: lexer feedback, a token-level preprocessing pass, or a syntax change that removes the ambiguity.
- Run the grammar through a generator and read the conflict report as evidence about the grammar-plus-algorithm pair, not as a verdict on ambiguity.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- Nested block comments are added to a language whose lexer is a plain regular scanner, and the first
/* /* */closes the outer comment early — the rest of the file is silently parsed as code and produces a cascade of unrelated errors. - A rule such as "arity must match" is pushed into the grammar with per-arity productions, and the grammar explodes combinatorially until the generator runs out of memory on a large state table.
- A C parser without the lexer hack accepts
A * B;as multiplication whenAis atypedefname, and the failure surfaces as a bizarre type error inside a header everyone assumes is correct. - An author fixes a shift/reduce conflict by adding precedence declarations without checking what they resolved, and a construct that used to parse now silently parses differently — the compiler still builds, the tests still pass, and one expression changes meaning.
When it helps
- Deciding which phase a language rule belongs to: if it needs unbounded memory that is not stack-shaped, it is not syntax and never will be.
- Designing syntax that will be cheap to parse: keeping the grammar context-free is the difference between a parser you can generate and one you must hand-write with feedback.
- Explaining otherwise inexplicable compiler behaviour, such as C++'s most vexing parse or C's dependence on
typedefvisibility.
When it hurts
- When the language is already not context-free — C, C++ — insisting on a pure context-free grammar produces a document that does not describe the compiler, which is worse than admitting the feedback.
- For a small configuration format, the whole hierarchy is overkill: the language is regular, a scanner and a loop are enough, and reaching for a parser generator adds a build dependency for nothing.
What it costs
Every one of these is paid by something.
- Keeping a language context-free buys generated parsers, tooling and a checkable specification, and costs syntax freedom — mandatory keywords, mandatory braces and turbofish syntax are all bills paid for it.
- Allowing lexer feedback buys the syntax you actually wanted and costs the ability to lex and parse independently, which breaks incremental parsing, syntax highlighting of incomplete files and any tool that wants tokens without a symbol table.
- Moving a non-context-free feature into the lexer, as Python does with indentation, buys a clean grammar and costs a lexer that carries state and can no longer be restarted at an arbitrary offset.
What else you could do
What a different compiler or language does instead, and when that is better.
- A context-sensitive or two-level grammar formalism, such as attribute grammars or van Wijngaarden grammars — ALGOL 68 used the latter to specify declare-before-use in the grammar itself, and the result was famously unimplementable in the intended sense.
- Parsing expression grammars, which trade the generative reading for ordered choice plus syntactic predicates; the predicates give limited context sensitivity, and the price is that ambiguity becomes invisible rather than reported — see
[[parser-generators]]. - GLR parsing, which accepts the full context-free class and resolves the leftovers semantically by parsing all readings and discarding the ones that fail type-checking. This is how several C++ frontends survive, and it costs both time and a great deal of machinery.
See it for yourself
The flag, dump or tool that shows you this directly.
bison -Wcounterexamples grammar.y(Bison 3.8 and later) prints an actual pair of inputs that the grammar parses two ways — the closest a tool gets to demonstrating ambiguity.clang -Xclang -ast-dump -fsyntax-only x.conA * B;with and without atypedef A;above it shows the same tokens producing a declaration in one case and an expression statement in the other.python3 -c "import tokenize, io; [print(t) for t in tokenize.generate_tokens(io.StringIO('if x:\n y = 1\n').readline)]"prints theINDENTandDEDENTtokens Python's lexer synthesises.- ANTLR's
-Xlogreports where its adaptive lookahead had to consider more than one alternative, which is the practical stand-in for an ambiguity check.
Plausible wrong readings
Stated the way a confident engineer states them.
- "Programming languages are context-free." Their *core expression and statement syntax* usually is. C and C++ are not, and every language has rules — declaration, typing, arity — that no context-free grammar can express.
- "Context-free means the grammar has no context." It means each production is applied without looking at surroundings. The parse tree has plenty of context; the *rules* may not consult it.
- "A parser generator will tell me if my grammar is ambiguous." It cannot — the question is undecidable. It reports conflicts, which is a different and more conservative claim.
- "If it needs a stack, it needs a parser." It needs a stack *of bounded shape*. Nested comments need a counter, which is why some lexers implement them without becoming parsers.
Misconceptions
The claim, and what is actually true.
A * B; cannot be classified without knowing whether A is a type name. Real C parsers pass symbol-table information back to the lexer to resolve it.Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
Context-free means every rule replaces a single named category with a sequence, without looking at what is around it. That restriction is what lets a parser use a stack and finish quickly. It handles nesting — brackets, blocks, expressions — and it cannot handle rules like "this name must have been declared", which is why compilers have phases after the parser.
practical
The useful test when designing syntax: does this rule require remembering an unbounded set of facts that is not a stack? If yes, it is not syntax. Put it in name resolution or the type checker and you will get a better error message anyway, because those phases can say "no function named foo in scope" while a grammar can only say "unexpected token".
advanced
The interesting engineering question is what you pay to *stay* inside the class. Rust's turbofish exists because f<a>(b) is ambiguous between a generic call and two comparisons, and Rust chose a syntax change over a feedback loop. C++ chose the feedback loop and inherited three decades of most-vexing-parse bugs, template disambiguation keywords and parsers that cannot run without a symbol table. Go chose to eliminate the question by making declarations syntactically distinct with func, var and type. All three are the same decision made differently, and none of them is free — the bill is paid in syntax noise, in parser complexity, or in incremental-tooling capability, and you choose which.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
INDENT/DEDENT behaviour described here is CPython's tokenizer as of 3.12, and the grammar it feeds is the PEG grammar introduced in 3.9 by PEP 617. Before 3.9 the same tokens fed an LL(1) parser. Other Python implementations reproduce the tokenizer behaviour because it is specified, not because they share code.If you were asked this in an interview
- Why can a regular expression not match balanced parentheses, and what exactly does a context-free grammar add?
- Name a rule in a language you use that a context-free grammar cannot express, and say which phase enforces it.
- Bison reports no conflicts. What have you learned about your grammar, and what have you not?