Context-Free Grammars

Consider the language of balanced parentheses: strings like `(())` and `()()` are valid. Strings like `)(` and `(()` are not. No finite automaton can recognize this language. Doing so would require counting unboundedly many nested parentheses. Proving Languages Nonregular shows exactly why counting defeats finite memory. Yet balanced parentheses, arithmetic expressions, and the nested structure of `if`-`then`-`else` blocks are everywhere in real software. We need a more expressive way to describe such languages precisely. Context-free grammars (CFGs) are that tool. A CFG describes a language by giving a small set of rewriting rules. These rules — productions — generate every string in the language by repeated substitution. This generative view differs from the recognizer view of automata. Instead of scanning an input and deciding accept or reject, a grammar builds strings from a start symbol outward. That shift in perspective turns out to be exactly what is needed. It captures nested, recursive structure. CFGs matter because they are the backbone of nearly every parser ever written. Programming language syntax, markup languages like HTML and JSON, and even natural-language syntax models are specified with context-free grammars or close variants. The theory here is not an academic curiosity. It is the mathematical foundation underneath every compiler front end. It underlies every configuration-file parser, and every "grammar" in a parser-generator tool like Yacc or ANTLR. This article gives the precise formal definition of a context-free grammar. That includes variables, terminals, productions, and the start symbol. It defines rigorously what language a grammar generates. It builds the vocabulary needed before tackling Derivations and Parse Trees. It also prepares for the normalization technique Chomsky Normal Form. Finally, it introduces the automaton model — the pushdown automaton. This automaton recognizes exactly the context-free languages.

Key takeaways

A context-free grammar (CFG) is a 4-tuple $(V, \Sigma, R, S)$ : variables, terminals, production rules, and a start symbol.
Productions have the form $A \to \alpha$ , where $A$ is a single variable and $\alpha$ is any string of variables and terminals — this "single variable on the left" restriction is what makes a grammar context-free.
The language generated by a grammar is the set of all terminal strings reachable from the start symbol via repeated rule applications (derivations).
CFGs can express nested and recursive structure — like balanced parentheses and arithmetic expressions — that no finite automaton or regular expression can.
Every regular language is context-free, but the reverse fails: context-free grammars are strictly more expressive than regular expressions.
The class of languages generated by CFGs is exactly the class recognized by pushdown automata, a fact proved via a direct grammar-to-automaton construction.

The core insight

A context-free grammar generates strings by rewriting one variable at a time, regardless of the surrounding context — and that single restriction is precisely what lets recursion, and hence nesting, be captured cleanly.

The idea

A context-free grammar is a formal system for generating strings through repeated substitution. Formally, it is a 4-tuple

G = (V, \Sigma, R, S)

where $V$ is a finite set of variables (also called nonterminals), $\Sigma$ is a finite set of terminals disjoint from $V$ , $R$ is a finite set of productions (or rules), and $S \in V$ is the designated start symbol. Each production has the form

A \to \alpha, \qquad A \in V,\ \alpha \in (V \cup \Sigma)^*

The left side of every production is a single variable, and the right side $\alpha$ can be any finite string built from variables and terminals — including the empty string $\varepsilon$ . This "one variable on the left" restriction is exactly what the word context-free refers to: a rule for rewriting $A$ may be applied wherever $A$ appears, irrespective of what surrounds it. (Contrast this with context-sensitive grammars, where the left side may include surrounding symbols that constrain when a rule fires.) Generation proceeds by derivation. Starting from the string consisting of just $S$ , at each step we pick some variable $A$ occurring in the current string, choose a production $A \to \alpha$ from $R$ , and replace that occurrence of $A$ with $\alpha$ . We write $u A v \Rightarrow u \alpha v$ for one such step, and $\Rightarrow^*$ for zero or more steps (the reflexive-transitive closure of $\Rightarrow$ ). A string $w \in \Sigma^*$ is derivable from $G$ if $S \Rightarrow^* w$ . The language generated by $G$ , written $L(G)$ , is the set of all such strings:

L(G) = \{\, w \in \Sigma^* \mid S \Rightarrow^* w \,\}

A language $L$ is context-free if there exists some CFG $G$ with $L(G) = L$ . Note carefully: $L(G)$ contains only strings entirely over $\Sigma$ (no leftover variables) — a derivation that stalls with variables still present has not produced a member of the language. Grammars are usually written compactly, listing productions with the same left-hand side on one line separated by `|` (read "or"). For example,

