CKY Parser
A probabilistic CYK chart parser with real Parseval evaluation, not just membership checking.
The Problem
Parsing a sentence under a context-free grammar requires handling genuine ambiguity — many different parse trees can be structurally valid, and you need an efficient way to find the most probable one. CKY is the classic dynamic-programming solution.
The Approach
Implemented the full Cocke-Kasami-Younger algorithm from scratch as a probabilistic (Viterbi) parser over a Chomsky Normal Form grammar — including chart construction, backpointer-based tree reconstruction, and a real Parseval-metric evaluation harness, not just a toy that checks whether a sentence parses.
Try It Live
A real client-side re-implementation of the probabilistic CKY parser above, running the same Viterbi chart-filling algorithm on a small demo grammar (vocabulary: a, ate, cat, chased, dog, house, in, man, on, park, saw, telescope, the, walked, with).
- ▹Chart is a sparse dict-of-dicts keyed by (i,j) span → nonterminal, storing either the terminal word (length-1 spans) or a backpointer pair to the two child constituents and their split point
- ▹Probabilistic scoring: for each span and nonterminal, takes log(rule_prob) + probs[left_child] + probs[right_child] across every valid split point, keeping only the maximum — genuine Viterbi decoding, O(n³·|G|) time
Highlights
- ▹True Viterbi/probabilistic CKY — tracks log-probabilities and keeps only the max-probability derivation per span, not just grammatical membership
- ▹Grammar validation is genuinely careful: uses math.fsum + math.isclose (not naive summation) to verify each nonterminal's rule probabilities actually sum to 1.0
- ▹Evaluation implements real Parseval precision/recall/F-score, plus parser coverage — and reports F-score both over parsed-only sentences and over all sentences, so failed parses can't silently inflate the number
- ▹Fully dependency-free — pure Python standard library