Earley parsing

Earley’s algorithm reads the sentence from left to right and keeps, for each position k, a set of items: rules with a dot showing how much of the right-hand side has been found, and the position where the constituent started. It predicts top-down like a recursive-descent parser, but stores every partial result once, so nothing is ever redone and no choice ever has to be undone.

Items and the chart

An item A → α • β [i] in the set Sₖ says: an A that starts at position i is being built; α has already been found over words i+1 … k, and β is still needed. Item sets S₀ … Sₙ form the chart. S₀ starts with γ → • S [0], where γ is a new start category.

Predict: For A → α • B β [i] in Sₖ, add B → • δ [k] to Sₖ for every rule B → δ.
Scan: For A → α • X β [i] in Sₖ where X is a part of speech of word k+1, add X → wₖ₊₁ • [k] to Sₖ₊₁.
Complete: For a finished item B → δ • [j] in Sₖ, find every item A → α • B β [i] in Sⱼ and add A → α B • β [i] to Sₖ.
Accept: The sentence is grammatical if γ → S • [0] is in Sₙ.

S0 = { γ → • S [0] }
for k = 0 … n:
    for each item A → α • β [i] in Sk   (including items added during the loop):
        if β = B β' and B has rules:  PREDICT   add B → • δ [k] to Sk, for each rule B → δ
        if β = X β' and X → w(k+1):   SCAN      add X → w(k+1) • [k] to Sk+1
        if β is empty:                COMPLETE  for each C → δ • A δ' [h] in Si:
                                                    add C → δ A • δ' [h] to Sk
accept iff γ → S • [0] ∈ Sn

An item is added to a set only once. If it can be obtained in another way, the new derivation is stored with the existing item (packing): this is how the chart represents ambiguity without multiplying work, and how all the trees can be read off at the end by following the stored derivations.

Properties

Any context-free grammar, including left-recursive ones: prediction of an item already in the set adds nothing, so NP → • NP PP cannot loop. ε-rules need a small correction (Aycock & Horspool 2002).
O(n³) time in general, O(n²) for unambiguous grammars and linear time for a large class of grammars (Earley 1970). Graham, Harrison & Ruzzo (1980) relate it to CKY.
It is a recogniser plus a packed forest: the number of parses may be exponential, but the chart stays polynomial.
Its probabilistic version computes prefix probabilities word by word (Stolcke 1995), used to model reading difficulty as surprisal (Hale 2001).

In this tool

Each step adds one item (or packs a derivation into an existing one). The chart shows the sets S₀ … Sₙ, with the current item highlighted; [i] is the item’s origin, ×2 marks an item with two derivations. The tree is the item read as a partial tree: the daughters already found, then dashed boxes for the categories after the dot.

Try it on an example → Left recursion in the chart →

References

Earley, J. (1970). An efficient context-free parsing algorithm. Communications of the ACM, 13(2), 94–102.
Aycock, J. & Horspool, R. N. (2002). Practical Earley parsing. The Computer Journal, 45(6), 620–630.
Graham, S. L., Harrison, M. A. & Ruzzo, W. L. (1980). An improved context-free recognizer. ACM Transactions on Programming Languages and Systems, 2(3), 415–462.
Kay, M. (1980). Algorithm Schemata and Data Structures in Syntactic Processing. Technical Report CSL-80-12, Xerox PARC. Reprinted in B. J. Grosz, K. Sparck Jones & B. L. Webber (Eds.), Readings in Natural Language Processing (1986), Morgan Kaufmann.
Shieber, S. M., Schabes, Y. & Pereira, F. C. N. (1995). Principles and implementation of deductive parsing. Journal of Logic Programming, 24(1–2), 3–36.
Stolcke, A. (1995). An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2), 165–201.
Hale, J. (2001). A probabilistic Earley parser as a psycholinguistic model. In Proceedings of the Second Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL 2001). aclanthology.org/N01-1021
Jurafsky, D. & Martin, J. H. (2009). Speech and Language Processing (2nd ed.). Upper Saddle River, NJ: Pearson Prentice Hall. Chapter 13, “Syntactic Parsing”.
Jurafsky, D. & Martin, J. H. Speech and Language Processing (3rd ed. draft), chapter on context-free grammars and constituency parsing. Online at web.stanford.edu/~jurafsky/slp3.
Grune, D. & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.). New York: Springer.