Context-Free Grammars for Parsing

A context-free grammar is formally a 4-tuple $G = (V, \Sigma, R, S)$ where $V$ is a finite set of nonterminals (syntactic categories such as `Expr` or `Stmt`), $\Sigma$ is a finite set of terminals (the actual tokens produced by the scanner, disjoint from $V$), $R$ is a finite set of production rules, and $S \in V$ is the designated start symbol. Each production has the form

where $A \in V$ is a single nonterminal and $\alpha \in (V \cup \Sigma)^*$ is any string of terminals and nonterminals (possibly empty, written $\varepsilon$). The grammar is called context-free precisely because the left-hand side of every rule is a single, bare nonterminal — the rule "fires" regardless of what surrounds $A$. This contrasts with more general phrase-structure grammars where the left-hand side can be a whole string, and the rewrite is legal only in specific surrounding context. A derivation starts from a string containing only $S$ and repeatedly replaces some nonterminal $A$ occurring in the current string with the right-hand side of a production $A \rightarrow \alpha$, writing $\Rightarrow$ for one rewrite step and $\Rightarrow^*$ for zero or more steps. The language generated by $G$, written $L(G)$, is the set of all terminal-only strings reachable from $S$:

Two grammars are equivalent if they generate the same language, even though their rule sets and derivation structures may differ completely — a fact that matters enormously when a compiler writer rewrites a grammar to remove ambiguity or make it suitable for a particular parsing algorithm, without changing the language it describes. This full apparatus — derivations as sequences of rewrites and the trees they induce — is developed properly under Derivations and Parse Trees; here the focus is on the grammar as a static object: what it is, what it can express, and why that expressive power is exactly what parsing needs.

Building and reading a CFG is mechanical once the pieces are fixed. The workflow a compiler front end (or a student writing a grammar by hand) follows is: 1. Identify terminals — these are exactly the token classes your scanner already emits (`ID`, `NUM`, `PLUS`, `LPAREN`, ...), per Building Scanners with Finite Automata. 2. Identify nonterminals — one per syntactic category you want to name (`Expr`, `Term`, `Factor`, `Stmt`, `Block`). 3. Write productions for each nonterminal, describing every way an instance of that category can be built from smaller pieces or terminals. 4. Designate the start symbol — the nonterminal representing "a complete program" or "a complete expression," whichever the grammar is meant to check. 5. Verify informally (or later, formally via parsing) that every intended string is derivable and no unintended string is. A canonical running example — arithmetic expressions with `+`, ``, parentheses, and identifiers — illustrates the whole process: ``` Grammar for arithmetic expressions: Nonterminals V = { Expr, Term, Factor } Terminals Σ = { id, num, '+', '', '(', ')' } Start symbol S = Expr Productions R: Expr -> Expr '+' Term Expr -> Term Term -> Term '' Factor Term -> Factor Factor -> '(' Expr ')' Factor -> id Factor -> num ``` Reading this as a generator: starting from `Expr`, you may repeatedly rewrite any nonterminal in the current string using a matching production, until only terminals remain. The layering `Expr → Term → Factor` is not decorative — it encodes that `` binds tighter than `+`, because a `Term` (product) can never directly contain a top-level `+`, while an `Expr` (sum) can contain `Term`s that internally contain ``. The following pseudocode is a generator — it nondeterministically expands the start symbol and demonstrates precisely what "belongs to the language" means, mirroring how a parser will later be asked to invert this process: ``` function generate(grammar): frontier <- [ grammar.start ] // list of symbols, terminals+nonterminals while frontier contains a nonterminal: choose (nondeterministically) some nonterminal A at position i in frontier choose (nondeterministically) some production A -> alpha in grammar.rules[A] replace frontier[i] with the sequence of symbols alpha // alpha may be empty (epsilon production): removes A with nothing return frontier // now a string of terminals only, i.e. a sentence function inLanguage(grammar, w): // membership by exhaustive/backtracking search over derivations return exists a sequence of choices in generate(grammar) that yields exactly w ``` `generate` is intentionally nondeterministic and, taken literally, exponential or non-terminating — it is a specification* of $L(G)$, not an efficient recognizer. The entire enterprise of Top-Down Parsing (and its bottom-up counterparts) exists to replace this brute-force search with a deterministic or low-backtracking algorithm that decides `inLanguage` in linear or near-linear time for well-behaved grammars. The figure below shows the grammar as a small rewriting system: nonterminals as rule-boxes, productions as labeled arrows into alternative right-hand sides.

