Syntactic parsing is the algorithmic process of mapping a linear sequence of natural language words into its underlying hierarchical grammatical constituent or dependency tree. Because human languages exhibit rampant structural ambiguities, brute-force recursive backtracking suffers from exponential time complexity. Dynamic programming chart parsers provide guaranteed polynomial-time solutions.
1. The Problem of Structural Syntactic Ambiguity
In natural language, a single surface sentence can admit a combinatorial explosion of distinct structural interpretations. The most pervasive ambiguity is prepositional phrase (PP) attachment:
[
ext{“I saw the man with the telescope.”}
]
- VP Attachment: The PP modifies the verb saw (implies) The instrument used for seeing was a telescope: ([_{VP} ext{ saw } [_{NP} ext{ the man }] [_{PP} ext{ with the telescope }]]).
- NP Attachment: The PP modifies the noun man (implies) The man was in physical possession of a telescope: ([_{VP} ext{ saw } [_{NP} ext{ the man } [_{PP} ext{ with the telescope }]]]).
For sentences with (k) successive prepositional phrases, the number of distinct valid parse trees scales with the Catalan number (C_k = rac{1}{k+1} binom{2k}{k}), which grows exponentially ((sim 4^k / k^{3/2})), rendering naive search impossible.
2. Chomsky Normal Form (CNF)
The Cocke-Younger-Kasami (CYK) algorithm requires the grammar to be formulated in Chomsky Normal Form (CNF). A Context-Free Grammar is in CNF if all production rules are strictly binary non-terminal branching or unary terminal emissions:
[
A o B C quad ext{or} quad A o a
]
Any arbitrary CFG can be algorithmically converted into weakly equivalent CNF in four deterministic steps: eliminating (psilon)-rules ((A o psilon)), removing unit rules ((A o B)), replacing terminals in mixed rules, and binarizing long rules with auxiliary variables ((A o B C D implies A o B X_1, X_1 o C D)).
3. The Cocke-Younger-Kasami (CYK) Dynamic Programming Algorithm
The CYK algorithm parses a sentence of (n) words (w_1 w_2 dots w_n) by filling a triangular dynamic programming table (T), where cell (T[i, j]) stores the set of all non-terminal symbols that can generate the substring spanning from word (w_{i+1}) to word (w_j) ((0 le i < j le n)).
CYK Execution Steps:
- Base Case (Length 1 Substrings): For each terminal word (w_i) along the diagonal ((j = i+1)):
[
T[i-1, i] = { A mid A o w_i in P }
] - Recursive Step (Lengths (l = 2) to (n)): For every span length (l), starting position (i), and endpoint (j = i + l), iterate over all possible intermediate split points (k) ((i < k < j)):
[
T[i, j] = bigcup_{k=i+1}^{j-1} { A mid A o B C in P, ext{ where } B in T[i, k] ext{ and } C in T[k, j] }
] - Termination: The sentence is grammatically valid if and only if the start symbol (S) is contained in the apex cell spanning the entire string: (S in T[0, n]).
Because CYK employs three nested loops (span length (l in [1, n]), start position (i in [1, n]), and split point (k in [1, n])), its algorithmic time complexity is strictly cubic in sentence length:
[
mathcal{O}(n^3 cdot |P|)
]
where (|P|) is the size of the CNF rule set.
4. Dependency Parsing: Transition-Based Arc-Eager Algorithms
While constituency parsing builds hierarchical phrase brackets, dependency grammar maps grammatical structure directly as a directed acyclic graph (DAG) of asymmetric head-dependent relations between individual words:
[
ext{Root} xrightarrow{ ext{nsubj}} ext{saw} xrightarrow{ ext{obj}} ext{dog}
]
Modern fast computational parsers utilize transition-based dependency parsing (Joakim Nivre). Operating with a stack (sigma), an input buffer (beta), and a set of accumulated dependency arcs (A), the parser executes four elementary atomic transitions:
- Shift: Removes the front word from buffer (beta) and pushes it onto stack (sigma).
- Left-Arc: Asserts a dependency link (( ext{top of buffer} o ext{top of stack})) and pops the stack.
- Right-Arc: Asserts a link (( ext{top of stack} o ext{top of buffer})) and pushes the buffer item onto the stack.
- Reduce: Pops the top of the stack if it already possesses a head.
Guided by multi-class neural network classifiers predicting the optimal transition at each state, transition-based parsers construct complete grammatical dependency trees in strictly linear time (mathcal{O}(n)), processing hundreds of sentences per second in industrial NLP pipelines.