A \to 0A1 \mid B, \qquad B \to \# \mid \varepsilon

is shorthand for four productions: $A \to 0A1$ , $A \to B$ , $B \to \#$ , $B \to \varepsilon$ . This particular grammar generates $\{0^n \# 1^n : n \ge 0\} \cup \{0^n 1^n : n \ge 0\}$ — precisely the kind of matched-count language that defeats finite automata, because each application of $A \to 0A1$ adds one `0` on the left and its matching `1` on the right, and only $B$ 's rules can end the recursion.

How it works

Constructing a CFG for a target language is a design exercise: you must find variables that capture the recursive substructure of the language, and productions that build every valid string while excluding every invalid one. A useful mental discipline is to give each variable a language it stands for, then check that its productions are exactly the ways to build members of that sub-language from smaller pieces.

Example 1 — balanced parentheses. Let $\Sigma = \{(, )\}$ and define one variable $P$ standing for "a balanced string of parentheses." The grammar

P \to (P) \mid PP \mid \varepsilon

works because every balanced string is either empty, a balanced string wrapped in one more pair of parentheses, or the concatenation of two balanced strings. Those three cases are exhaustive and mutually exploitable via recursion.

Example 2 — arithmetic expressions. With terminals $\{+, \times, (, ), \mathtt{id}\}$ , a grammar reflecting operator precedence uses three tiers of variables:

E \to E + T \mid T \qquad T \to T \times F \mid F \qquad F \to (E) \mid \mathtt{id}

Here $E$ (expression) handles addition at the loosest binding, $T$ (term) handles multiplication, and $F$ (factor) handles atoms and parenthesization — a layered design that simultaneously encodes the language of valid expressions and their precedence structure, which is why compiler grammars are typically written this way. The following pseudocode gives an explicit, generic derivation procedure: given a grammar and a target string, it performs a bounded, systematic search for a derivation (this is the naive membership-testing idea that motivates smarter parsing algorithms such as CYK, covered alongside Chomsky Normal Form). ``` function DERIVES(G = (V, Σ, R, S), target w, maxSteps):

# Breadth-first search over sentential forms (strings over V ∪ Σ) frontier ← { S } # a set of sentential forms, start with just S visited ← { S } for step in 1 .. maxSteps: nextFrontier ← ∅ for each sentential form α in frontier: if α == w: return TRUE # found a derivation S ⇒ w if α has no variables and α != w: continue # dead end: fully terminal but wrong if length(α) > length(w): continue # prune: can only grow via non-erasing rules for each position i where α[i] is a variable A: for each production (A → β) in R: α' ← α with α[i] replaced by β if α' not in visited: add α' to visited add α' to nextFrontier frontier ← nextFrontier if frontier is empty: return FALSE return FALSE # exceeded maxSteps without finding w (only a heuristic bound) ``` The pruning step `length(α) > length(w)` is valid only when every production is non-shrinking (no rule with $|\beta| < |A| = 1$ , i.e. no $\varepsilon$ -productions); grammars with $\varepsilon$ -productions need a variant that also prunes on other grounds (e.g. removing $\varepsilon$ -productions from $G$ first via a standard transformation) — this is one reason real parsers convert grammars to a normal form before parsing. This brute-force search is presented for conceptual completeness — it illustrates precisely what "derivation" means as a search process — but it is not how real parsers work; it can loop or blow up on ambiguous or highly recursive grammars. Efficient parsing (CYK, Earley, LL, LR) restricts either the grammar shape or the search strategy to guarantee polynomial time, and is developed once Chomsky Normal Form and pushdown automata are on the table.

Figure

A context-free grammar as a rewriting system: derivation tree for the grammar E → E+T | T, T → T×F | F, F → (E) | id, deriving "id + id × id"

Complexity & correctness

Membership testing (worst case, general CFGs). The classic algorithm for deciding whether $w \in L(G)$ is the CYK algorithm, which requires the grammar first be converted to Chomsky Normal Form (every rule of the shape $A \to BC$ or $A \to a$ ). CYK runs in

O(n^3 \cdot |G|)

time and $O(n^2)$ space, where $n = |w|$ and $|G|$ is the size of the grammar (number of productions), by dynamic programming over substrings — this bound, and its derivation, belongs properly to the CYK/Chomsky Normal Form discussion, but it is worth previewing here: context-freeness buys polynomial-time parsing, in contrast to the undecidability that looms for more powerful grammar classes.

