CYK Parsing

This is a Method page for CYK Parsing.

The Cocke–Younger–Kasami (CYK) algorithm is an algorithm for parsing PCFG. It is bottom up and makes use of dynamic programming.

Description

The input to the algorithm is a grammar $G$ in Chomsky Normal Form, and a sentence $X$. The idea behind the parsing algorithm is to recursively build parses from bottom up, and mantaining a chart C[i, j] which contains productions that generates X[i] ... X[j].

Pseudocode

''for'' each i = 1 to n
  ''for'' each production A -> a
    ''if'' a == X[i]
      ''add'' A to C[i,i]