Syntactic Parsing
Consider the sentence "I saw the man with the telescope." Did the speaker use a telescope to see the man? Or did they see a man who was holding a telescope? A human reader effortlessly juggles both readings. But a machine needs a formal way to represent each interpretation. It needs this before it can reason about meaning, translate the sentence, or answer questions about it. Syntactic parsing is the process of assigning a grammatical tree structure to a sentence. It makes explicit how words combine into phrases. It also shows how phrases combine into the whole sentence. That tree is exactly what disambiguates the two readings above. The prepositional phrase "with the telescope" attaches either to the verb phrase or to the noun phrase "the man." Parsing sits at the boundary between symbolic linguistics and statistical modeling. It powers a surprising range of downstream systems. Machine translation systems use parse structure to reorder phrases correctly. This matters across languages with different word orders. Grammar checkers use parses to detect subject-verb agreement violations. Information extraction systems use parses to identify who did what to whom. Even modern large language models rarely build explicit trees. But they are trained on objectives that implicitly reward learning the same hierarchical regularities. These are the regularities that constituency grammars make explicit. Recognizing phrase boundaries is baked into how attention patterns organize themselves in transformer layers. This article builds up the classical machinery. It covers context-free grammars as a model of phrase structure. It covers the CKY algorithm for exhaustively parsing a sentence in polynomial time. It also covers probabilistic context-free grammars (PCFGs). These are used for choosing the single best parse among exponentially many candidates. We assume familiarity with Part-of-Speech Tagging. This is because part-of-speech tags are typically the terminal symbols. A parser's grammar rewrites these terminal symbols into phrases. By the end, you will understand precisely why naive recursive-descent parsing explodes combinatorially on ambiguous sentences. You will see how dynamic programming tames that explosion. You will learn how probabilities are estimated and combined to score whole trees. And you will see where the approach's real weaknesses lie. These weaknesses motivate the shift toward Dependency Parsing and neural parsers in later material.
- Constituency parsing assigns a sentence a tree showing how words group into nested phrases (NP, VP, PP, …).
- Context-free grammars (CFGs) formalize phrase structure with rewrite rules like `VP → V NP`.
- Naive parsing is exponential because of structural ambiguity; CKY parsing uses dynamic programming to run in polynomial time.
- CKY requires the grammar in Chomsky Normal Form (CNF), where every rule has exactly two nonterminals or one terminal on its right side.
- Probabilistic CFGs (PCFGs) attach probabilities to rules, letting a parser pick the single most likely tree instead of returning every legal one.
- Constituency parsing struggles with long-range dependencies and lexical selection, motivating dependency-based and neural approaches.
A sentence's meaning-bearing structure can be recovered by recursively grouping words into phrases according to a grammar, and dynamic programming lets us find the best such grouping in polynomial rather than exponential time.
The idea
A constituent is a group of words that behaves as a single unit within a larger structure — it can be moved, replaced by a pronoun, or coordinated with another constituent of the same type. "The man with the telescope" is a constituent (a noun phrase, NP) because it can be replaced wholesale by "he." A context-free grammar (CFG) is a formal system for generating exactly the legal constituent structures of a language. It consists of a set of terminal symbols (words, or part-of-speech tags), a set of nonterminal symbols (phrase categories like NP, VP, PP, S), a designated start symbol (usually S, for sentence), and a set of production rules of the form `A → β`, where `A` is a single nonterminal and `β` is a string of terminals and/or nonterminals. The grammar is context-free because the left-hand side is always a lone nonterminal — the rule for rewriting `NP` applies wherever an `NP` occurs, regardless of surrounding context. Parsing is the inverse of generation: given a sentence (a string of terminals), find one or more derivation trees — also called parse trees or constituency trees — that the grammar could have used to generate it. Each internal node of the tree is a nonterminal labeled with a phrase category, each leaf is a terminal word, and each internal node's children correspond to the right-hand side of some grammar rule. The fundamental challenge is that natural-language grammars are highly ambiguous: the same string of words is often derivable via many distinct trees, corresponding to different meanings ("I saw the man with the telescope" has at least two trees, from the attachment ambiguity described above). A parser's job is not just to find a tree but to search the exponentially large space of legal trees efficiently, and, in the probabilistic setting, to identify the most probable one. Two properties make this tractable. First, phrase structure is recursively self-similar — an NP can contain a PP, which contains another NP, and so on — so the grammar is naturally described by a small number of recursive rules rather than an enumeration of every possible sentence. Second, and crucially for algorithmic purposes, the best subtree spanning a given span of words depends only on that span, not on what lies outside it (an instance of optimal substructure), which is exactly the condition that makes dynamic programming applicable.
How it works
Context-free grammars and Chomsky Normal Form
A small illustrative grammar for our running example might include: ``` S → NP VP NP → Det N | Det N PP | Pronoun VP → V NP | VP PP PP → P NP Det → the N → man | telescope V → saw P → with Pronoun → I ``` Applied to "I saw the man with the telescope," this grammar admits two derivations because `PP` can attach either as a child of `VP` (verb-attachment: I used the telescope to see) or as a child of the inner `NP` (noun-attachment: the man had the telescope). The classical exhaustive-search parsing algorithm, CKY (Cocke–Kasami–Younger), requires the grammar to be in Chomsky Normal Form (CNF): every rule is either `A → B C` (two nonterminals) or `A → a` (one terminal). Any CFG can be converted to an equivalent CNF grammar (generating the same language, with trees convertible back and forth) through three transformations: 1. Binarization: replace rules with more than two symbols on the right, e.g., `VP → V NP PP`, by introducing a new nonterminal, e.g., `VP → V VP-bar`, `VP-bar → NP PP`. 2. Unit-rule elimination: replace chains like `NP → Pronoun`, `Pronoun → I` by directly deriving `NP → I` (or, keeping tags as preterminals, collapsing unit productions between nonterminals). 3. Terminal isolation: ensure rules mixing terminals and nonterminals, e.g., `PP → with NP`, are rewritten so terminals appear only in unit rules, e.g., `PP → P NP`, `P → with`.
The CKY algorithm
CKY fills a triangular dynamic-programming table indexed by spans of the input. For a sentence of `n` words, cell `table[i][j]` holds the set of nonterminals that can generate the substring spanning positions `i` through `j`. The table is filled from short spans to long spans; each cell of length greater than one is computed by trying every way to split the span into a left part and a right part, and combining nonterminals found in each part according to grammar rules of the form `A → B C`. ``` function CKY-PARSE(words[1..n], grammar):
# table[i][j] = set of (nonterminal, backpointer) pairs
# that derive words[i..j], for 1 <= i <= j <= n initialize table[i][j] = empty set for all i, j
# Base case: spans of length 1 (single words) for i in 1..n: for each rule (A -> words[i]) in grammar: add (A, LEAF) to table[i][i]
# Recursive case: spans of increasing length for length in 2..n: for i in 1..(n - length + 1): j = i + length - 1 for k in i..(j - 1): # split point for each rule (A -> B C) in grammar: if (B, _) in table[i][k] and (C, _) in table[k+1][j]: add (A, (k, B, C)) to table[i][j] if (StartSymbol, _) in table[1][n]: return BUILD-TREES(table, 1, n, StartSymbol) else: return "no parse" ``` The base case handles single words directly via lexical rules `A → word`. The recursive case is the heart of the algorithm: to know whether nonterminal `A` can span positions `i..j`, we ask, for every possible split point `k`, whether there is a rule `A → B C` such that `B` spans `i..k` and `C` spans `k+1..j`. Because the grammar is in CNF, every possible way of building a tree over span `i..j` corresponds to exactly one such split and one such rule, so trying all splits and all rules is exhaustive and correct — this is precisely the recurrence that dynamic programming exploits, since each cell's answer is computed purely from strictly smaller sub-cells that have already been finalized.
From recognition to parsing, and to the single best tree
As written, CKY is a recognizer: it answers yes/no to "does the grammar generate this sentence" by checking whether the start symbol appears in `table[1][n]`. To recover actual trees, each cell stores backpointers to the split point and child nonterminals that justified adding each entry, and `BUILD-TREES` recursively follows these backpointers to reconstruct one or all derivations. Because natural grammars are ambiguous, `table[1][n]` may contain the start symbol via many different backpointer chains — exponentially many, in general. To select a single preferred tree, we attach probabilities to rules, forming a Probabilistic Context-Free Grammar (PCFG). Each rule `A → β` carries a probability `P(A → β | A)`, and probabilities of all rules expanding the same nonterminal `A` must sum to 1. The probability of an entire tree is the product of the probabilities of every rule used in its derivation: ``` P(tree) = ∏ over all rules (A -> β) used in the tree of P(A -> β | A) ``` The probabilistic CKY algorithm (also called the Viterbi CKY or CKY-Viterbi) modifies the recognizer to track, for each nonterminal in each cell, only the highest-probability way of deriving that nonterminal over that span, discarding lower-probability alternatives immediately — an application of the Viterbi/dynamic-programming principle that the globally best tree must be built from locally best sub-trees. ``` function PROB-CKY-PARSE(words[1..n], pcfg): initialize score[i][j][A] = 0 for all i, j, A initialize back[i][j][A] = null for i in 1..n: for each rule (A -> words[i], p) in pcfg: if p > score[i][i][A]: score[i][i][A] = p back[i][i][A] = LEAF for length in 2..n: for i in 1..(n - length + 1): j = i + length - 1 for k in i..(j - 1): for each rule (A -> B C, p) in pcfg: candidate = p score[i][k][B] score[k+1][j][C] if candidate > score[i][j][A]: score[i][j][A] = candidate back[i][j][A] = (k, B, C) if score[1][n][StartSymbol] > 0: return TRACE-BACK(back, 1, n, StartSymbol) else: return "no parse" ``` Rule probabilities are typically estimated from a treebank — a corpus of hand-annotated parse trees, most famously the Penn Treebank — via maximum likelihood estimation: ``` P(A -> β | A) = Count(A -> β in treebank) / Count(A in treebank) ```
Complexity & correctness
Time complexity. CKY's triple-nested loop structure directly gives the bound. There are `O(n²)` distinct spans `(i, j)`. For each span of length `length`, the algorithm tries `O(n)` split points `k`. At each split point, it checks every binary grammar rule, a constant `|Grammar|` independent of `n`. This yields: ``` O(n²) spans × O(n) split points × O(|Grammar|) rule checks = O(n³ · |Grammar|) ``` For a fixed grammar, this is O(n³) in sentence length — polynomial, in sharp contrast to naive recursive-descent or top-down backtracking parsers, which can require exponential time in the worst case because they may re-derive the same sub-span's parse many times across different branches of the search (the same inefficiency that motivates memoization in any exponential recursive-substructure problem, such as computing Fibonacci numbers without a cache). The dependence on grammar size is more precisely `O(n³ · |R|)` where `|R|` is the number of binary rules, since for a fixed split point we must check compatibility against all rules; with suitable indexing of rules by their right-hand-side symbols this factor can often be reduced but not eliminated.
Space complexity. The table has `O(n²)` cells, and each cell stores at most `|Nonterminals|` entries (one score/backpointer per nonterminal that can span it), giving O(n² · |Nonterminals|) space.
Correctness argument. The proof is by induction on span length, mirroring exactly how the algorithm executes. Base case (length 1): `table[i][i]` correctly contains nonterminal `A` if and only if the grammar has a rule `A → word[i]`, which is exactly what the initialization loop checks. Inductive step: Assume `table[i'][j']` is correct (complete and sound) for every span with `j' - i' < j - i`. A nonterminal `A` derives `words[i..j]` if and only if some CNF rule `A → B C` was used at the root of that derivation, splitting the span at some point `k` into a left part derived by `B` and a right part derived by `C`. Since `B` derives a strictly shorter span `i..k` and `C` derives a strictly shorter span `k+1..j`, by the inductive hypothesis both `B ∈ table[i][k]` and `C ∈ table[k+1][j]` are correctly known already. The algorithm's inner loop tries every split `k` and every rule `A → B C`, so it will find this decomposition exactly when it exists. Hence `table[i][j]` is filled correctly. Because CNF restricts every production to binary or unary lexical form, "some split point and some binary rule" is a fully exhaustive characterization of how any subtree can be built — there is no other shape a CNF derivation can take. This is why CNF conversion is not a mere technicality but the structural fact that makes the split-point enumeration complete. For probabilistic CKY, the same induction applies to scores rather than membership: the highest-probability derivation of `A` over `i..j` must, at its root, split into some best derivation of `B` over `i..k` and some best derivation of `C` over `k+1..j`, because the probability of the whole tree is a product over independent rule applications and maximizing a product of independently-computed factors is achieved by maximizing each factor — this is the same optimality argument underlying the Viterbi algorithm for Part-of-Speech Tagging via Hidden Markov Models.
Tradeoffs. CKY guarantees finding the truly best-scoring parse under the PCFG, but plain PCFGs are known to be poor probability models of real sentences: they ignore lexical content (a `VP → V NP` rule's probability does not depend on which verb or noun appear), so PCFGs badly conflate attachment ambiguities that hinge on specific words (like "saw...with a telescope" versus "saw...with a friend"). Lexicalized PCFGs and later neural constituency parsers fix this at the cost of much larger grammars or entirely different scoring mechanisms. Even with a good probability model, `O(n³)` becomes a real bottleneck at web scale, motivating approximate and incremental parsers, and eventually the shift toward simpler, faster dependency structures, previewed in Dependency Parsing.
Worked example
Take the ambiguous sentence "I saw the man with the telescope" and the toy grammar given earlier, converted implicitly to CNF (imagine `Det N` and `Det N PP` binarized as needed; we display the human-readable non-CNF rules for clarity). Running probabilistic CKY with illustrative rule probabilities:
| Rule | Probability |
|---|---|
| `S → NP VP` | 1.0 |
| `VP → V NP` | 0.7 |
| `VP → VP PP` | 0.3 |
| `NP → Det N` | 0.4 |
| `NP → Det N PP` | 0.3 |
| `NP → I` (Pronoun) | 0.3 |
| `PP → P NP` | 1.0 |
Two full derivations exist for the sentence, differing in where `PP = "with the telescope"` attaches:
Verb attachment (VP → VP PP): `S → NP(I) VP`, where `VP = VP(saw the man) PP(with the telescope)`. Probability contribution from the ambiguous choice: `P(VP → V NP) × P(VP → VP PP) = 0.7 × 0.3 = 0.21`.
Noun attachment (NP → Det N PP): `S → NP(I) VP(saw NP(the man with the telescope))`, where the object NP itself contains the PP. Probability contribution: `P(VP → V NP) × P(NP → Det N PP) = 0.7 × 0.3 = 0.21`. In this deliberately symmetric toy example the two trees tie, which is realistic: plain PCFGs frequently cannot distinguish attachment preferences because the rule probabilities do not look at the actual words "telescope" or "saw." A lexicalized model, which conditions rule probabilities on head words (e.g., `P(VP → VP PP | head verb = "saw")` versus `P(NP → Det N PP | head noun = "man")`), can break this tie using corpus statistics about which verbs and nouns tend to take which prepositional attachments — precisely the limitation flagged in the complexity discussion above. Tracing the chart itself: `table[1][1] = {NP}` (from "I" via the Pronoun rule), `table[2][2] = {V}` ("saw"), `table[3][3] = {Det}` ("the"), `table[4][4] = {N}` ("man"), `table[5][5] = {P}` ("with"), `table[6][6] = {Det}` ("the"), `table[7][7] = {N}` ("telescope"). Building upward: `table[3][4] = {NP}` ("the man," via `Det N`), `table[5][7] = {PP}` ("with the telescope," via `P NP` where `table[6][7] = {NP}` first), `table[2][4] = {VP}` ("saw the man," via `V NP`), `table[3][7] = {NP}` ("the man with the telescope," via `Det N PP`), `table[2][7] = {VP}` via two distinct backpointers (`VP PP` split at 4, or `V NP` split at 2 using the larger NP), and finally `table[1][7] = {S}` combining `NP(1,1)` with either `VP` derivation.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Forgetting to convert to CNF before running CKY | Grammar has rules with 3+ symbols or unit chains on the right-hand side | Split-point enumeration silently misses valid derivations; recognizer returns false negatives |
| Treating PCFG rule probabilities as context-independent | Ignoring that `A → β` probability should really depend on lexical heads | Attachment ambiguities (PP-attachment, coordination) are resolved arbitrarily or tied |
| Confusing recognition with parsing | CKY as described only checks table membership | Forgetting to store and follow backpointers means no actual tree is ever produced |
| Off-by-one in span indexing | Spans can be inclusive `[i,j]` or half-open `[i,j)`; mixing conventions | Split-point loop bounds become wrong, causing missed or duplicated combinations |
| Assuming O(n³) is always fast enough | Grammar size and constant factors ignored | Real-world grammars (thousands of rules from a treebank) make wall-clock time far worse than toy estimates suggest |
| Believing CFGs capture all of syntax | Cross-serial dependencies and certain long-range agreement phenomena are not context-free | Some natural language constructions (e.g., in Swiss German) provably require mildly context-sensitive formalisms |
Pioneers & history
Origins · 1 minNoam Chomsky and how this was discovered
Where this matters
Statistical constituency parsers trained on the Penn Treebank, such as the Stanford Parser and the Charniak and Collins lexicalized parsers, were for years a standard component of NLP pipelines for tasks like question answering and information extraction, where phrase boundaries help identify candidate answer spans or extraction targets. Grammar-checking and writing-assistance tools use constituency structure to detect subject-verb agreement errors and awkward attachments. Machine translation systems, especially syntax-based statistical MT systems that predate neural sequence-to-sequence models, used constituency parses of the source language to guide reordering into the target language's word order. Speech synthesis systems use phrase structure to predict prosodic boundaries — where a speaker should pause — since phrase boundaries in text correlate strongly with natural pauses in speech. Even in the era of large neural language models that do not explicitly output trees, probing studies have shown that hidden representations in transformer-based models implicitly encode constituency-like structure, suggesting that the linguistic regularities CFGs formalize remain relevant even when not explicitly engineered into the architecture. The core dynamic-programming idea behind CKY — decompose a global structure-scoring problem into scores over sub-spans combined at a split point — recurs directly in the alignment and scoring algorithms used in Dependency Parsing and in sequence alignment problems throughout computational biology and speech recognition.
Ask the tutor: How does lexicalizing a PCFG change the CKY dynamic-programming recurrence, and what does it cost in complexity?
What is the difference between constituency parsing and dependency parsing?
Constituency parsing groups words into nested phrases labeled with categories (NP, VP, PP), producing a tree whose internal nodes are phrase types and whose leaves are words. Dependency parsing instead draws direct binary relations between individual words — a verb governs its subject, an adjective modifies its noun — producing a tree whose nodes are the words themselves, with no separate phrase-category nodes. Dependency trees are often faster to parse (many algorithms run in linear or near-linear time) and transfer more directly across languages with flexible word order, since they emphasize grammatical relations over rigid phrase templates. Constituency structure is still useful when phrase-level operations (like movement, ellipsis, or coordination scope) matter, but dependency parsing has become the dominant practical formalism, as previewed by its role as the natural next topic after constituency parsing.
Why is CKY parsing O(n³) rather than something faster like O(n log n)?
The O(n²) factor comes from the number of distinct contiguous spans in a sentence of length n — there are roughly n²/2 pairs of start and end positions. For each span, the algorithm must try every possible split point where a left constituent and right constituent could meet, and there are O(n) such split points per span. Multiplying these together gives O(n³). This is not an artifact of a poor implementation; it reflects the genuine combinatorial cost of considering all ways two shorter constituents could combine into a longer one, and no algorithm for general CFG parsing is known to beat cubic time in the worst case, though faster algorithms exist for restricted grammar classes.
What exactly is Chomsky Normal Form and why does converting to it not lose information?
Chomsky Normal Form requires every production rule to be either `A → B C` (exactly two nonterminals) or `A → a` (exactly one terminal), with no rule directly generating the empty string (except possibly a rule from the start symbol, handled as a special case). Any context-free grammar can be mechanically transformed into an equivalent CNF grammar generating exactly the same language, through binarizing longer right-hand sides, eliminating unit productions, and isolating terminals into their own rules. The transformation changes the shape of the derivation trees (adding intermediate nonterminals for binarized rules) but a straightforward inverse transformation recovers the original tree shape, so no grammatical information about the language is lost, only the internal bookkeeping of how trees are represented.
How are PCFG rule probabilities estimated in practice?
The standard approach is maximum likelihood estimation from a treebank: for every rule `A → β` that appears in the annotated trees, count how many times that exact rule was used, and divide by the total count of all rules expanding the same nonterminal `A`. This gives the relative frequency estimate `P(A → β | A) = Count(A → β) / Count(A)`, which is the maximum likelihood estimator under a simple generative model where each rule choice is treated as an independent multinomial draw conditioned on the parent nonterminal. In practice, smoothing is applied to handle rules unseen in training data, and lexicalized or refined-grammar variants condition probabilities on head words or split nonterminals into finer-grained subcategories to improve accuracy.
Can context-free grammars capture all syntactic phenomena in natural language?
Not entirely. Certain constructions, most famously cross-serial dependencies in Swiss German subordinate clauses, have been shown to require a formalism strictly more expressive than context-free grammars while still less expressive than fully context-sensitive grammars — a class called mildly context-sensitive. Tree-adjoining grammars and combinatory categorial grammars were developed partly to handle such cases while retaining efficient (polynomial-time) parsing algorithms. For the vast majority of practical NLP applications, however, context-free grammars augmented with lexicalization or probabilistic refinement provide a good enough approximation, and the extra expressive power of mildly context-sensitive formalisms is rarely needed.
Why did constituency parsing become less central in modern NLP pipelines?
Two forces pushed constituency parsing out of the pipeline spotlight. First, dependency parsing offers comparable or better accuracy for many downstream tasks while being computationally cheaper and more directly useful for extracting grammatical relations like subject and object. Second, neural sequence models, particularly transformer-based large language models, learn to perform downstream tasks (translation, question answering, summarization) end-to-end from raw text, without an explicit parsing stage, and empirically these models capture much of the useful structural information implicitly. Constituency parsing remains valuable in linguistics research, certain grammar-checking tools, and as a diagnostic for probing what neural models have learned about syntax.
What is the practical difference between a parser that only recognizes and one that returns trees?
A recognizer answers a yes/no question: does this grammar generate this string. This is enough to test grammaticality but useless for any task needing the actual structure, such as extracting who did what to whom. A full parser augments the same dynamic-programming table with backpointers recording exactly which split point and child nonterminals justified each table entry, so that after the table is filled, a simple recursive traceback reconstructs an actual tree (or, with a beam or k-best modification, several top trees). Almost every practical application needs a full parser, since the tree itself, not merely its existence, is what encodes disambiguating structure like attachment decisions.