Space for grammar representation. A CFG with $|V|$ variables and $|R|$ productions, each of bounded length $\ell$ , is described in $O(|R| \cdot \ell)$ space — grammars are typically tiny (tens of rules) even when the languages they generate are infinite, which is the entire point of a generative, finite description of an infinite set.

Correctness of " $L(G)$ is well-defined." The relation $\Rightarrow$ is defined on sentential forms (strings in $(V \cup \Sigma)^*$ ); $\Rightarrow^*$ is its reflexive-transitive closure, a standard closure operation, so $L(G) = \{ w \in \Sigma^* : S \Rightarrow^* w\}$ is a well-defined set for every grammar $G$ — no ambiguity in what a grammar "means" as a language, even though (as the pitfalls section shows) a string can have more than one derivation.

Correctness of a specific grammar (proof technique). To prove a grammar $G$ generates exactly a target language $L$ , show both inclusions: 1. $L(G) \subseteq L$ (soundness). Prove by induction on the number of derivation steps that every string derivable from any variable satisfies the invariant intended for that variable (e.g., "every string derivable from $P$ is balanced"). The base case covers productions with only terminals/ $\varepsilon$ on the right; the inductive step covers productions that introduce recursive variables, using the inductive hypothesis on the shorter sub-derivations of those variables. 2. $L \subseteq L(G)$ (completeness). Prove by induction on the structure of an arbitrary string in $L$ (e.g., on parenthesis nesting depth, or on string length) that it can be built by some production, reducing to strings that are shorter/simpler and hence covered by the inductive hypothesis. For the balanced-parentheses grammar $P \to (P) \mid PP \mid \varepsilon$ : soundness follows because $\varepsilon$ is balanced, wrapping a balanced string in parentheses preserves balance, and concatenating two balanced strings is balanced. Completeness follows because any nonempty balanced string either has matching outer parentheses around a balanced substring ( $(P)$ case) or splits at its first point of "returning to depth zero" into two nonempty balanced pieces ( $PP$ case) — an argument entirely mirrored by the recursive definition itself, which is exactly why the grammar is correct.

Expressive tradeoff. Context-freeness is a genuine restriction: languages like $\{a^n b^n c^n : n \ge 0\}$ (three matched counts, not two) are not context-free, provable via the pumping lemma for context-free languages — a cousin of the technique from Proving Languages Nonregular, but with pumping applied to two separated locations in a parse tree rather than one contiguous substring. So CFGs sit in a strict expressiveness band: strictly more powerful than regular languages, strictly less powerful than context-sensitive or unrestricted (Turing-recognizable) grammars.

Worked example

Trace a full derivation of the string `id + id × id` using the arithmetic grammar

E \to E + T \mid T, \qquad T \to T \times F \mid F, \qquad F \to (E) \mid \mathtt{id}

using leftmost derivation (always rewrite the leftmost remaining variable — a standard canonical choice that removes spurious ordering ambiguity when tracing steps).

Step	Sentential form	Rule applied
0	$E$	— (start)
1	$E + T$	$E \to E + T$
2	$T + T$	$E \to T$
3	$F + T$	$T \to F$
4	$\mathtt{id} + T$	$F \to \mathtt{id}$
5	$\mathtt{id} + T \times F$	$T \to T \times F$
6	$\mathtt{id} + F \times F$	$T \to F$
7	$\mathtt{id} + \mathtt{id} \times F$	$F \to \mathtt{id}$
8	$\mathtt{id} + \mathtt{id} \times \mathtt{id}$	$F \to \mathtt{id}$

Reading off step 8: the fully terminal string is `id + id × id`, matching the target, so $E \Rightarrow^* \texttt{id + id \times id}$ , confirming membership in $L(G)$ . Notice the structural payoff: because $T \times F$ nests below $E + T$ in the derivation, the parse tree (shown in the figure above) groups the multiplication tighter than the addition — the grammar has encoded operator precedence purely through its layered variables, with no extra "priority" mechanism needed.

A second, contrasting trace — showing failure. Attempt to derive the malformed string `id +` (a dangling operator) from the same grammar. Any derivation must eventually replace every variable with terminals; in particular the rightmost symbol of any string generated via $E \to E + T$ must eventually expand $T$ into a nonempty terminal string, because every production for $T$ and its descendants ( $T \to T \times F \mid F$ , $F \to (E) \mid \mathtt{id}$ ) produces at least one terminal symbol before halting — no production ever erases a variable to $\varepsilon$ in this grammar. Hence no derivation can end with a dangling `+`, and `id +` $\notin L(G)$ , exactly matching the informal expectation that a plus sign always needs a right operand.

