Context-free grammar

A context-free grammar is a 4-tuple (N, T, P, S) where N is a finite set of nonterminals, T is a finite set of terminals (disjoint from N), P is a finite set of production rules of the form A → α with A ∈ N and α ∈ (N ∪ T)*, and S ∈ N is the start symbol.¹ The language generated by a CFG is the set of all strings of terminals that can be derived from the start symbol by repeatedly replacing a nonterminal with the right-hand side of one of its productions. A classic example is the grammar for arithmetic expressions: E → E + T | T, T → T * F | F, F → ( E ) | id. CFGs are often expressed in Backus–Naur form (BNF), a notation widely used in programming language specifications.²

Context-free grammars are the standard formalism for defining the syntax of programming languages such as C, Java, and Python. Compilers use CFGs to drive parsers that construct parse trees from source code.² In natural language processing, CFGs model the syntactic structure of sentences, enabling parsing and generation.³ Beyond computing, CFGs describe RNA secondary structure in bioinformatics, where base-pairing rules resemble context-free productions. The formalism also underpins the design of markup languages like XML and the structure of data serialization formats.

Efficient parsing of context-free languages is achieved by algorithms such as LL (top-down) and LR (bottom-up) parsing, which operate in linear time for deterministic grammars.² The CYK algorithm, a dynamic programming method, parses any CFG in O(n³) time and is used for general parsing. Earley's parser also handles arbitrary CFGs in O(n³) time but performs better on many practical grammars. Every CFG corresponds to a nondeterministic pushdown automaton (PDA) that recognizes the same language, and vice versa, establishing a fundamental equivalence between grammars and automata.¹

Certain context-free languages are inherently ambiguous, meaning every grammar for them is ambiguous—a property that complicates deterministic parsing.⁴ The pumping lemma for context-free languages provides a necessary (but not sufficient) condition for a language to be context-free, and is used to prove that some languages, such as {aⁿbⁿcⁿ | n≥0}, are not context-free. Normal forms, such as Chomsky normal form and Greibach normal form, restrict the structure of productions without changing the generated language, aiding in proofs and algorithm design.¹ The equivalence problem for CFGs—whether two grammars generate the same language—is undecidable, highlighting the expressive power of the formalism.

Nonterminal

A symbol that can be replaced by a production rule; typically denoted by uppercase letters.

Terminal

A symbol that appears in the generated strings and cannot be replaced further.

Production rule

A rewrite rule of the form A → α, where A is a nonterminal and α is a string of terminals and/or nonterminals.

Start symbol

The designated nonterminal from which all derivations begin.

Derivation

A sequence of rule applications that transforms the start symbol into a string of terminals.

Parse tree

A tree representation of a derivation, showing the hierarchical structure of the string.