13.4.1 CKY Parsing

Let's begin our investigation of CKY algorithm by examining one of its major requirements: the grammars used with it must be in Chomsky Normal Form (CNF). Recall from Ch. 12 that grammars in CNF are restricted to rules of the form $ A \to B C $, or $ A \to w $. That is, the right-hand side of each rule must expand to either two non-terminals or to a single terminal. Recall also that restricting a grammar to CNF does not lead to any loss in expressiveness since any context-free grammar can be converted into a corresponding CNF grammar that accepts exactly the same set of strings as the original grammar. This single restriction gives rise to an extremely simple and elegant table-based parsing method.

Conversion to CNF

Let's start with the process of converting a generic CFG into one represented in CNF. Assuming we're dealing with an $ \varepsilon $-free grammar, there are three situations we need to address in any generic grammar: rules that mix terminals with non-terminals on the right-hand side, rules that have a single non-terminal on the right, and rules where the right-hand side's length is greater than two.

The remediation for rules that mix terminals and non-terminals is to simply introduce a new dummy non-terminal that covers only the original terminal. For example, a rule for an infinitive verb phrase such as $ INF-VP \rightarrow to VP $ would be replaced by the two rules $ INF-VP \rightarrow TO VP $ and $ TO \rightarrow to $.

Rules with a single non-terminal on the right are called unit productions. Unit productions are eliminated by rewriting the right-hand side of the original rules with the right-hand side of all the non-unit production rules that they ultimately lead to. More formally, if $ A \overset{*}{\to} B $ by a chain of one or more unit productions, and $ B \to \gamma $ is a non-unit production in our grammar, then we add $ A \to \gamma $ for each such rule in the grammar, and discard all the intervening unit productions. As we'll see with our toy grammar, this can lead to a substantial flattening of the grammar, and a consequent promotion of terminals to fairly high levels in the resulting trees.

Rules with right-hand sides longer than 2 are remedied through the introduction of new non-terminals that spread the longer sequences over several new productions. Formally, if we have a rule like

$$ A\to B C\gamma $$

we replace the leftmost pair of non-terminals with a new non-terminal and introduce a new production result in the following new rules.

$$ X1\to B C $$

$$ A\to X I\:\gamma $$

In the case of longer right-hand sides, we simply iterate this process until the offending rule has length 2. The choice of replacing the leftmost pair of non-terminals is purely arbitrary; any systematic scheme that results in binary rules would suffice.

In our current grammar, the rule $ S \to \text{Aux} NP\ VP $ would be replaced by the two rules $ S \to X1\ VP $ and $ X1 \to \text{Aux} NP $.

The entire conversion process can be summarized as follows:

1. Copy all conforming rules to the new grammar unchanged.

2. Convert terminals within rules to dummy non-terminals.

3. Convert unit-productions.

4. Binarize all rules and add to new grammar.

Fig. 13.8 shows the results of applying this entire conversion procedure to the $ \mathcal{L}_1 $ grammar introduced earlier on page 2. Note that this figure doesn't show the original lexical rules; since these original lexical rules are already in CNF, they all carry over unchanged to the new grammar. Fig. 13.8 does, however, show the various places where the process of eliminating unit-productions has, in effect, created new lexical rules. For example, all the original verbs have been promoted to both VPs and to Ss in the converted grammar.

CKY Recognition

With our grammar now in CNF, each non-terminal node above the part-of-speech level in a parse tree will have exactly two daughters. A simple two-dimensional matrix can be used to encode the structure of an entire tree. More specifically, for a sentence of length $n$, we will be working with the upper-triangular portion of an $(n+1) \times (n+1)$ matrix. Each cell $[i, j]$ in this matrix contains a set of non-terminals that represent all the constituents that span positions $i$ through $j$ of the input. Since our indexing scheme begins with 0, it's natural to think of the indexes as pointing at the gaps between the input words (as in 0 Book $1$ that $2$ flight $3$). It follows then that the cell that represents the entire input resides in position $[0, n]$ in the matrix.

Since our grammar is in CNF, the non-terminal entries in the table have exactly two daughters in the parse. Therefore, for each constituent represented by an entry $ [i, j] $ in the table there must be a position in the input, k, where it can be split into two parts such that $ i < k < j $. Given such a k, the first constituent $ [i, k] $ must lie to the left of entry $ [i, j] $ somewhere along row i, and the second entry $ [k, j] $ must lie beneath it, along column j.

To make this more concrete, consider the following example with its completed parse matrix shown in Fig. 13.9.

Book the flight through Houston.

The superdiagonal row in the matrix contains the parts of speech for each input word in the input. The subsequent diagonals above that superdiagonal contain constituents that cover all the spans of increasing length in the input.

$S \rightarrow NP\ VP$

$S \rightarrow Aux\ NP\ VP$

$S \rightarrow VP$

NP $\rightarrow$ Pronoun

NP $\rightarrow$ Proper-Noun

NP $\rightarrow$ Det Nominal

Nominal $\rightarrow$ Noun

Nominal $\rightarrow$ Nominal Noun

Nominal $\rightarrow$ Nominal PP

$VP \rightarrow$ Verb

$VP \rightarrow$ Verb NP

$VP \rightarrow$ Verb NP PP

$VP \rightarrow$ Verb PP

$VP \rightarrow$ VP PP

$S \rightarrow$ NNP VP

$S \rightarrow$ XI VP

$X1 \rightarrow$ Aux NP

$S \rightarrow$ book | include | prefer