Common pitfalls & traps

Pitfall	Why it happens	Fix
Confusing "generates" with "recognizes"	Beginners think of a grammar as scanning input like an automaton	Remember a grammar builds strings top-down from $S$ ; recognition (parsing) is a separate, derived problem
Forgetting $L(G)$ excludes sentential forms with leftover variables	A derivation that "gets stuck" with a variable present looks like progress	Only fully-terminal strings ( $\Sigma^*$ ) count as members of $L(G)$
Assuming every string has a unique derivation	Confusing derivation order (leftmost vs. rightmost vs. arbitrary) with genuine structural ambiguity	Distinguish order-ambiguity (harmless, resolved by leftmost-derivation convention) from true ambiguity (two different parse trees for the same string)
Writing left-recursive rules without checking termination	$A \to A\alpha$ style rules can be correct but easy to reason about wrong	Trace small derivations by hand; verify a base case (non-recursive alternative) exists and is reachable
Treating CFGs as closed under intersection and complement	Regular languages have those closures, so people assume CFGs do too	Context-free languages are closed under union, concatenation, and Kleene star, but not in general under intersection or complement
Ignoring $\varepsilon$ -productions when reasoning about string length	$A \to \varepsilon$ silently shrinks a sentential form, breaking naive length-based pruning	Handle $\varepsilon$ -productions explicitly, or eliminate them first via a standard transformation before length-based arguments

Common trapThe silent trap of ambiguous grammars

A grammar can generate exactly the right language while still being dangerously ambiguous — meaning some string has two distinct parse trees. The classic culprit is the "dangling-else" grammar `S → if E then S | if E then S else S | other`, where `if E1 then if E2 then S1 else S2` parses two different ways depending on which `if` the `else` attaches to. Ambiguity is not a syntax error; the grammar is perfectly well-formed and $L(G)$ is well-defined. The danger is semantic: a compiler or interpreter built on an ambiguous grammar may silently pick the wrong parse tree, changing program meaning. Some inherently ambiguous languages have no unambiguous grammar at all, so this is a property of the language, not a fixable bug in one grammar — a fact that must be checked for, not assumed away, before treating a grammar as ready for use in a real parser.

Pioneers & history

The formal apparatus of context-free grammars grew from two independent traditions arriving at essentially the same object: rewriting-rule generative systems in theoretical linguistics, and BNF-style syntax specification in early programming-language design.

Origins · 1 minNoam Chomsky and how this was discovered

Noam Chomsky

born 1928 · Developed the generative-grammar hierarchy in the mid-1950s, classifying grammars by the shape of their production rules — the "context-free" level sits between regular and context-sensitive grammars in what became known as the Chomsky hierarchy

John Backus

1924–2007 · Co-designed FORTRAN and, working with Peter Naur, devised Backus-Naur Form (BNF) to specify ALGOL 60's syntax — a notation for production rules essentially equivalent to context-free grammars, now the near-universal notation for programming-language syntax

History

1956

— Noam Chomsky publishes a hierarchy of grammar types, introducing the class later called context-free.

1959–1963

— John Backus and Peter Naur develop and refine BNF to specify the syntax of ALGOL 60, popularizing production-rule notation in computing.

1961

— Independent work by Robert Floyd and others formalizes parsing algorithms driven directly by context-free grammars.

1965

— Donald Knuth introduces LR parsing, giving a general, efficient parsing method for a large practical subclass of context-free grammars.

1968

— Cocke, Younger, and Kasami's dynamic-programming parsing algorithm (CYK) establishes polynomial-time parsing for all context-free grammars via Chomsky Normal Form.

Where this matters

Context-free grammars are the specification language for essentially every parser in production software. Compiler front ends for languages like C, Python, and Java are built from CFGs processed by parser generators such as Yacc, Bison, and ANTLR, which convert a grammar directly into working parsing code. Data formats — JSON, XML, YAML, and even most configuration-file syntaxes — are defined with grammars, and the parsing libraries that read them implement context-free (or near-context-free) recognition algorithms under the hood. Beyond compilers, CFGs underlie network protocol parsers (where malformed input handling is a security-critical concern), template engines, regular-expression-engine syntax itself (regex syntax is context-free even though the matched language may be regular), and computational linguistics, where probabilistic context-free grammars model natural-language syntax for parsing and machine translation pipelines. The theoretical guarantee that context-free membership testing is solvable in polynomial time — a fact whose machinery is built out in Chomsky Normal Form and realized operationally by Pushdown Automata — is precisely why "write a grammar, generate a parser" is a reliable engineering workflow rather than a computationally risky gamble. Understanding Derivations and Parse Trees is the natural next step, since it makes precise how a grammar's abstract generative process turns into the concrete tree structure that every real parser actually builds.

