Pseudocode for the CKY algorithm

When implementing, you'll want to take care when choosing data structures.

```function CKY(words, grammar)
score = new double[#words+1][#words+1][#nonterms]
back = new Triple[#words+1][#words+1][#nonterms]]

for ii = 0 to #words
begin = ii
end = ii+1

// Add the POS tags for this word.
for A in nonterms
if A -> words[begin] in grammar
score[begin][end][A] = P(A -> words[begin])

// Add all unary rules that match.
addUnary(score, back, begin, end)
done

for span = 2 to #words
for begin = 0 to #words-span
end = begin + span
for split = begin+1 to end-1
for A,B,C in nonterms
if A->BC is in the grammar
prob=score[begin][split][B]*score[split][end][C]*P(A->BC)
if(prob > score[begin][end][A])
score[begin]end][A] = prob
back[begin][end][A] = new Triple(split,B,C)

// Add all unary rules that match.
addUnary(score, back, begin, end)
done

// Call a function that uses your back pointers to rebuild the most probable tree.
return buildTree(score, back)
endfunc

// Add all unary rules that match.
function addUnary(score, back, begin, end)
while added a new rule in the last loop...
for A,B in nonterms
prob = P(A->B)*score[begin][end][B];
if(prob > score[begin][end][A])
score[begin][end][A] = prob
back[begin][end][A]  = B
endfunc

```