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.

Definition: A CFG is in Chomsky Normal Form (CNF) if all productions are of the form

$A \rightarrow BC$ or

$A \rightarrow a$

where

$A, B, C \in V$ and

$a \in T$ .

Assume G=(V,T,S,P) is in CNF, and w=a1a2...an.
Define substrings wij=ai...aj.
Define subsets of
V,Vij={A∈V∣A∗⇒wij}
Then w∈L(G) if and only if S∈V1n.

Note

$A \in V_{ii}$ if and only if there is what kind of production?

Answer: $A \rightarrow a_i$

All

$V_{ii}$ are easy, just based on if there is a production.

Note: Compute

$V_{ij}$ . For

$j >i$ ,

$A$ derives

$w_{ij}$ if and only if there is a production

$A \rightarrow BC$ with

$B \stackrel{*}{\Rightarrow} w_{ik}$ and

$C \stackrel{*}{\Rightarrow} w_{{k+1}j}$ for some

$k$ with

$i \le k, k < j$ .

How do we know if it worked? If the last step is $S$