Expressive power, argued precisely. Every regular language is context-free (any finite automaton converts directly into a right-linear grammar with productions of the form $A \rightarrow a B$ or $A \rightarrow \varepsilon$), so CFGs are at least as powerful as regular expressions. The strict inclusion is what matters for parsing: the balanced-parenthesis language $L = \{a^n b^n \mid n \ge 0\}$ is context-free — generated by $S \rightarrow aSb \mid \varepsilon$ — but not regular. This is provable directly from the pumping lemma for regular languages: any regular language has a pumping length $p$ such that every string of length $\ge p$ can be split $xyz$ with $|xy|\le p$, $|y|\ge 1$, and $xy^iz \in L$ for all $i \ge 0$. Take $a^pb^p \in L$; any nonempty $y$ inside the first $p$ symbols consists only of $a$'s, so pumping $y$ (say $i=2$) produces more $a$'s than $b$'s, leaving the resulting string outside $L$. Since no valid split exists, $L$ is not regular. Because real programming-language syntax needs unboundedly nested brackets, blocks, and expressions — exactly this pattern — no scanner alone can check syntactic well-formedness; a CFG (and a parser for it) is structurally necessary, not a convenience.

Grammar size vs. language size. A CFG is a finite object — finitely many nonterminals and productions — yet it can generate an infinite language, because recursive productions (a nonterminal appearing, directly or indirectly, in its own right-hand side) allow unbounded reuse of the same finite rule set. This is the same compression idea behind regular expressions and DFAs, taken up a level of expressive power: a constant-size description implicitly encodes infinitely many strings.

Membership and ambiguity are properties of the grammar, checked algorithmically later. Determining whether $w \in L(G)$ for a general CFG (with $n = |w|$ tokens) is decidable in $O(n^3)$ time via the CYK or Earley algorithms — a fact whose algorithmic proof belongs to parsing proper, previewed here only to be honest that recognizing membership from the raw definition (`generate`/`inLanguage` above) is not by itself efficient. What belongs squarely at the grammar level is a subtler correctness notion: ambiguity. A grammar is ambiguous if some string $w \in L(G)$ has two distinct parse trees (equivalently, two distinct leftmost derivations). Ambiguity is undecidable in general — there is no algorithm that, given an arbitrary CFG, always correctly reports whether it is ambiguous — but for concrete grammars we can often exhibit two derivations directly, which is a fully rigorous proof that the grammar (not necessarily the language) is ambiguous, since some other equivalent unambiguous grammar may exist for the same language.

Tradeoffs. The expressive gain over regular languages is not free: CFG parsing is asymptotically more expensive ($O(n^3)$ worst case for arbitrary CFGs, versus $O(n)$ for regular languages via a DFA), and grammar design introduces failure modes — ambiguity, left recursion, unreachable or unproductive nonterminals — that regular expressions simply cannot exhibit. Restricting to well-behaved grammar subclasses (LL(1), LR(1)) recovers linear-time parsing, at the cost of grammar-writing discipline covered under Top-Down Parsing.

Trace the grammar above on the concrete token string `id + id * id` (already lexed — three `id` tokens and the operators), producing a leftmost derivation (always rewrite the leftmost nonterminal):

Every step rewrites exactly one nonterminal into the right-hand side of one production, and after 8 steps every symbol is a terminal, matching the input exactly — so `id + id id ∈ L(G)`, proved constructively by exhibiting the derivation. Notice how the grammar's structure, not just the string, encodes precedence: the `` ends up nested two levels deeper (inside `Term`) than the `+` (at `Expr` level), which is exactly why, when this derivation is later turned into a parse tree, multiplication groups tighter than addition without a single explicit "precedence number" anywhere in the grammar. Now contrast with a naively unified grammar that collapses `Expr`, `Term`, `Factor` into one nonterminal: ``` Expr -> Expr '+' Expr | Expr '' Expr | '(' Expr ')' | id | num ``` This generates the exact same language — every string derivable in the layered grammar is derivable here too, and vice versa — but for `id + id id` it admits two distinct leftmost derivations, one that groups as `id + (id id)` and one that groups as `(id + id) id`. Both are legitimate parse structures for the same token string under this grammar, which is precisely the definition of ambiguity: the layered three-nonterminal grammar was designed exactly to eliminate this by construction, using nonterminal layering as a substitute for explicit precedence declarations.

Every production compiler front end — GCC, Clang, `javac`, the Rust and Go compilers, V8's JavaScript parser — begins with a context-free grammar (explicit or embedded in hand-written parser code) that defines legal program syntax before any semantic analysis happens. Language specifications (the C standard, the Java Language Specification, ECMAScript) publish their syntax as BNF or EBNF grammars directly, making the CFG the literal, citable legal definition of "valid syntax" for the language. Parser-generator tools such as Yacc/Bison, ANTLR, and Menhir take a CFG as direct textual input and emit a working parser, meaning grammar design is not academic exercise but the actual engineering artifact compiler teams maintain and version. Beyond compilers, CFGs underlie configuration-file formats (JSON, YAML, TOML each have a published CFG), markup languages (HTML/XML's nesting structure), query languages (SQL grammars), and even parts of computational linguistics, where Chomsky's original motivation — modeling natural language syntax — persists in modern syntactic parsers used in NLP pipelines. Any system that must recognize nested structure rather than merely a flat pattern of tokens reaches for a CFG.

Ask the tutor: How do I mechanically eliminate left recursion from a grammar before writing a recursive-descent parser?