CYK Method

The Cocke-Younger-Kasami parsing method is based on a bottom-up approach to the partitioning of the input. In its most general form it is identical to chart parsing.

The algorithm proceeds as follows:

Phase 1

For each symbol in the input string, construct a set of all those non-terminals that can generate that symbol on its own. (This can be calculated from the grammar)

Phase 2

For each adjacent pair of symbols, construct a set consisting of all those non-terminals that can derive that pair, or some pairing of their phase 1 non-terminals.

Phase $i$

For each substring of the input of length $i$, construct a set of non-terminals which can generate that string, or some combonation of the terminals in the string and any phase $k$ non-terminals (for any $k < i$).

We are finished if the start symbol is a phase $n$ non-terminal, where $n$ is the string length.