Bottom-up parsing with CKY

Reading

Jurafsky and Martin (2023, Ch. 18) on CKY parsing. The algorithm is due independently to Kasami and Younger (Kasami 1965; Younger 1967).

Given a grammar $G$ and an input string $\boldsymbol\sigma$, how can we determine whether $\boldsymbol\sigma\in\mathbb{L}(G)$ without trying every derivation from scratch? Recognition asks for the membership answer, while parsing asks for the derivations that establish it. The Cocke–Kasami–Younger algorithm (CKY) solves both problems for a grammar in Chomsky Normal Form.

The chart

Suppose the input contains $n$ terminals. A CKY chart has one cell $[i,j]$ for each span satisfying $0\leq i<j\leq n$. The cell records the variables that derive the substring $\sigma_i\ldots\sigma_{j-1}$.

The length-one cells follow from lexical rules:

\[A\in\operatorname{chart}[i,i+1]\quad\text{if}\quad A\rightarrow\sigma_i\in R.\]

Every longer constituent follows from a binary rule and a split point. For $i<k<j$,

\[ \frac{B\in\operatorname{chart}[i,k]\qquad C\in\operatorname{chart}[k,j]\qquad A\rightarrow BC\in R} {A\in\operatorname{chart}[i,j]}. \]

This is the CKY recurrence. It reduces a parsing problem over $[i,j]$ to two problems over shorter spans.

Why the recurrence is correct

But why does filling these local cells answer the original question? The chart is correct if the following invariant holds after all spans up to a given length have been filled:

\[ A\in\operatorname{chart}[i,j] \quad\Longleftrightarrow\quad A\Rightarrow^*\sigma_i\cdots\sigma_{j-1}. \]

We prove the two directions separately by induction on span length.

Soundness

Assume CKY places $A$ in $[i,j]$. We must show that $A$ really derives the substring over that span.

For a length-one span, CKY adds $A$ only if the grammar contains $A\rightarrow\sigma_i$. Thus, $A$ derives the required one-token substring.

Now suppose the claim holds for spans shorter than $j-i$. CKY can add $A$ to the longer span only if there are a rule $A\rightarrow BC$ and a split $k$ such that

\[B\in[i,k] \qquad\text{and}\qquad C\in[k,j].\]

By the induction hypothesis,

\[ B\Rightarrow^*\sigma_i\cdots\sigma_{k-1} \quad\text{and}\quad C\Rightarrow^*\sigma_k\cdots\sigma_{j-1}. \]

Applying $A\rightarrow BC$ and then those two derivations shows that $A$ derives their concatenation, which is exactly $\sigma_i\cdots\sigma_{j-1}$. Thus, every chart entry is sound.

Completeness

Now assume $A\Rightarrow^*\sigma_i\cdots\sigma_{j-1}$. We must show that CKY places $A$ in $[i,j]$.

If the span has length one, a CNF derivation of one terminal must use a lexical rule $A\rightarrow\sigma_i$. CKY thus adds $A$ during initialization.

For a longer span, the root of a CNF parse must use some binary rule $A\rightarrow BC$. The left subtree covers a nonempty prefix $[i,k]$, and the right subtree covers the remaining nonempty suffix $[k,j]$, for some $i<k<j$. Both spans are shorter than $[i,j]$. By the induction hypothesis, CKY enters $B$ in $[i,k]$ and $C$ in $[k,j]$. When it processes span $[i,j]$ and split $k$, it considers $A\rightarrow BC$ and adds $A$.

The invariant thus holds for every span. Applying it to $[0,n]$ gives

\[ S\in\operatorname{chart}[0,n] \quad\Longleftrightarrow\quad S\Rightarrow^*\boldsymbol\sigma. \]

Thus, the recognizer returns True exactly for nonempty strings in the grammar’s language. The implementation handles the one exceptional CNF case separately: it accepts the empty input exactly when the grammar contains $S\rightarrow\epsilon$.

