### Pseudocode for the CKY algorithm

When implementing, you don't actually want to use triple arrays like this.
Create a nice data structure, like Cell.java, which holds all of a table cell's info. Then create a double array of those cells!

```function CKY(words, grammar)
cells = new Cell[#words+1][#words+1]

// Fill in the table's diagonal, the words' tags
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
cells[begin][end].addNonTerminal(A, P(A -> words[begin]))

// Add all unary rules that match.
done

// Fill in the rest of the table
for span = 2 to #words
for begin = 0 to #words-span
end = begin + span
for split = begin+1 to end-1
for each rule A->BC in the grammar
prob = cells[begin][split].getScore(B) * cells[split][end].getScore(C) * P(A->BC)
if(prob > cells[begin][end].getScore(A))
cells[begin][end].setScore(A, prob)
cells[begin][end].setBackPointer(A, new Triple(split,B,C))

// Add all unary rules that match.
done

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

// Add all unary rules that match.
function addUnary(cells, begin, end)
while added a new rule in the last loop...
for each unary rule A->B in the grammar
prob = P(A->B) * cells[begin][end].getScore(B);
if(prob > cells[begin][end].getScore(A))
cells[begin][end].setScore(A, prob)
cells[begin][end].setBackPointer(A, new Triple(-1,B,null))  // special unary rule, no split!
endfunc

```