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