Grammars & Parsing
Add a stack to a state machine and you can handle nesting — which is exactly what every programming language needs.
Context-Free Grammars
A context-free grammar (CFG) is a set of production rules that generate strings by replacing symbols. Non-terminals (variables) expand into other symbols; terminals are the actual characters. CFGs capture nesting — the thing regex can’t — which is why every programming language’s syntax is a CFG.
S → ( S ) S
S → ε
# derivation of "(())":
S → (S)S → ((S)S)S → (())
That rule S → (S)S is self-referential — S contains S — which is how a finite set of rules generates infinitely deep nesting. No finite automaton can do this; the recursion is the whole point.
Pushdown Automata — CFG + a Stack
The machine that recognizes context-free languages is a pushdown automaton (PDA): a finite automaton plus a stack. The stack is the unbounded memory that lets it count. For aⁿbⁿ: push on each a, pop on each b, accept if the stack empties exactly as input ends.
aⁿbⁿcⁿ needs to count two things at once and is not context-free. That takes a Turing machine — two guides on.Parsing — From Text to Tree
Parsing is running a grammar in reverse: given a string, find the derivation (the parse tree) that produces it. This is the front-end of every compiler and interpreter. 2 + 3 * 4 parses into a tree where * sits below + — that structure is how precedence gets enforced.
| Stage | Turns | Into |
|---|---|---|
| Lexer | Characters | Tokens (2, +, 3) — a regular language job |
| Parser | Tokens | Parse tree / AST — a context-free job |
| Rest of compiler | AST | Types, IR, machine code |
Note the layering: the lexer is regular (regex-level), the parser is context-free (grammar-level). Each stage uses exactly the weakest machine that suffices — a recurring engineering principle.
Ambiguity — the Grammar Bug
A grammar is ambiguous if one string has two different parse trees. The classic “dangling else” (if a if b … else … — whose if owns the else?) is ambiguity, and it’s a real language-design bug: it means the meaning isn’t determined by the syntax. Real grammars are carefully written (precedence, associativity rules) to be unambiguous.
Interview Questions
What can a context-free grammar express that a regex cannot?
Nesting / balanced recursion — matched parentheses, nested blocks, the structure of programming languages. The self-referential rules generate unbounded depth that a finite automaton can’t track.
What machine recognizes context-free languages?
A pushdown automaton: a finite automaton plus a stack. The stack is the unbounded memory that lets it match nested/counted structure like aⁿbⁿ.
Why is lexing regular but parsing context-free?
Tokens (identifiers, numbers, operators) have no nesting — a regular language, matched by regex. Program structure (nested expressions, blocks) does nest — context-free, needing a grammar and a stack. Each stage uses the weakest sufficient model.
What is an ambiguous grammar and why does it matter?
One where a string has more than one parse tree, so its meaning isn’t uniquely determined by syntax (the dangling-else problem). Language designers rewrite grammars with precedence/associativity to remove ambiguity.