Ling 472 Section, November 7, 2003

 

Revised pseudo code for the (non-probabilistic) CKY algorithm:

 

Create and clear chart[#words, #words]

 

for i ß 1 to #words

   chart[i, i] ß {α | α à inputi}

 

for span ß 2 to #words

   for begin ß 1 to #wordsspan + 1

      end ß begin + span – 1

      for m ß begin to end – 1

         if (α à β1β2 Î P Ù

            β1 Î chart[begin, m] Ù β2 Î chart[m + 1, end] then

               chart[begin, end] = chart[begin, end] È {α}