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.
      addUnary(cells, begin, end)
   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.
            addUnary(cells, begin, end)
   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