---
title: "Context-free grammar — definition and key papers"
description: "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…"
canonical: "https://research.elamur.ai/free/en/concepts/context-free-grammar/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/concepts/context-free-grammar/)

[home](https://md.research.elamur.ai/free/en/) / [concepts](https://md.research.elamur.ai/free/en/concepts/) / Context-free grammar

# 🌲 Context-free grammar

Concept · 25 key papers · [all concepts](https://md.research.elamur.ai/free/en/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:

- Nonterminals stand for categories such as "noun phrase".
- Terminals are the actual words or characters.

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:

- S → NP VP
- NP → Det N | NP PP
- VP → V NP | VP PP
- PP → P NP
- Det → the; N → man | dog | telescope; V → saw; P → with

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:

- The root is S.
- Each internal node is a nonterminal whose children are the right-hand side of the rule applied.
- The leaves, read left to right, form the sentence (its yield).

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:

- In one, the PP attaches to the VP (the seeing used a telescope).
- In the other, it attaches to the NP (the dog had the telescope).

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:

- N is a finite set of nonterminals.
- Σ is a finite set of terminals, disjoint from N.
- R is a finite set of rules.
- S ∈ N is the start symbol.

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:

- Storing "summed probability" instead of "which nonterminals" gives the Inside algorithm.
- Storing "best probability" gives Viterbi parsing.

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](https://md.research.elamur.ai/free/en/papers/johnson-1998-pcfg-models-linguistic-tree-representations/)).

## 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:

- Kasami (1965), Younger (1967) and Cocke, working largely independently (Cocke's version appeared with Schwartz in 1970), gave the cubic chart recognition algorithm now called CYK.
- Earley (1970) gave a general parser that needs no normal form.
- Valiant (1975) tied CFG recognition to Boolean matrix multiplication.
- Lee later showed the link runs in both directions: any substantially faster CFG parser would yield fast Boolean matrix multiplication ([Lee 2001](https://md.research.elamur.ai/free/en/papers/lee-2001-fast-context-free-grammar-parsing/)).

The probabilistic line has three classic problems:

- string probability via the Inside algorithm;
- the best parse via Viterbi;
- rule estimation via Inside-Outside.

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](https://md.research.elamur.ai/free/en/papers/jelinek-1991-computation-probability-initial-substring-generation/)). 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](https://md.research.elamur.ai/free/en/papers/jelinek-1991-computation-probability-initial-substring-generation/)). Stolcke's probabilistic Earley parser computes prefix probabilities incrementally, word by word, for grammars not in normal form ([Stolcke 1995](https://md.research.elamur.ai/free/en/papers/stolcke-1995-efficient-probabilistic-context-free-parsing/)).

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](https://md.research.elamur.ai/free/en/papers/chi-1998-estimation-probabilistic-context-free-grammars/); [Chi 1999](https://md.research.elamur.ai/free/en/papers/chi-1999-statistical-properties-probabilistic-context-free/)).

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](https://md.research.elamur.ai/free/en/papers/chi-1998-estimation-probabilistic-context-free-grammars/)). 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](https://md.research.elamur.ai/free/en/papers/chi-1999-statistical-properties-probabilistic-context-free/)).

## 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](https://md.research.elamur.ai/free/en/papers/mascarenhas-2013-relation-between-context-free-grammars/)).

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](https://md.research.elamur.ai/free/en/papers/johnson-1998-pcfg-models-linguistic-tree-representations/)).

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](https://md.research.elamur.ai/free/en/papers/schmid-2004-efficient-parsing-highly-ambiguous-context/)). Lexicalised extensions motivated specialised algorithms for bilexical grammars ([Eisner & Satta 1999](https://md.research.elamur.ai/free/en/papers/eisner-1999-efficient-parsing-bilexical-context-free/)).

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](https://md.research.elamur.ai/free/en/papers/kitaev-2018-constituency-parsing-self-attentive-encoder/)), and 95.8 F1 with a BERT ensemble ([Kitaev et al. 2019](https://md.research.elamur.ai/free/en/papers/kitaev-2019-multilingual-constituency-parsing-self-attention/)).

Transition-based alternatives give up dynamic programming for speed:

- One shift-reduce parser reached 91.3% F-score on English ([Zhu et al. 2013](https://md.research.elamur.ai/free/en/papers/zhu-2013-fast-accurate-shift-reduce-constituent/)).
- A span-based transition system needs exactly 4n−2 steps for an n-word sentence and scored 91.3 F1 on WSJ section 23 ([Cross & Huang 2016](https://md.research.elamur.ai/free/en/papers/cross-2016-span-based-constituency-parsing-structure/)).
- An in-order traversal system scored 91.8 F1 greedily on WSJ ([Liu & Zhang 2017](https://md.research.elamur.ai/free/en/papers/liu-2017-order-transition-based-constituent-parsing/)).

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](https://md.research.elamur.ai/free/en/papers/roca-2026-sequence-labeling-constituent-parsing-comparative/)).

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](https://md.research.elamur.ai/free/en/papers/bai-2023-constituency-parsing-using-llms/)).

Constituent trees also feed downstream tasks such as discourse parsing ([Chen et al. 2015](https://md.research.elamur.ai/free/en/papers/chen-2015-shallow-discourse-parsing-constituent-parsing/)). 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](https://md.research.elamur.ai/free/en/papers/hale-2001-probabilistic-earley-parser-as-psycholinguistic/)). 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](https://md.research.elamur.ai/free/en/papers/huang-2009-binarization-synchronous-context-free-grammars/)).

## Open questions

Several limits and open problems remain:

- **Expressive adequacy for natural language.** Cross-serial dependencies in Swiss German (Shieber 1985) show that some human languages are not context-free. Mildly context-sensitive formalisms such as TAG and CCG were developed to cover such patterns. Discontinuous constituents also strain context-free trees ([Coavoux 2020](https://md.research.elamur.ai/free/en/papers/coavoux-2020-qu-apporte-bert-l-analyse/)). Richer frameworks such as HPSG add feature structures on top of phrase structure ([Müller et al. 2021](https://md.research.elamur.ai/free/en/papers/muller-2021-hpsg-handbook/)).
- **Unsupervised learning.** Inducing a grammar from raw text remains hard. Active approaches include depth-bounded PCFGs inspired by memory limits ([Jin et al. 2018](https://md.research.elamur.ai/free/en/papers/jin-2018-unsupervised-grammar-induction-depth-bounded/)) and compound PCFGs with neural parameterisations ([Kim et al. 2019](https://md.research.elamur.ai/free/en/papers/kim-2019-compound-probabilistic-context-free-grammars/)).
- **Parsing complexity.** Valiant's reduction already gives subcubic recognition in theory. Because fast CFG parsing would also yield fast Boolean matrix multiplication, practical subcubic parsing would require practical fast Boolean matrix multiplication ([Lee 2001](https://md.research.elamur.ai/free/en/papers/lee-2001-fast-context-free-grammar-parsing/)). Prefix-probability methods also struggle when very many nonterminals make the matrix inversion costly ([Jelinek & Lafferty 1991](https://md.research.elamur.ai/free/en/papers/jelinek-1991-computation-probability-initial-substring-generation/)).
- **Neural networks and the hierarchy.** It is unclear whether, and how, neural architectures generalise on context-free languages. This question is being probed with tasks organised by the Chomsky hierarchy ([Delétang et al. 2022](https://md.research.elamur.ai/free/en/papers/deletang-2022-neural-networks-chomsky-hierarchy/); [Someya et al. 2024](https://md.research.elamur.ai/free/en/papers/someya-2024-targeted-syntactic-evaluation-chomsky-hierarchy/)).

## 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.

- [A Probabilistic Earley Parser as a Psycholinguistic Model](https://md.research.elamur.ai/free/en/papers/hale-2001-probabilistic-earley-parser-as-psycholinguistic/) — John Hale · 2001 · 1,448 citations
- [Constituency Parsing with a Self-Attentive Encoder](https://md.research.elamur.ai/free/en/papers/kitaev-2018-constituency-parsing-self-attentive-encoder/) — Nikita Kitaev, Dan Klein · 2018 · 759 citations
- [PCFG Models of Linguistic Tree Representations](https://md.research.elamur.ai/free/en/papers/johnson-1998-pcfg-models-linguistic-tree-representations/) — Mark Johnson · 1998 · 488 citations
- [Multilingual Constituency Parsing with Self-Attention and Pre-Training](https://md.research.elamur.ai/free/en/papers/kitaev-2019-multilingual-constituency-parsing-self-attention/) — Nikita Kitaev, Steven Cao, Dan Klein · 2019 · 356 citations
- [Fast and Accurate Shift-Reduce Constituent Parsing](https://md.research.elamur.ai/free/en/papers/zhu-2013-fast-accurate-shift-reduce-constituent/) — Muhua Zhu, Yue Zhang, Wenliang Chen et al. · 2013 · 247 citations
- [Efficient Parsing of Highly Ambiguous Context-Free Grammars with Bit Vectors](https://md.research.elamur.ai/free/en/papers/schmid-2004-efficient-parsing-highly-ambiguous-context/) — Helmut Schmid · 2004 · 209 citations
- [Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles](https://md.research.elamur.ai/free/en/papers/cross-2016-span-based-constituency-parsing-structure/) — James Cross, Liang Huang · 2016 · 191 citations
- [Computation of the Probability of Initial Substring Generation by Stochastic Context-Free Grammars](https://md.research.elamur.ai/free/en/papers/jelinek-1991-computation-probability-initial-substring-generation/) — Frederick Jelinek, John D. Lafferty · 1991 · 150 citations
- [Statistical Properties of Probabilistic Context-Free Grammars](https://md.research.elamur.ai/free/en/papers/chi-1999-statistical-properties-probabilistic-context-free/) — Zhiyi Chi · 1999 · 145 citations
- [In-Order Transition-based Constituent Parsing](https://md.research.elamur.ai/free/en/papers/liu-2017-order-transition-based-constituent-parsing/) — Jiangming Liu, Yue Zhang · 2017 · 98 citations
- [Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars](https://md.research.elamur.ai/free/en/papers/eisner-1999-efficient-parsing-bilexical-context-free/) — Jason Eisner, Giorgio Satta · 1999 · 90 citations
- [Binarization of Synchronous Context-Free Grammars](https://md.research.elamur.ai/free/en/papers/huang-2009-binarization-synchronous-context-free-grammars/) — Liang Huang, Hao Zhang, Daniel Gildea et al. · 2009 · 84 citations
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://md.research.elamur.ai/free/en/papers/kim-2019-compound-probabilistic-context-free-grammars/) — Yoon Kim, Chris Dyer, Alexander Rush · 2019 · 79 citations
- [An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities](https://md.research.elamur.ai/free/en/papers/stolcke-1995-efficient-probabilistic-context-free-parsing/) — Andreas Stolcke · 1995 · 70 citations
- [Neural Networks and the Chomsky Hierarchy](https://md.research.elamur.ai/free/en/papers/deletang-2022-neural-networks-chomsky-hierarchy/) — Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya et al. · 2022 · 66 citations
- [Unsupervised Grammar Induction with Depth-bounded PCFG](https://md.research.elamur.ai/free/en/papers/jin-2018-unsupervised-grammar-induction-depth-bounded/) — Lifeng Jin, Finale Doshi-Velez, Timothy Miller et al. · 2018 · 55 citations
- [Head-Driven Phrase Structure Grammar: The handbook](https://md.research.elamur.ai/free/en/papers/muller-2021-hpsg-handbook/) — Stefan Müller, Anne Abeillé, Robert D. Borsley et al. · 2021 · 30 citations
- [Estimation of Probabilistic Context-Free Grammars](https://md.research.elamur.ai/free/en/papers/chi-1998-estimation-probabilistic-context-free-grammars/) — Zhiyi Chi, Stuart Geman · 1998 · 18 citations
- [Shallow Discourse Parsing Using Constituent Parsing Tree](https://md.research.elamur.ai/free/en/papers/chen-2015-shallow-discourse-parsing-constituent-parsing/) — Changge Chen, Peilu Wang, Hai Zhao · 2015 · 15 citations
- [Constituency Parsing using LLMs](https://md.research.elamur.ai/free/en/papers/bai-2023-constituency-parsing-using-llms/) — Xuefeng Bai, Jialong Wu, Yulong Chen et al. · 2023 · 14 citations
- [Targeted Syntactic Evaluation on the Chomsky Hierarchy](https://md.research.elamur.ai/free/en/papers/someya-2024-targeted-syntactic-evaluation-chomsky-hierarchy/) — Taiga Someya, Ryo Yoshida, Yohei Oseki · 2024 · 10 citations
- [Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication](https://md.research.elamur.ai/free/en/papers/lee-2001-fast-context-free-grammar-parsing/) — Lillian Lee · 2001 · 7 citations
- [On the Relation between Context-Free Grammars and Parsing Expression Grammars](https://md.research.elamur.ai/free/en/papers/mascarenhas-2013-relation-between-context-free-grammars/) — Fabio Mascarenhas, Sérgio Medeiros, Roberto Ierusalimschy · 2013 · 2 citations
- [Sequence Labeling for Constituent Parsing: A Comparative Study and Encoding Innovations](https://md.research.elamur.ai/free/en/papers/roca-2026-sequence-labeling-constituent-parsing-comparative/) — Diego Roca, David Vilares, Carlos Gómez-Rodríguez · 2026
- [Qu'apporte BERT à l'analyse syntaxique en constituants discontinus ? Une suite de tests pour évaluer les prédictions de structures syntaxiques discontinues en anglais (What does BERT contribute to discontinuous constituency parsing ? A test suite to evaluate discontinuous constituency structure predictions in English)](https://md.research.elamur.ai/free/en/papers/coavoux-2020-qu-apporte-bert-l-analyse/) — Maximin Coavoux · 2020

## Related concepts

- [Dependency parsing](https://md.research.elamur.ai/free/en/concepts/dependency-parsing/) — Dependency parsing is the task of recovering a sentence's syntactic structure as directed, labelled links between its words. Each word is…
- [Construction grammar](https://md.research.elamur.ai/free/en/concepts/construction-grammar/) — Construction grammar is a family of linguistic theories holding that knowledge of a language consists of constructions. Constructions are…
- [Semantic parsing](https://md.research.elamur.ai/free/en/concepts/semantic-parsing/) — Semantic parsing is the task of mapping a natural-language utterance to a formal, machine-interpretable representation of its meaning, such…
- [Universal Dependencies](https://md.research.elamur.ai/free/en/concepts/universal-dependencies/) — Universal Dependencies is a framework and an open collection of treebanks that annotates the grammar of many languages with one shared…

## More papers

Topics: [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/) · [🗂️ Treebanks](https://md.research.elamur.ai/free/en/topics/treebanks/)

Shelves: [🗣️ Linguistics & languages](https://md.research.elamur.ai/free/en/shelves/linguistics/)

- [← previous concept Construction grammar](https://md.research.elamur.ai/free/en/concepts/construction-grammar/)
- [next concept → Coreference resolution](https://md.research.elamur.ai/free/en/concepts/coreference-resolution/)
- [↑ back to concepts](https://md.research.elamur.ai/free/en/concepts/)