Filling the chart

The recurrence determines the order of computation. We first fill every length-one cell, then consider spans of length two, three, and so on. For each span, we try every internal split point.

import sys
from collections.abc import Sequence

sys.path.insert(0, "_code")
from grammar import ContextFreeGrammar, Rule

type SpanIndices = tuple[int, int]
type CKYCell = set[str]
type CKYChart = list[list[CKYCell]]


def fill_cky_chart(
    grammar: ContextFreeGrammar,
    tokens: Sequence[str],
) -> CKYChart:
    """Return the CKY recognition chart for ``tokens``."""
    size = len(tokens)
    chart: CKYChart = [
        [set() for _ in range(size + 1)]
        for _ in range(size + 1)
    ]

    for left, token in enumerate(tokens):
        chart[left][left + 1].update(grammar.reduce(token))

    for span_length in range(2, size + 1):
        for left in range(size - span_length + 1):
            right = left + span_length
            for split in range(left + 1, right):
                for left_symbol in chart[left][split]:
                    for right_symbol in chart[split][right]:
                        chart[left][right].update(
                            grammar.reduce(left_symbol, right_symbol)
                        )

    return chart


def cky_recognize(
    grammar: ContextFreeGrammar,
    tokens: Sequence[str],
) -> bool:
    """Whether ``tokens`` belongs to the language of ``grammar``."""
    if not tokens:
        return Rule(grammar.start_variable) in grammar.rules()
    chart = fill_cky_chart(grammar, tokens)
    return grammar.start_variable in chart[0][len(tokens)]

There are $O(n^2)$ spans and $O(n)$ split points per span. The memoized ContextFreeGrammar.reduce method supplies the needed mapping from right sides to left sides, though its first lookup for a particular right side scans the rules. The chart-filling structure is cubic in the input length for a fixed grammar; the grammar-dependent factor depends on how this mapping is represented.

A hand trace

Consider the following CNF grammar and input:

\[ \begin{aligned} W &\rightarrow MM \mid MW \\ M &\rightarrow \text{un}\mid\text{lock}\mid\text{able} \end{aligned} \qquad \langle\text{un},\text{lock},\text{able}\rangle. \]

Question

Fill the upper triangle of the chart. Which cells contain $M$? Which contain $W$? Does the grammar recognize the input?

Answer

The length-one cells $[0,1]$, $[1,2]$, and $[2,3]$ each contain $M$. The cells $[0,2]$ and $[1,3]$ contain $W$ by $W\rightarrow MM$. Finally, $[0,3]$ contains $W$ by $W\rightarrow MW$ with the split at 1. Because $W$ is the start variable, the grammar recognizes the input.

From recognition to parsing

The recognition chart records only that a variable covers a span. To reconstruct a tree, we must also record why it covers that span. A backpointer stores the rule and split point that licensed an entry.

from dataclasses import dataclass


@dataclass(frozen=True, slots=True)
class CKYBackPointer:
    """The two child entries used to construct a CKY item."""

    left_symbol: str
    left_span: SpanIndices
    right_symbol: str
    right_span: SpanIndices


type CKYParseCell = dict[str, set[CKYBackPointer]]
type CKYParseChart = list[list[CKYParseCell]]

When $A$ is added to $[i,j]$ from $B\in[i,k]$, $C\in[k,j]$, and $A\rightarrow BC$, we add the corresponding CKYBackPointer to the set for $A$. Several backpointers in the same entry represent local ambiguity. Recursively following all of them from $[S,0,n]$ yields the complete parses.

CNF makes this representation possible because every nonlexical entry has exactly two children. The next parser removes that restriction by recording partial progress through rules of arbitrary length.

References

Jurafsky, Daniel, and James H. Martin. 2023. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. 3rd ed. https://web.stanford.edu/~jurafsky/slp3/old_jan23/ed3book.pdf.

Kasami, Tadao. 1965. An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages. AFCRL-65-758. Air Force Cambridge Research Labs.

