Top-down parsing with Earley

Reading

Earley (1970) and Jurafsky and Martin (2023, Ch. 18) on Earley parsing.

CKY begins with the terminals and builds larger constituents. But what if we do not want to convert the grammar to Chomsky Normal Form first? The Earley algorithm combines bottom-up evidence with top-down predictions about which rules may apply, and it operates directly on rules of arbitrary length.

Dotted rules

An Earley item has the form

\[[A\rightarrow\alpha\bullet\beta,i,j].\]

It states that the parser began expanding $A$ at position $i$, has recognized $\alpha$ through position $j$, and still expects $\beta$. The dot records progress through the rule.

For instance,

\[[N\rightarrow \text{Prefix}\;\bullet\;\text{Adjective}\;\text{Suffix},0,1]\]

states that a Prefix spanning $[0,1]$ has been recognized and that an Adjective followed by a Suffix is still required.

We can represent the item directly. Python’s typing.Self type marks advance as returning an instance of the same class.

from dataclasses import dataclass
from typing import Self


@dataclass(frozen=True, slots=True)
class EarleyItem:
    """A dotted CFG rule over one input span."""

    left_side: str
    right_side: tuple[str, ...]
    dot: int
    origin: int
    position: int

    @property
    def is_complete(self) -> bool:
        """Whether the dot follows the entire right side."""
        return self.dot == len(self.right_side)

    @property
    def next_symbol(self) -> str | None:
        """The symbol after the dot, if one remains."""
        if self.is_complete:
            return None
        return self.right_side[self.dot]

    def advance(self, position: int) -> Self:
        """Return an item with the dot advanced by one symbol."""
        if self.is_complete:
            raise ValueError("cannot advance a complete item")
        return type(self)(
            left_side=self.left_side,
            right_side=self.right_side,
            dot=self.dot + 1,
            origin=self.origin,
            position=position,
        )

Predict, scan, and complete

Earley parsing repeatedly applies three operations.

Predict expands a variable after the dot. If $B$ is next, then every rule with $B$ on the left may begin at the current position.

\[ \frac{[A\rightarrow\alpha\bullet B\beta,i,j]} {[B\rightarrow\bullet\gamma,j,j]} \quad B\rightarrow\gamma\in R \]

Scan matches a terminal after the dot against the next input symbol.

\[ \frac{[A\rightarrow\alpha\bullet a\beta,i,j]} {[A\rightarrow\alpha a\bullet\beta,i,j+1]} \quad a=\sigma_j \]

Complete uses a finished constituent to advance every item that was waiting for it at the constituent’s origin.

\[ \frac{[A\rightarrow\alpha\bullet B\beta,i,j] \qquad[B\rightarrow\gamma\bullet,j,k]} {[A\rightarrow\alpha B\bullet\beta,i,k]} \]

Prediction and completion add items to the same chart position. Scanning is the only operation that consumes input.

Why the three operations are sufficient

Why are prediction, scanning, and completion enough? An Earley item has two linked claims. First, its recognized-prefix claim is

\[ \alpha\Rightarrow^*\sigma_i\cdots\sigma_{j-1}. \]

Second, its context claim is that the parser reached this occurrence of $A$ from the artificial start item through predictions and completed constituents. The first claim says that the material left of the dot matches the stated input span. The second prevents the parser from accepting a complete rule that was never licensed by a possible start-symbol derivation.

Soundness

We check the seed and then each operation.

