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] ß {α | α à input_i}

for span ß 2 to #words

for begin ß 1 to #words – span + 1

end ß begin + span – 1

for m ß begin to end – 1

if (α à β₁β₂ Î P Ù

β₁ Î chart_{[begin, m]} Ù β₂ Î chart_{[m + 1, end]} then

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