The CYK Algorithm

We conclude the discussion of context-free languages by answering the question, “How can we tell whether a string is in the language of a context-free grammar?”

Parsing is the process of taking a linear sequence of characters and converting this into structured data, such as a parse tree (or, more commonly in practice, into a simplified version of the parse tree called an Abstract Syntax Tree).

There are a number of clever parsing algorithms commonly used in practice, including Recursive Descent and Shift-Reduce Parsing. Both of these algorithms are very efficient; parsing a string of length $n$ can be done in $O(n)$ time.

Unfortunately, these algorithms only work for some CFGs, not all. Recursive Descent is designed to work if the CFG is “LL($k$)” (for some $k\geq 1$), while Shift-Reduce Parsing works if the CFG is “LR($k$)” or “LALR($k$)” (for some $k\geq 0$).

In many computer applications, this isn’t a problem, because we can often modify the grammar or even the entire language to make these algorithms work! The original designers of Java, for example, chose a syntax for the language—keywords, operators, punctuation, etc.—specifically designed to be LALR(1).

However, we don’t always have the option of changing the language. A linguist trying to model a portion of English using CFGs, for example, doesn’t have the option of changing the syntax of English to make it easier to parse! And since this is a course on Theory of Computability, we still might like to know whether it’s possible to parse strings using arbitrary context-free grammars.

The answer is yes!

The CYK Algorithm

There are several parsing algorithms that work for all CFGs, such as Earley’s Algorithm, though none are terribly efficient (often $O(n^3)$ for an input of length $n$). Here we will briefly describe the CYK Algorithm, probably the simplest algorithm for general-purpose CFG parsing.

(The CYK algorithm was independently invented by many researchers; the name comes from the initials of Cocke, Younger, and Kasami, three of people who rediscovered and published this algorithm.)

Chomsky Normal Form

The CYK algorithm only works (efficiently) for grammars in Chomsky Normal Form. This is less a problem than it might seem at first, because there’s an algorithm to convert any CFG into Chomsky Normal Form grammar with the same language. In fact, if the grammar doesn’t explicitly mention $\epsilon$, then the conversion is relatively easy to do by hand:

The Idea

Suppose our input is a string

(where $n\geq 1$). The idea is to answer the question, “For every substring of the input $a_i\ldots a_k$, what nonterminals can produce that substring?”

We denote by ${\cal N}(i,k)$ the set of nonterminals that can produce the substring $a_i\ldots a_k$.

More formally, for every $i,k$ such that $1 \leq i \leq k \leq n$,

We are primarily interested in calculating the set ${\cal N}(1,n)$, because the start symbol $S$ is in this set iff $S\Rightarrow\cdots\Rightarrow a_1\cdots a_n$, that is, iff our given string is in the language of the grammar.

The Algorithm

We can calculate ${\cal N}(1,n)$ recursively as follows:

That is,

• Since our grammar is in Chomsky normal form, the only nonterminals that can produce a single character substring $a_i$ are those with a rule that directly replaces that nonterminal with character $a_i$.
• For a nonterminal $C$ to produce a longer string $a_i\cdots a_k$, there has to be a rule $C\to AB$ such that $A$ produces the first part of this string and $B$ produces the rest.

In practice, we don’t want to directly implement this recursive definition, because we end up with a lot of redundant work. (The same function calls happen over and over again. This is the same problem with the simple recursive definition of the Fibonacci function.) The easiest solution is to use Dynamic Programming.

In the Dynamic Programming implementation of CYK, we create a two-dimensional array N of size $n$ by $n$, with the idea that N[i,k] will hold the value of ${\cal N}(1,n)$. Then we can define

If we fill the entries of the array in the right order (starting at the diagonal), then we can ensure that when computing the value of a new array cell, we only look at other entries in the array that have already been computed. The last cell filled is N[1,$n$]; if it contains our start symbol then we have verified that the entire strings is in the language of the grammar.

For a string of length $n$ we have to calculate values for $O(n^2)$ array elements, each containing a set of nonterminals. Each calculation takes $O(n)$ on average, so the CYK Algorithm runs in total time $O(n^3)$.