Younger, Daniel H. 1967. “Recognition and Parsing of Context-Free Languages in Time $n^3$.” Information and Control 10 (2): 189–208. https://doi.org/10.1016/S0019-9958(67)80007-X.

--- title: Bottom-up parsing with CKY bibliography: ../references.bib jupyter: python3 --- ::: {.callout-tip} ## Reading @jurafsky_speech_2023[Ch. 18] on CKY parsing. The algorithm is due independently to Kasami and Younger [@kasami_efficient_1965; @younger_recognition_1967]. ::: Given a grammar $G$ and an input string $\boldsymbol\sigma$, how can we determine whether $\boldsymbol\sigma\in\mathbb{L}(G)$ without trying every derivation from scratch? Recognition asks for the membership answer, while parsing asks for the derivations that establish it. The **Cocke–Kasami–Younger algorithm** (CKY) solves both problems for a grammar in Chomsky Normal Form. ## The chart Suppose the input contains $n$ terminals. A CKY chart has one cell $[i,j]$ for each span satisfying $0\leq i<j\leq n$. The cell records the variables that derive the substring $\sigma_i\ldots\sigma_{j-1}$. The length-one cells follow from lexical rules: $$A\in\operatorname{chart}[i,i+1]\quad\text{if}\quad A\rightarrow\sigma_i\in R.$$ Every longer constituent follows from a binary rule and a split point. For $i<k<j$, $$ \frac{B\in\operatorname{chart}[i,k]\qquad C\in\operatorname{chart}[k,j]\qquad A\rightarrow BC\in R} {A\in\operatorname{chart}[i,j]}. $$ This is the **CKY recurrence**. It reduces a parsing problem over $[i,j]$ to two problems over shorter spans. ## Why the recurrence is correct But why does filling these local cells answer the original question? The chart is correct if the following invariant holds after all spans up to a given length have been filled: $$ A\in\operatorname{chart}[i,j] \quad\Longleftrightarrow\quad A\Rightarrow^*\sigma_i\cdots\sigma_{j-1}. $$ We prove the two directions separately by induction on span length. ### Soundness Assume CKY places $A$ in $[i,j]$. We must show that $A$ really derives the substring over that span. For a length-one span, CKY adds $A$ only if the grammar contains $A\rightarrow\sigma_i$. Thus, $A$ derives the required one-token substring. Now suppose the claim holds for spans shorter than $j-i$. CKY can add $A$ to the longer span only if there are a rule $A\rightarrow BC$ and a split $k$ such that $$B\in[i,k] \qquad\text{and}\qquad C\in[k,j].$$ By the induction hypothesis, $$ B\Rightarrow^*\sigma_i\cdots\sigma_{k-1} \quad\text{and}\quad C\Rightarrow^*\sigma_k\cdots\sigma_{j-1}. $$ Applying $A\rightarrow BC$ and then those two derivations shows that $A$ derives their concatenation, which is exactly $\sigma_i\cdots\sigma_{j-1}$. Thus, every chart entry is sound. ### Completeness Now assume $A\Rightarrow^*\sigma_i\cdots\sigma_{j-1}$. We must show that CKY places $A$ in $[i,j]$. If the span has length one, a CNF derivation of one terminal must use a lexical rule $A\rightarrow\sigma_i$. CKY thus adds $A$ during initialization. For a longer span, the root of a CNF parse must use some binary rule $A\rightarrow BC$. The left subtree covers a nonempty prefix $[i,k]$, and the right subtree covers the remaining nonempty suffix $[k,j]$, for some $i<k<j$. Both spans are shorter than $[i,j]$. By the induction hypothesis, CKY enters $B$ in $[i,k]$ and $C$ in $[k,j]$. When it processes span $[i,j]$ and split $k$, it considers $A\rightarrow BC$ and adds $A$. The invariant thus holds for every span. Applying it to $[0,n]$ gives $$ S\in\operatorname{chart}[0,n] \quad\Longleftrightarrow\quad S\Rightarrow^*\boldsymbol\sigma. $$ Thus, the recognizer returns `True` exactly for nonempty strings in the grammar's language. The implementation handles the one exceptional CNF case separately: it accepts the empty input exactly when the grammar contains $S\rightarrow\epsilon$. ## Filling the chart The recurrence determines the order of computation. We first fill every length-one cell, then consider spans of length two, three, and so on. For each span, we try every internal split point. ```{python} import sys from collections.abc import Sequence sys.path.insert(0, "_code") from grammar import ContextFreeGrammar, Rule type SpanIndices = tuple[int, int] type CKYCell = set[str] type CKYChart = list[list[CKYCell]] def fill_cky_chart( grammar: ContextFreeGrammar, tokens: Sequence[str], ) -> CKYChart: """Return the CKY recognition chart for ``tokens``.""" size = len(tokens) chart: CKYChart = [ [set() for _ in range(size + 1)] for _ in range(size + 1) ] for left, token in enumerate(tokens): chart[left][left + 1].update(grammar.reduce(token)) for span_length in range(2, size + 1): for left in range(size - span_length + 1): right = left + span_length for split in range(left + 1, right): for left_symbol in chart[left][split]: for right_symbol in chart[split][right]: chart[left][right].update( grammar.reduce(left_symbol, right_symbol) ) return chart def cky_recognize( grammar: ContextFreeGrammar, tokens: Sequence[str], ) -> bool: """Whether ``tokens`` belongs to the language of ``grammar``.""" if not tokens: return Rule(grammar.start_variable) in grammar.rules() chart = fill_cky_chart(grammar, tokens) return grammar.start_variable in chart[0][len(tokens)] ``` There are $O(n^2)$ spans and $O(n)$ split points per span. The memoized `ContextFreeGrammar.reduce` method supplies the needed mapping from right sides to left sides, though its first lookup for a particular right side scans the rules. The chart-filling structure is cubic in the input length for a fixed grammar; the grammar-dependent factor depends on how this mapping is represented. ## A hand trace Consider the following CNF grammar and input: $$ \begin{aligned} W &\rightarrow MM \mid MW \\ M &\rightarrow \text{un}\mid\text{lock}\mid\text{able} \end{aligned} \qquad \langle\text{un},\text{lock},\text{able}\rangle. $$ ::: {.callout-caution} ## Question Fill the upper triangle of the chart. Which cells contain $M$? Which contain $W$? Does the grammar recognize the input? ::: ::: {.callout-tip collapse=true} ## Answer The length-one cells $[0,1]$, $[1,2]$, and $[2,3]$ each contain $M$. The cells $[0,2]$ and $[1,3]$ contain $W$ by $W\rightarrow MM$. Finally, $[0,3]$ contains $W$ by $W\rightarrow MW$ with the split at 1. Because $W$ is the start variable, the grammar recognizes the input. ::: ## From recognition to parsing The recognition chart records only that a variable covers a span. To reconstruct a tree, we must also record *why* it covers that span. A **backpointer** stores the rule and split point that licensed an entry. ```{python} from dataclasses import dataclass @dataclass(frozen=True, slots=True) class CKYBackPointer: """The two child entries used to construct a CKY item.""" left_symbol: str left_span: SpanIndices right_symbol: str right_span: SpanIndices type CKYParseCell = dict[str, set[CKYBackPointer]] type CKYParseChart = list[list[CKYParseCell]] ``` When $A$ is added to $[i,j]$ from $B\in[i,k]$, $C\in[k,j]$, and $A\rightarrow BC$, we add the corresponding `CKYBackPointer` to the set for $A$. Several backpointers in the same entry represent local ambiguity. Recursively following all of them from $[S,0,n]$ yields the complete parses. CNF makes this representation possible because every nonlexical entry has exactly two children. The next parser removes that restriction by recording partial progress through rules of arbitrary length.