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)
   score = new double[#words+1][#words+1][#nonterms]
   back = new Triple[#words+1][#words+1][#nonterms]

   // 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
            score[begin][end][A] = P(A -> words[begin])

      // Add all unary rules that match.
      addUnary(score, back, 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 = 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 each unary rule A->B in the grammar
         prob = P(A->B) * score[begin][end][B];
         if(prob > score[begin][end][A])
            score[begin][end][A] = prob
            back[begin][end][A]  = new Triple(-1,B,null)  // special unary rule, no split!
endfunc