Ask the tutor: How does converting a context-free grammar to Chomsky Normal Form actually work, and why does it preserve the generated language exactly?

Is every regular language also context-free?

Yes. Any regular language can be generated by a CFG whose productions mirror the transitions of a finite automaton or the structure of a regular expression: for each state $q$ with a transition to state $r$ on symbol $a$ , add a production $Q \to aR$ (where $Q, R$ are variables corresponding to states), and mark accepting states with $Q \to \varepsilon$ . This "right-linear grammar" construction shows regular languages sit strictly inside context-free languages. The containment is strict because languages like $\{0^n1^n\}$ are context-free but demonstrably not regular, as shown via the pumping lemma for regular languages.

What's the difference between a sentential form and a string in the language?

A sentential form is any string reachable from the start symbol during a derivation — it may still contain variables. A string in $L(G)$ must be a sentential form consisting only of terminals, with $S \Rightarrow^* w$ for that all-terminal $w$ . Intermediate sentential forms like $E + T$ or $T \times F$ in the worked derivation are not themselves members of the language; they are waypoints. This distinction matters because algorithms reasoning about derivations, like the CYK algorithm, explicitly track terminal-only substrings as the base case of their recursion.

Can every context-free language be generated by an unambiguous grammar?

No — some context-free languages are inherently ambiguous, meaning every grammar generating them has at least one string with multiple parse trees. A classical example combines two overlapping matched-count patterns, such as the union of $\{a^ib^jc^k : i=j\}$ and $\{a^ib^jc^k : j=k\}$ , whose overlap region ( $i=j=k$ ) forces any generating grammar to derive some strings two structurally different ways. This is a property of the language itself, not a fixable flaw in a particular grammar, and it has real consequences for programming-language design, since language designers deliberately avoid inherently ambiguous constructs.

How is a CFG different from a regular expression?

A regular expression describes a language using concatenation, union, and Kleene star applied to symbols, with no mechanism for matching nested structure across arbitrary distances. A CFG allows recursive variables that can reference themselves, enabling constructs like $A \to (A)$ that pair up symbols no matter how deeply nested. Every regular expression can be converted to an equivalent (non-recursive-in-a-certain-sense) CFG, but the reverse fails: grammars with genuine self-embedding recursion, such as $A \to (A) \mid \varepsilon$ , generate languages no regular expression can match.

Do CFGs always terminate when generating a string?

Any single derivation step is trivial and always terminates, but a derivation sequence only "finishes" when every variable has been rewritten away, leaving a pure terminal string — and nothing forces this to happen quickly, or ever, along an arbitrary sequence of choices. Rules like $A \to \varepsilon$ or $A \to a$ are essential "escape hatches" that let a derivation stop expanding. A grammar with no such escape hatch reachable from some variable can derive infinite sentential forms without ever producing a terminal string from that variable, effectively contributing nothing usable to $L(G)$ .

Why do grammars for arithmetic expressions use three variables (E, T, F) instead of one?

Layering variables by precedence level encodes operator precedence directly into the grammar's structure without any extra bookkeeping. A single flat rule like $E \to E + E \mid E \times E \mid \mathtt{id}$ generates the right language but is ambiguous — `id + id × id` would have two structurally different parse trees, one where `+` binds tighter and one where `×` does. Splitting into $E$ (sums), $T$ (products), $F$ (atoms) forces multiplication to always nest below addition in any parse tree, resolving the ambiguity and matching the intended arithmetic semantics.

How does grammar size relate to the complexity of parsing algorithms?

Grammar size (number of productions, $|R|$ ) enters parsing time linearly or with a small polynomial factor, separate from the input length $n$ . The CYK algorithm's $O(n^3|G|)$ bound, for instance, is cubic in the string length but only linear in the number of grammar rules (after Chomsky Normal Form conversion, where each rule contributes a bounded amount of work per substring pair). In practice grammars for real programming languages have on the order of dozens to a few hundred productions, so the $n^3$ term dominates for anything but the shortest inputs — one reason production parsers use restricted grammar classes (LL, LR) achieving linear time instead of general CYK.