Elamur Research⌕
☰
home / concepts / Context-free grammar

🌲 Context-free grammar

Concept · 25 key papers · all concepts

A context-free grammar is a formal system of rewriting rules in which each rule replaces a single nonterminal symbol with a string of symbols, regardless of surrounding context. It defines a language as the set of terminal strings derivable from a designated start symbol.

Also: CFG, context-free phrase-structure grammar, Type-2 grammar, BNF grammar (in programming-language notation); probabilistic or stochastic variant: PCFG, SCFG

What it is

A context-free grammar (CFG) describes how strings are assembled from nested parts. It has two kinds of symbols:

Every rule rewrites one nonterminal, and the rule can apply wherever that nonterminal occurs. The neighbouring symbols play no role, which is what "context-free" means. In the Chomsky hierarchy, CFGs sit above regular grammars and below context-sensitive grammars. The languages they generate are exactly those recognised by pushdown automata.

Here is a small grammar for English fragments:

A derivation starts at S and repeatedly rewrites a nonterminal: S ⇒ NP VP ⇒ Det N VP ⇒ the N VP ⇒ the man VP ⇒ … ⇒ the man saw the dog.

The same derivation can be drawn as a parse tree:

Different rewriting orders, such as leftmost and rightmost, can correspond to one tree. The tree is therefore the real unit of structure.

A grammar is ambiguous if some string has more than one parse tree. With the rules above, "the man saw the dog with the telescope" has two trees:

Ambiguity is primarily a property of grammars. A language is called inherently ambiguous when every grammar for it is ambiguous.

The key idea

G = (N, Σ, R, S),   rules  A → α,   A ∈ N,  α ∈ (N ∪ Σ)*
P(T) = ∏ p(A → α)   over all rule uses in tree T

The symbols in the first line mean:

In a rule A → α, the left side A is one nonterminal, and α is any finite sequence of terminals and nonterminals. The star denotes all such sequences, including the empty one. The language L(G) is the set of strings over Σ alone that can be derived from S.

The second line covers probabilistic CFGs (PCFGs). Each rule gets a probability p, and the probabilities of all rules sharing a left side sum to one. The probability of a tree T is the product of the probabilities of the rules used to build it. A sentence's probability is the sum over all of its trees.

Context-freeness lets parsing decompose into independent subproblems over spans. Any CFG can be converted to a weakly equivalent grammar in Chomsky normal form (CNF). Weak equivalence means the language is kept but the trees generally are not. In CNF, each rule either rewrites a nonterminal as exactly two nonterminals (A → B C) or as a single terminal (A → a). The one exception is a possible rule letting S produce the empty string, allowed only if S occurs on no right-hand side.

On CNF grammars, the CYK algorithm fills a triangular chart. Cell (i, j) collects every nonterminal that can yield words i through j. It is filled by combining pairs of adjacent smaller cells under binary rules, which takes time cubic in sentence length. Two variants follow from changing what each cell stores:

The context-free assumption also has a probabilistic cost. A PCFG treats each subtree as independent of everything outside it once the subtree's root label is fixed. A node's label is the only channel between a subtree and its context, so the labeling scheme fixes the independence assumptions of a treebank-estimated PCFG. Plain treebank labels carry too little context (Johnson 1998).

History and founding papers

Noam Chomsky introduced phrase-structure grammars in 1956 and 1957 and formalised the hierarchy of grammar types (Types 0–3) in 1959. Around 1959–1960, Backus and Naur adopted an equivalent notation (BNF) to specify ALGOL. This made CFGs the standard tool for programming-language syntax.

Parsing algorithms followed:

The probabilistic line has three classic problems:

Both the Inside computation and Inside-Outside estimation go back to Baker (1979). Jelinek and Lafferty added a fourth problem: the probability that a sentence begins with a given prefix, which speech recognisers need for next-word prediction (Jelinek & Lafferty 1991). Their Left-to-Right Inside algorithm works on CNF grammars. It obtains left-corner quantities in closed form as Q_L = P_L[I − P_L]⁻¹. For a fixed grammar it runs in O(k³) for a k-word prefix, about twice the Inside algorithm's cost (Jelinek & Lafferty 1991). Stolcke's probabilistic Earley parser computes prefix probabilities incrementally, word by word, for grammars not in normal form (Stolcke 1995).

Theoretical work then settled when PCFGs are well-defined. Careless rule probabilities can leak mass to infinite derivations; a grammar that loses no mass is called tight (or consistent). Take A → AA | a and write p for P(A → AA). Finite trees then receive total mass min(1, 1/p − 1), so the grammar is tight only when p ≤ ½ (Chi & Geman 1998; Chi 1999).

Chi and Geman proved that relative-frequency estimates from parsed corpora are always tight. They also proved that EM iterates are tight when null and unit rules are absent (Chi & Geman 1998). Chi extended this result into a general weighting method. He also showed that a Gibbs model whose only features are rule counts defines the same distributions as a PCFG (Chi 1999).

How it is used today

In compilers and data formats, CFGs remain the specification language for syntax. They are usually restricted to deterministic subclasses such as LL(k), LR(k) and LALR, which can be parsed in linear time. Parsing expression grammars are a related but different formalism, and their relation to CFGs has been studied formally (Mascarenhas et al. 2013).

In natural-language processing, treebanks have long been read as large PCFGs. The baseline Penn Treebank grammar has 14,962 productions. Of these, 1,327 can never appear in a most-probable parse, because combinations of shorter rules always beat them on probability. Annotating each node with its parent's category improved the average of precision and recall by roughly 8% (Johnson 1998).

The BitPar parser copes with the massive ambiguity of such treebank grammars. It handled a grammar of 65,855 rules and 4,444 categories by storing the CYK chart as bit vectors (Schmid 2004). Lexicalised extensions motivated specialised algorithms for bilexical grammars (Eisner & Satta 1999).

Modern constituency parsers still output context-free trees, but neural networks now do the scoring. Chart-based span parsers with self-attentive encoders are decoded with a CYK variant. They reached 95.13 F1 on the WSJ test set with ELMo (Kitaev & Klein 2018), and 95.8 F1 with a BERT ensemble (Kitaev et al. 2019).

Transition-based alternatives give up dynamic programming for speed:

Sequence-labeling encodings reduce trees to one tag per word. The best of them average about 92 F1 over nine treebanks: the English Penn Treebank and eight SPMRL languages (Swedish, Polish, Korean, Hungarian, Hebrew, German, French and Basque) (Roca et al. 2026).

Large language models can be prompted to emit trees. In a zero-shot setting, prompts included error-annotated example parses, and extra agents checked each tree's validity and faithfulness. This approach reached 76.87 F1, reported as the best end-to-end unsupervised result. It is not comparable to the supervised scores above, and LLM output is often malformed (Bai et al. 2023).

Constituent trees also feed downstream tasks such as discourse parsing (Chen et al. 2015). The prefix probabilities of PCFGs support the surprisal theory of human sentence processing. That theory predicts garden-path effects and the extra difficulty of object relatives (Hale 2001). Synchronous CFGs extend the formalism to pairs of languages for machine translation. Unlike monolingual CFGs, their rules cannot always be binarized (Huang et al. 2009).

Open questions

Several limits and open problems remain:

Key papers

The works this page cites, the most cited first; citations as counted by OpenAlex plus the papers of this library that cite the work, read 2026-10-23.

More papers

Topics: 📐 Syntax & grammar formalisms · 🗂️ Treebanks

Shelves: 🗣️ Linguistics & languages

This page in Markdown → https://md.research.elamur.ai/free/en/concepts/context-free-grammar/