CYK Algorithm (Parsing Context-Free Grammars)

The membership question

Given a context-free grammar G and a string w, is w in the language of G? Compilers must answer this for every program. The CYK algorithm (Cocke–Younger–Kasami) answers it for any grammar in Chomsky normal form (CNF), using the same table-filling idea as matrix chain multiplication and LCS.

Chomsky normal form

Every rule must look like X → YZ (two variables) or X → a (one terminal). Any grammar can be converted to this form.

The grammar used in the visualization:

S → AB | BC
A → BA | a
B → CC | b
C → AB | a

The idea

Let T[len][i] be the set of variables that can produce the substring of length len that starts at position i.

• Length 1: X is in the cell if there is a rule X → (that letter).
• Longer substrings: cut the substring into a left part and a right part in every possible way. If Y can produce the left part, Z the right part, and X → YZ is a rule, then X can produce the whole substring.

The string is accepted when S is in the top cell (the whole string).

Worked example: baaba

The top cell contains S, so baaba is generated by the grammar. For aabb the top cell is empty, so it is rejected.

Code

def cyk(w, binary, terminal):
    n = len(w)
    T = [[set() for _ in range(n)] for _ in range(n + 1)]
    for i, ch in enumerate(w):
        T[1][i] = {x for x, t in terminal if t == ch}
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            for k in range(1, length):
                for x, y, z in binary:
                    if y in T[k][i] and z in T[length - k][i + k]:
                        T[length][i].add(x)
    return 'S' in T[n][0]

Where is it used?

CYK is the textbook parser for exams, and the idea survives in practical parsers for natural language. Programming languages use faster algorithms such as LL and LR parsers, which work on restricted grammars in O(n) time.

Common mistakes

• Using a grammar that is not in CNF: rules like A → aB or S → ε break the table logic.
• Trying only one split point instead of all of them.
• Forgetting that a cell can hold several variables.
• Checking for S in the bottom row instead of the top cell.