41.4. CYK Parsing¶
41.4.1. CYK Parsing¶
Invented by J. Cocke, D.H. Younger, and T. Kasami
Requires \(|w|^3\) steps to parse string \(w\).
Dynamic Programming remembers the answer to small subproblems so that it won’t have to solve them again.
For CYK Parsing, the grammar must be in Chomsky Normal Form (CNF) first.
41.4.1.1. CYK Parsing Algorithm¶
Note
\(A \in V_{ii}\) if and only if there is what kind of production?
Answer: \(A \rightarrow a_i\)
41.4.1.2. Algorithm¶
Compute \(V_{11}, V_{22}, V_{33}, \ldots, V_{nn}\)
Compute \(V_{12}, V_{23}, V_{34}, \ldots, V_{{n-1}n}\)
Compute \(V_{13}, V_{24}, V_{35}, \ldots, V_{{n-2}n}\)
\(\ldots\)
Last step is? Compute \(V_{1n}\)
How do we know if it worked? If the last step is \(S\)