The seed $[S'\rightarrow\bullet S,0,0]$ has an empty recognized prefix and is the root of the context relation.
Predict adds $[B\rightarrow\bullet\gamma,j,j]$. Its recognized prefix is empty, so it derives the empty substring $[j,j]$. The waiting item supplies its context.
Scan advances over terminal $a$ only when $a=\sigma_j$. If $\alpha$ derived the substring over $[i,j]$, then $\alpha a$ derives the substring over $[i,j+1]$. The item’s context does not change.
Complete combines a waiting item whose recognized prefix spans $[i,j]$ with a completed $B$ spanning $[j,k]$. Their derivations concatenate, so $\alpha B$ derives the substring over $[i,k]$. The completed child was predicted in a licensed context, so advancing the waiting item also preserves the context claim.

Every inferred item thus satisfies both claims. If the goal $[S'\rightarrow S\bullet,0,n]$ is present, its recognized-prefix claim gives $S\Rightarrow^*\sigma_0\cdots\sigma_{n-1}$. Acceptance is sound.

Completeness

Suppose instead that the grammar has a parse tree for the input. We show that Earley can trace that tree from left to right.

The seed waits for the root $S$, so prediction adds the rule used at the root of the chosen tree with its dot at the beginning. Consider any predicted rule $A\rightarrow X_1\cdots X_m$ whose tree node begins at position $i$. We prove by induction on $r$ that Earley constructs the item with the dot after $X_r$ at the position where the first $r$ children end.

The case $r=0$ is the predicted item. For the next child, there are two cases.

If $X_{r+1}$ is a terminal, the parse tree says that it is the next input token. Scan thus advances the dot.
If $X_{r+1}$ is a nonterminal, predict adds the rule used by that child. Applying the same argument recursively to the child eventually produces its complete item. Complete then advances the parent dot across $X_{r+1}$.

After all $m$ children have been handled, the item for $A$ is complete over exactly the span of its parse-tree node. Applying this reasoning upward from the leaves completes the root item $[S\rightarrow\gamma\bullet,0,n]$, which in turn completes the artificial start item. Thus, every grammatical input reaches the goal.

Soundness and completeness together establish that the three operations recognize exactly the CFG language. Epsilon rules cause a child to begin and end at the same position; the repeated prediction-completion closure at each chart position handles that case without changing the argument.

Filling the chart

We add an artificial rule $S'\rightarrow S$ and seed chart position 0 with $[S'\rightarrow\bullet S,0,0]$. At each position, we close the item set under prediction and completion, then scan matching terminals into the next position.

import sys
from collections.abc import Sequence

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

type EarleyChart = list[set[EarleyItem]]


def earley_start_symbol(grammar: ContextFreeGrammar) -> str:
    """Return an artificial start symbol absent from ``grammar``."""
    symbol = "EARLEY_START"
    while symbol in grammar.variables or symbol in grammar.alphabet:
        symbol += "_"
    return symbol


def fill_earley_chart(
    grammar: ContextFreeGrammar,
    tokens: Sequence[str],
) -> EarleyChart:
    """Return the Earley recognition chart for ``tokens``."""
    chart: EarleyChart = [set() for _ in range(len(tokens) + 1)]
    goal_symbol = earley_start_symbol(grammar)

    start_item = EarleyItem(
        left_side=goal_symbol,
        right_side=(grammar.start_variable,),
        dot=0,
        origin=0,
        position=0,
    )
    chart[0].add(start_item)

    for position in range(len(tokens) + 1):
        changed = True
        while changed:
            changed = False
            for item in tuple(chart[position]):
                symbol = item.next_symbol

                if symbol in grammar.variables:
                    predicted = {
                        EarleyItem(
                            left_side=rule.left_side,
                            right_side=rule.right_side,
                            dot=0,
                            origin=position,
                            position=position,
                        )
                        for rule in grammar.rules(symbol)
                    }
                    old_size = len(chart[position])
                    chart[position].update(predicted)
                    changed |= len(chart[position]) > old_size

                elif item.is_complete:
                    completed = {
                        waiting.advance(position)
                        for waiting in chart[item.origin]
                        if waiting.next_symbol == item.left_side
                    }
                    old_size = len(chart[position])
                    chart[position].update(completed)
                    changed |= len(chart[position]) > old_size

        if position == len(tokens):
            continue

        for item in chart[position]:
            if item.next_symbol == tokens[position]:
                chart[position + 1].add(item.advance(position + 1))

    return chart


def earley_recognize(
    grammar: ContextFreeGrammar,
    tokens: Sequence[str],
) -> bool:
    """Whether ``tokens`` belongs to the language of ``grammar``."""
    chart = fill_earley_chart(grammar, tokens)
    goal = EarleyItem(
        left_side=earley_start_symbol(grammar),
        right_side=(grammar.start_variable,),
        dot=1,
        origin=0,
        position=len(tokens),
    )
    return goal in chart[-1]

The recognizer above keeps sets of items, so a left-recursive or epsilon-producing grammar cannot add the same item indefinitely. An agenda-based Earley recognizer with suitable indexes has cubic worst-case time in the input length for a fixed grammar, and particular grammar classes permit tighter bounds. The compact implementation above repeatedly scans item sets to compute closure, so it is intended to exhibit the inference rules rather than to realize the tight cubic bound.

Question

Why can Earley parse a rule such as $N\rightarrow\text{Prefix}\;\text{Adjective}\;\text{Suffix}$ without first binarizing it?

Answer

The dot can occupy each of the four positions in that rule. Each successful prediction, scan, or completion advances it by one symbol, so the item records partial progress through a right side of any finite length.

Recovering trees and predictions

As with CKY, recognition items must be augmented with backpointers to recover parse trees. A completed Earley item records which waiting item and which completed child licensed it. Following those backpointers reconstructs the derivation without enumerating trees during chart filling.

An unfinished item also has predictive content. If chart position $j$ contains an item whose next symbol is a part of speech, the grammar predicts the words licensed by that part of speech at position $j$. This observation underlies the next-word prediction task in the homework: Earley items describe not only analyses of the observed prefix but also the continuations that the grammar still permits.

References

Earley, Jay. 1970. “An Efficient Context-Free Parsing Algorithm.” Communications of the ACM 13 (2): 94–102. https://doi.org/10.1145/362007.362035.

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.

--- title: Top-down parsing with Earley bibliography: ../references.bib jupyter: python3 --- ::: {.callout-tip} ## Reading @earley_efficient_1970 and @jurafsky_speech_2023[Ch. 18] on Earley parsing. ::: CKY begins with the terminals and builds larger constituents. But what if we do not want to convert the grammar to Chomsky Normal Form first? The **Earley algorithm** combines bottom-up evidence with top-down predictions about which rules may apply, and it operates directly on rules of arbitrary length. ## Dotted rules An Earley item has the form $$[A\rightarrow\alpha\bullet\beta,i,j].$$ It states that the parser began expanding $A$ at position $i$, has recognized $\alpha$ through position $j$, and still expects $\beta$. The dot records progress through the rule. For instance, $$[N\rightarrow \text{Prefix}\;\bullet\;\text{Adjective}\;\text{Suffix},0,1]$$ states that a `Prefix` spanning $[0,1]$ has been recognized and that an `Adjective` followed by a `Suffix` is still required. We can represent the item directly. Python's `typing.Self` type marks `advance` as returning an instance of the same class. ```{python} from dataclasses import dataclass from typing import Self @dataclass(frozen=True, slots=True) class EarleyItem: """A dotted CFG rule over one input span.""" left_side: str right_side: tuple[str, ...] dot: int origin: int position: int @property def is_complete(self) -> bool: """Whether the dot follows the entire right side.""" return self.dot == len(self.right_side) @property def next_symbol(self) -> str | None: """The symbol after the dot, if one remains.""" if self.is_complete: return None return self.right_side[self.dot] def advance(self, position: int) -> Self: """Return an item with the dot advanced by one symbol.""" if self.is_complete: raise ValueError("cannot advance a complete item") return type(self)( left_side=self.left_side, right_side=self.right_side, dot=self.dot + 1, origin=self.origin, position=position, ) ``` ## Predict, scan, and complete Earley parsing repeatedly applies three operations. **Predict** expands a variable after the dot. If $B$ is next, then every rule with $B$ on the left may begin at the current position. $$ \frac{[A\rightarrow\alpha\bullet B\beta,i,j]} {[B\rightarrow\bullet\gamma,j,j]} \quad B\rightarrow\gamma\in R $$ **Scan** matches a terminal after the dot against the next input symbol. $$ \frac{[A\rightarrow\alpha\bullet a\beta,i,j]} {[A\rightarrow\alpha a\bullet\beta,i,j+1]} \quad a=\sigma_j $$ **Complete** uses a finished constituent to advance every item that was waiting for it at the constituent's origin. $$ \frac{[A\rightarrow\alpha\bullet B\beta,i,j] \qquad[B\rightarrow\gamma\bullet,j,k]} {[A\rightarrow\alpha B\bullet\beta,i,k]} $$ Prediction and completion add items to the same chart position. Scanning is the only operation that consumes input. ## Why the three operations are sufficient Why are prediction, scanning, and completion enough? An Earley item has two linked claims. First, its recognized-prefix claim is $$ \alpha\Rightarrow^*\sigma_i\cdots\sigma_{j-1}. $$ Second, its context claim is that the parser reached this occurrence of $A$ from the artificial start item through predictions and completed constituents. The first claim says that the material left of the dot matches the stated input span. The second prevents the parser from accepting a complete rule that was never licensed by a possible start-symbol derivation. ### Soundness We check the seed and then each operation. 1. The seed $[S'\rightarrow\bullet S,0,0]$ has an empty recognized prefix and is the root of the context relation. 2. **Predict** adds $[B\rightarrow\bullet\gamma,j,j]$. Its recognized prefix is empty, so it derives the empty substring $[j,j]$. The waiting item supplies its context. 3. **Scan** advances over terminal $a$ only when $a=\sigma_j$. If $\alpha$ derived the substring over $[i,j]$, then $\alpha a$ derives the substring over $[i,j+1]$. The item's context does not change. 4. **Complete** combines a waiting item whose recognized prefix spans $[i,j]$ with a completed $B$ spanning $[j,k]$. Their derivations concatenate, so $\alpha B$ derives the substring over $[i,k]$. The completed child was predicted in a licensed context, so advancing the waiting item also preserves the context claim. Every inferred item thus satisfies both claims. If the goal $[S'\rightarrow S\bullet,0,n]$ is present, its recognized-prefix claim gives $S\Rightarrow^*\sigma_0\cdots\sigma_{n-1}$. Acceptance is sound. ### Completeness Suppose instead that the grammar has a parse tree for the input. We show that Earley can trace that tree from left to right. The seed waits for the root $S$, so prediction adds the rule used at the root of the chosen tree with its dot at the beginning. Consider any predicted rule $A\rightarrow X_1\cdots X_m$ whose tree node begins at position $i$. We prove by induction on $r$ that Earley constructs the item with the dot after $X_r$ at the position where the first $r$ children end. The case $r=0$ is the predicted item. For the next child, there are two cases. - If $X_{r+1}$ is a terminal, the parse tree says that it is the next input token. Scan thus advances the dot. - If $X_{r+1}$ is a nonterminal, predict adds the rule used by that child. Applying the same argument recursively to the child eventually produces its complete item. Complete then advances the parent dot across $X_{r+1}$. After all $m$ children have been handled, the item for $A$ is complete over exactly the span of its parse-tree node. Applying this reasoning upward from the leaves completes the root item $[S\rightarrow\gamma\bullet,0,n]$, which in turn completes the artificial start item. Thus, every grammatical input reaches the goal. Soundness and completeness together establish that the three operations recognize exactly the CFG language. Epsilon rules cause a child to begin and end at the same position; the repeated prediction-completion closure at each chart position handles that case without changing the argument. ## Filling the chart We add an artificial rule $S'\rightarrow S$ and seed chart position 0 with $[S'\rightarrow\bullet S,0,0]$. At each position, we close the item set under prediction and completion, then scan matching terminals into the next position. ```{python} import sys from collections.abc import Sequence sys.path.insert(0, "_code") from grammar import ContextFreeGrammar type EarleyChart = list[set[EarleyItem]] def earley_start_symbol(grammar: ContextFreeGrammar) -> str: """Return an artificial start symbol absent from ``grammar``.""" symbol = "EARLEY_START" while symbol in grammar.variables or symbol in grammar.alphabet: symbol += "_" return symbol def fill_earley_chart( grammar: ContextFreeGrammar, tokens: Sequence[str], ) -> EarleyChart: """Return the Earley recognition chart for ``tokens``.""" chart: EarleyChart = [set() for _ in range(len(tokens) + 1)] goal_symbol = earley_start_symbol(grammar) start_item = EarleyItem( left_side=goal_symbol, right_side=(grammar.start_variable,), dot=0, origin=0, position=0, ) chart[0].add(start_item) for position in range(len(tokens) + 1): changed = True while changed: changed = False for item in tuple(chart[position]): symbol = item.next_symbol if symbol in grammar.variables: predicted = { EarleyItem( left_side=rule.left_side, right_side=rule.right_side, dot=0, origin=position, position=position, ) for rule in grammar.rules(symbol) } old_size = len(chart[position]) chart[position].update(predicted) changed |= len(chart[position]) > old_size elif item.is_complete: completed = { waiting.advance(position) for waiting in chart[item.origin] if waiting.next_symbol == item.left_side } old_size = len(chart[position]) chart[position].update(completed) changed |= len(chart[position]) > old_size if position == len(tokens): continue for item in chart[position]: if item.next_symbol == tokens[position]: chart[position + 1].add(item.advance(position + 1)) return chart def earley_recognize( grammar: ContextFreeGrammar, tokens: Sequence[str], ) -> bool: """Whether ``tokens`` belongs to the language of ``grammar``.""" chart = fill_earley_chart(grammar, tokens) goal = EarleyItem( left_side=earley_start_symbol(grammar), right_side=(grammar.start_variable,), dot=1, origin=0, position=len(tokens), ) return goal in chart[-1] ``` The recognizer above keeps sets of items, so a left-recursive or epsilon-producing grammar cannot add the same item indefinitely. An agenda-based Earley recognizer with suitable indexes has cubic worst-case time in the input length for a fixed grammar, and particular grammar classes permit tighter bounds. The compact implementation above repeatedly scans item sets to compute closure, so it is intended to exhibit the inference rules rather than to realize the tight cubic bound. ::: {.callout-caution} ## Question Why can Earley parse a rule such as $N\rightarrow\text{Prefix}\;\text{Adjective}\;\text{Suffix}$ without first binarizing it? ::: ::: {.callout-tip collapse=true} ## Answer The dot can occupy each of the four positions in that rule. Each successful prediction, scan, or completion advances it by one symbol, so the item records partial progress through a right side of any finite length. ::: ## Recovering trees and predictions As with CKY, recognition items must be augmented with backpointers to recover parse trees. A completed Earley item records which waiting item and which completed child licensed it. Following those backpointers reconstructs the derivation without enumerating trees during chart filling. An unfinished item also has predictive content. If chart position $j$ contains an item whose next symbol is a part of speech, the grammar predicts the words licensed by that part of speech at position $j$. This observation underlies the next-word prediction task in the homework: Earley items describe not only analyses of the observed prefix but also the continuations that the grammar still permits.