$S \rightarrow$ Verb NP

$S \rightarrow$ X2 PP

$S \rightarrow$ Verb PP

$S \rightarrow$ VP PP

NP $\rightarrow$ I | she | me

NP $\rightarrow$ TWA | Houston

NP $\rightarrow$ Det Nominal

Nominal $\rightarrow$ book | flight | meal | money

Nominal $\rightarrow$ Nominal Noun

Nominal $\rightarrow$ Nominal PP

$VP \rightarrow$ book | include | prefer

$VP \rightarrow$ Verb NP

$VP \rightarrow$ Verb NP PP

$VP \rightarrow$ Verb PP

$VP \rightarrow$ VP PP

$PP \rightarrow$ Preposition NP

$PP \rightarrow$ Preposition NP

Given all this, CKY recognition is simply a matter of filling the parse table in the right way. To do this, we'll proceed in a bottom-up fashion so that at the point

where we are filling any cell $ [i, j] $, the cells containing the parts that could contribute to this entry, (i.e. the cells to the left and the cells below) have already been filled. There are several ways to do this; as the right side of Fig. 13.9 illustrates, the algorithm given in Fig. 13.10 fills the upper-triangular matrix a column at a time working from left to right. Each column is then filled from bottom to top. This scheme guarantees that at each point in time we have all the information we need (to the left, since all the columns to the left have already been filled, and below since we're filling bottom to top). It also mirrors on-line parsing since filling the columns from left to right corresponds to processing each word one at a time.

function CKY-Parse(words, grammar) returns table

for $j\leftarrow$ from 1 to LENGTH(words) do

table[j-1, j] $\leftarrow$ {A | A $\rightarrow$ words[j] $\in$ grammar}

for $i\leftarrow$ from $j-2$ downto 0 do

for $k\leftarrow i+1$ to $j-1$ do

table[i,j] $\leftarrow$ table[i,j] $\cup$

{A | A $\rightarrow$ BC $\in$ grammar,

B $\in$ table[i,k],

C $\in$ table[k,j] }

The outermost loop of the algorithm given in Fig. 13.10 iterates over the columns, the second loop iterates over the rows, from the bottom up. The purpose of the innermost loop is to range over all the places where a substring spanning $i$ to $j$ in the input might be split in two. As $k$ ranges over the places where the string can be split, the pairs of cells we consider move, in lockstep, to the right along row $i$ and down along column $j$. Fig. 13.11 illustrates the general case of filling cell $[i, j]$. At each such split, the algorithm considers whether the contents of the two cells can be combined in a way that is sanctioned by a rule in the grammar. If such a rule exists, the non-terminal on its left-hand side is entered into the table.

Fig. 13.12 shows how the five cells of column 5 of the table are filled after the word Houston is read. The arrows point out the two spans that are being used to add an entry to the table. Note that the action in cell $ [0,5] $ indicates the presence of three alternative parses for this input, one where the PP modifies the flight, one where it modifies the booking, and one that captures the second argument in the original $ VP \rightarrow Verb\ NP\ PP $ rule, now captured indirectly with the $ VP \rightarrow X2\ PP $ rule.

In fact, since our current algorithm manipulates sets of non-terminals as cell entries, it won't include multiple copies of the same non-terminal in the table; the second S and VP discovered while processing [0,5] would have no effect. We'll revisit this behavior in the next section.

CKY Parsing

The algorithm given in Fig. 13.10 is a recognizer, not a parser; for it to succeed it simply has to find an $S$ in cell $[0,N]$. To turn it into a parser capable of returning all possible parses for a given input, we'll make two simple changes to the algorithm: the first change is to augment the entries in the table so that each non-terminal is paired with pointers to the table entries from which it was derived (more or less as shown in Fig. 13.12), the second change is to permit multiple versions of the same non-terminal to be entered into the table (again as shown in Fig. 13.12.) With these changes, the completed table contains all the possible parses for a given input. Returning an arbitrary single parse consists of choosing an $S$ from cell $[0,n]$ and then recursively retrieving its component constituents from the table.

Of course, returning all the parses for a given input may incur considerable cost. As we saw earlier, there may be an exponential number of parses associated with a given input. In such cases, returning all the parses will have an unavoidable exponential

cost. Looking forward to Ch. 14, we can also think about retrieving the best parse for a given input by further augmenting the table to contain the probabilities of each entry. Retrieving the most probable parse consists of running a suitably modified version of the Viterbi algorithm from Ch. 5 over the completed parse table.

CKY in Practice

Finally, we should note that while the restriction to CNF does not pose a problem theoretically, it does pose some non-trivial problems in practice. Obviously, as things stand now, our parser isn't returning trees that are consistent with the grammar given to us by our friendly syntacticians. In addition to making our grammar developers unhappy, the conversion to CNF will complicate any syntax-driven approach to semantic analysis.

One approach to getting around these problems is to keep enough information around to transform our trees back to the original grammar as a post-processing step of the parse. This is trivial in the case of the transformation used for rules with length greater than 2. Simply deleting the new dummy non-terminals and promoting their daughters restores the original tree.

In the case of unit productions, it turns out to be more convenient to alter the basic CKY algorithm to handle them directly than it is to store the information needed to recover the correct trees. Exercise 13.3 asks you to make this change. Many of the probabilistic parsers presented in Ch. 14 use the CKY algorithm altered in just this manner. Another solution is to adopt a more complex dynamic programming solution that simply accepts arbitrary CFGs. The next section presents such an approach.