function CYK-Parse(words, grammar) returns P, a table of probabilities
N ← Length(words)
M ← the number of nonterminal symbols in grammar
P ← an array of size [M, N, N], initially all 0
/* insert lexical rules for each word */
for i = 1 to N do
for each rule of form (X → wordsi[P]) do
P[X, i, 1] ← p
/* Combine first and second parts of right-hand sides of rules, from short to long */
for length = 2 to N do
for start = 1 to N - length + 1 do
for len1 = 1 to length - 1 do
len2 ← length - len1
for each rule of the form (X → Y Z [p]) do
P[X, start, length] ← Max(P[X, start, length], P[Y, start, len1] x P[Z, start + len1, len2] x p)
return P
Figure ?? The CYK algorithm for parsing. Given a sequence of words, it finds the most probable derivation for the whole sequence and for each subsequence. It returns the whole table, P, in which and entry P[X, start, len] is the probability of the most probable X of length len starting at position start. If there is no X of that size at that location, the probability is 0.