CYK Parsing Algorithm
What you'll learn: You'll learn how to parse context-free grammars efficiently using a bottom-up, dynamic programming approach that works on grammars in Chomsky Normal Form.
The Core Idea
The CYK (Cocke-Younger-Kasami) algorithm is a parsing method that determines whether a string belongs to the language generated by a context-free grammar. It builds up parse information from small substrings to larger ones, storing results in a table to avoid redundant work.
Think of it like assembling a jigsaw puzzle from the bottom up: you first identify which small pieces (individual symbols) can form valid pairs, then which pairs can combine into larger structures, and so on until you've built the complete picture (the full string).
How It Works
The algorithm requires the grammar to be in Chomsky Normal Form (CNF), where every production is either A → BC (two nonterminals) or A → a (one terminal).
You build a triangular table where:
- Row 1 identifies which nonterminals can generate each single character
- Row 2 identifies which nonterminals can generate each two-character substring
- Row i identifies which nonterminals can generate each substring of length i
For each cell, you check all possible ways to split the substring into two parts, consulting previously filled cells to see if any grammar rule can combine those parts.
The string is accepted if the start symbol appears in the top cell (covering the entire string).
Why Dynamic Programming?
Without storing intermediate results, you'd repeatedly analyze the same substrings. The CYK table ensures each substring is analyzed exactly once, giving O(n³|G|) time complexity, where n is string length and |G| is grammar size.
Key Takeaway: The CYK algorithm uses dynamic programming on CNF grammars to parse strings bottom-up, efficiently determining membership by building a table of substring derivations.