Earley parsing

Earley parsing is a parsing algorithm for arbitrary context-free grammars^[1]. Unlike LL and LR parsers, it accepts every grammar, whether ambiguous, left-recursive or right-recursive, without transformation. It reads the input once, from left to right, and after each token it records every way in which a grammar rule could be partly recognized so far: an Earley item is a rule with a dot in its right-hand side, marking how much has been recognized, and the input position where recognition of the rule began. Three operations fill in the sets of items. Prediction adds the rules of a nonterminal the parser is about to look for, scanning moves the dot past a token that matches the input, and completion, when a rule has been recognized in full, advances every item that was waiting for its nonterminal. The algorithm takes $O (n^{3})$ time in the worst case, $O (n^{2})$ on unambiguous grammars, and linear time on most grammars used for programming languages. Jay Earley developed it in his 1968 thesis and published it in 1970^[2]^[1].

§ 01

Items and sets

Let the input be $a_{1} a_{2} \dots a_{n}$ , with positions $0$ to $n$ between the tokens. The parser builds sets $S_{0}, \dots, S_{n}$ . An item $[A \to α ∙ β, i]$ in $S_{j}$ records that $α$ derives the input between positions $i$ and $j$ , and that an $A$ starting at position $i$ is consistent with the input before it:

⟺ and [A \to α ∙ β, i] \in S_{j} S \Rightarrow^{*} a_{1} \dots a_{i} A γ for some γ α \Rightarrow^{*} a_{i + 1} \dots a_{j}

Initially $S_{0}$ contains $[S \to ∙ γ, 0]$ for every rule of the start symbol, and the input is accepted if $S_{n}$ contains a completed item $[S \to γ ∙, 0]$ . The sets are filled in order by three rules^[1]:

predict: \frac{[ A \to α ∙ B β , i ] \in S _{j} B \to γ}{[ B \to ∙ γ , j ] \in S _{j}}

scan: \frac{[ A \to α ∙ a β , i ] \in S _{j} a = a _{j + 1}}{[ A \to α a ∙ β , i ] \in S _{j + 1}}

complete: \frac{[ B \to γ ∙ , k ] \in S _{j} [ A \to α ∙ B β , i ] \in S _{k}}{[ A \to α B ∙ β , i ] \in S _{j}}

Prediction is top-down: it proposes only rules that could continue what has been read. Completion is bottom-up: it combines a recognized nonterminal with the items that were waiting for it. Because an item is added to a set at most once, a left-recursive rule, which would send a recursive-descent parser into an infinite loop, is predicted once per position and then used as often as needed.

An Earley recognizer. Each set is filled by a work queue\; a hash table per set prevents duplicate items.

(* Earley's algorithm. An item (rule, dot, origin) in set j says that
   rule's right-hand side, up to the dot, derives the input from position
   origin to position j. *)
type sym = T of string | N of string
type item = { rule : int; dot : int; origin : int }
 
type grammar = { start : string; rules : (string * sym array) array }
 
let nullable g =
  let nul = Hashtbl.create 8 and changed = ref true in
  while !changed do
    changed := false;
    Array.iter (fun (a, rhs) ->
        if not (Hashtbl.mem nul a)
        && Array.for_all (function N b -> Hashtbl.mem nul b | T _ -> false) rhs
        then (Hashtbl.replace nul a (); changed := true)) g.rules
  done;
  fun a -> Hashtbl.mem nul a
 
let work = ref 0      (* items examined, including duplicates *)
 
let recognize g (input : string array) =
  let n = Array.length input in
  let nul = nullable g in
  let sets = Array.init (n + 1) (fun _ -> ref []) in
  let seen = Array.init (n + 1) (fun _ -> Hashtbl.create 64) in
  let add j it =
    incr work;
    if not (Hashtbl.mem seen.(j) it) then begin
      Hashtbl.add seen.(j) it (); sets.(j) := it :: !(sets.(j)); true end
    else false in
  let queue = Queue.create () in
  let push j it = if add j it then Queue.add it queue in
  let next_sym it = let rhs = snd g.rules.(it.rule) in
    if it.dot < Array.length rhs then Some rhs.(it.dot) else None in
  Array.iteri (fun r (a, _) -> if a = g.start then push 0 { rule = r; dot = 0; origin = 0 }) g.rules;
  for j = 0 to n do
    while not (Queue.is_empty queue) do
      let it = Queue.pop queue in
      match next_sym it with
      | Some (N b) ->
        (* predict: start every rule for b here; if b can derive the
           empty string, also move past it (Aycock and Horspool) *)
        Array.iteri (fun r (a, _) -> if a = b then push j { rule = r; dot = 0; origin = j }) g.rules;
        if nul b then push j { it with dot = it.dot + 1 }
      | Some (T t) ->
        (* scan: move past a terminal that matches the next token *)
        if j < n && input.(j) = t then ignore (add (j + 1) { it with dot = it.dot + 1 })
      | None ->
        (* complete: advance every item in the origin set waiting for this nonterminal *)
        let a = fst g.rules.(it.rule) in
        List.iter (fun w -> if next_sym w = Some (N a) then push j { w with dot = w.dot + 1 })
          (List.rev !(sets.(it.origin)))
    done;
    if j < n then List.iter (fun it -> Queue.add it queue) (List.rev !(sets.(j + 1)))
  done;
  let accepted = List.exists (fun it ->
      it.origin = 0 && fst g.rules.(it.rule) = g.start && next_sym it = None) !(sets.(n)) in
  (accepted, Array.map (fun s -> List.rev !s) sets)
 
let show_item g it =
  let a, rhs = g.rules.(it.rule) in
  let syms = Array.to_list (Array.map (function T x | N x -> x) rhs) in
  let before = List.filteri (fun i _ -> i < it.dot) syms
  and after = List.filteri (fun i _ -> i >= it.dot) syms in
  Printf.sprintf "%s → %s  (%d)" a (String.concat " " (before @ ["•"] @ after)) it.origin

§ 02

Empty rules

Nullable nonterminals, which can derive the empty string, need care. A nonterminal $B$ may be completed in $S_{j}$ with origin $j$ before all the items in $S_{j}$ waiting for $B$ have been added, and those items would then never be advanced. Implementations that follow Earley's original description closely get this case wrong. Aycock and Horspool gave the simple fix used above: when an item predicts a nullable nonterminal, the dot is also moved past it immediately^[3].

§ 03

Example

The sets for n + n * n under the ambiguous grammar E → E + E | E * E | n. The number in parentheses is the origin.

open Earley
 
(* An ambiguous grammar: E → E + E | E * E | n. *)
let ambiguous = { start = "E"; rules = [|
    "E", [| N "E"; T "+"; N "E" |];
    "E", [| N "E"; T "*"; N "E" |];
    "E", [| T "n" |] |] }

Running it.

S0
    E → • E + E  (0)
    E → • E * E  (0)
    E → • n  (0)
S1  after n
    E → n •  (0)
    E → E • + E  (0)
    E → E • * E  (0)
S2  after +
    E → E + • E  (0)
    E → • E + E  (2)
    E → • E * E  (2)
    E → • n  (2)
S3  after n
    E → n •  (2)
    E → E + E •  (0)
    E → E • + E  (2)
    E → E • * E  (2)
    E → E • + E  (0)
    E → E • * E  (0)
S4  after *
    E → E * • E  (2)
    E → E * • E  (0)
    E → • E + E  (4)
    E → • E * E  (4)
    E → • n  (4)
S5  after n
    E → n •  (4)
    E → E * E •  (2)
    E → E * E •  (0)
    E → E • + E  (4)
    E → E • * E  (4)
    E → E + E •  (0)
    E → E • + E  (2)
    E → E • * E  (2)
    E → E • + E  (0)
    E → E • * E  (0)
accepted: true

In $S_{5}$ there are two completed items for $E$ starting at 0, reached in different ways: $[E \to E * E ∙, 0]$ combines the $E$ from 0 to 3 with the $n$ from 4 to 5, and $[E \to E + E ∙, 0]$ combines the $n$ from 0 to 1 with the $E$ from 2 to 5, which is itself completed by $[E \to E * E ∙, 2]$ . These are the two parse trees of the sentence.

The spans of the completed E items for n + n * n. The whole input, E (0,5), is built either from E (0,3) and the last n, or from the first n and E (2,5): two parse trees sharing their sub-parts.

§ 04

Parse forests

The recognizer's sets contain all the information needed to recover the parse trees, but an ambiguous sentence can have exponentially many. The sum $n + n + \dots + n$ with $k$ operators under the ambiguous grammar has the Catalan number $C_{k} = \frac{1}{k + 1} (k 2 k)$ of parse trees, one for each way to bracket it.

Counting the parse trees from the sets, without building them.

open Earley
 
let ambiguous = E1_grammar.ambiguous
 
(* Count the parse trees of a grammar without empty rules, using the
   chart to find where each nonterminal can end: a completed item
   (A → γ •, i) in set m means that A derives the input from i to m. *)
let count g input sets =
  let ends = Hashtbl.create 64 in
  Array.iteri (fun m s -> List.iter (fun it ->
      let a, rhs = g.rules.(it.rule) in
      if it.dot = Array.length rhs then Hashtbl.replace ends (a, it.origin, m) ()) s) sets;
  let memo = Hashtbl.create 64 in
  let rec nt a i j =
    match Hashtbl.find_opt memo (a, i, j) with
    | Some c -> c
    | None ->
      let c = ref 0 in
      Array.iter (fun (b, rhs) -> if b = a then c := !c + seq rhs 0 i j) g.rules;
      Hashtbl.add memo (a, i, j) !c; !c
  and seq rhs k i j =
    if k = Array.length rhs then (if i = j then 1 else 0)
    else match rhs.(k) with
      | T t -> if i < j && input.(i) = t then seq rhs (k + 1) (i + 1) j else 0
      | N b ->
        (* in a grammar without empty rules every symbol covers at least
           one token, which also rules out cycles *)
        let c = ref 0 and rest = Array.length rhs - k - 1 in
        for m = i + 1 to j - rest do
          if Hashtbl.mem ends (b, i, m) then c := !c + nt b i m * seq rhs (k + 1) m j
        done; !c
  in
  nt g.start 0 (Array.length input)

Running it.

operators  parse trees
        1  1
        2  2
        3  5
        4  14
        5  42
       10  16796
       20  6564120420

A parser therefore returns a shared packed parse forest (SPPF) rather than a list of trees: a graph in which each node is a nonterminal with a span, as in the figure, and a node with several derivations has several packed children. Its size is polynomial in the length of the input. Earley's original method for extracting derivations could produce spurious ones that the grammar does not allow, as Tomita observed\; Scott showed how to build a correct SPPF during recognition^[5]^[8].

§ 05

Complexity

Each set $S_{j}$ contains items with origins $0$ to $j$ , and there are $O (∣ G ∣)$ dotted rules, so each set has $O (∣ G ∣ n)$ items and all the sets together $O (∣ G ∣ n^{2})$ . Prediction and scanning take constant time per item, but completing an item with origin $k$ examines the $O (n)$ items of $S_{k}$ , giving $O (n^{3})$ time overall. Earley showed that on unambiguous grammars each item is added in only one way, so the time is $O (n^{2})$ , and that on many grammars, including most LR( $k$ ) grammars, the sets have bounded size and the time is linear^[1].

Items created and total work, including duplicate attempts, on three grammars for the same language, as the input doubles.

open Earley
 
let left = { start = "E"; rules = [| "E", [| N "E"; T "+"; T "n" |]; "E", [| T "n" |] |] }
let right = { start = "E"; rules = [| "E", [| T "n"; T "+"; N "E" |]; "E", [| T "n" |] |] }

Running it.

grammar          tokens      items         work
left-recursive      201        304          306
left-recursive      401        604          606
left-recursive      801       1204         1206
right-recursive     201       5554         5554
right-recursive     401      21104        21104
right-recursive     801      82204        82204
ambiguous           201      20806       202912
ambiguous           401      81606      1475812
ambiguous           801     323206     11231612

The left-recursive grammar is parsed in linear time. The right-recursive one, although unambiguous and LR(1), makes the sets grow linearly, since each $S_{j}$ holds an item $[E \to n + E ∙, i]$ for every earlier $i$ , which gives quadratic time. Leo showed how to avoid this by memoizing the chains of completions that right recursion produces, which makes Earley parsing linear on every LR( $k$ ) grammar^[4]. The ambiguous grammar has a quadratic number of items and a cubic amount of work: doubling the input multiplies the work by about 7.5.

The cubic bound is not the best known for general context-free parsing. The CYK algorithm, found independently by Cocke, Kasami and Younger, also takes cubic time but requires the grammar in Chomsky normal form^[7]^[6]. Valiant reduced recognition to Boolean matrix multiplication, giving $O (n^{2.81})$ and better with faster multiplication algorithms^[9], and Lee showed a converse: substantially subcubic parsing would give fast Boolean matrix multiplication^[10]. Graham, Harrison and Ruzzo gave a variant of Earley's algorithm that combines it with the CYK table^[13].

§ 06

Uses

Generalized parsing is used where grammars are written for people rather than for parser generators, or where the language is ambiguous. Natural language processing has long used Earley and chart parsers\; Stolcke extended Earley's algorithm to probabilistic grammars, where it also computes the probability of each prefix of the input^[12]. Libraries such as Marpa, nearley and Lark offer Earley parsing for programming-language tools, where it lets a grammar be written in its natural form, left recursion and all, and reports ambiguity instead of a conflict. Generalized LR parsing, which Tomita developed for natural language, is the main alternative^[8]. For deterministic grammars, LL and LR parsers remain faster by a constant factor.

§ 07

History

Jay Earley presented the algorithm in his 1968 thesis at Carnegie Mellon University, supervised by Robert Floyd, and published it in Communications of the ACM in 1970^[2]^[1]. It followed the cubic-time CYK algorithm of Kasami and of Younger^[7]^[6] and, unlike CYK, needed no normal form and was efficient on the grammars of programming languages. Graham, Harrison and Ruzzo studied its relation to CYK in 1980^[13], Leo made it linear on all LR( $k$ ) grammars in 1991^[4], and Aycock and Horspool fixed its handling of empty rules and made it fast in practice in 2002^[3]. Scott's construction of shared packed parse forests from Earley recognizers followed in 2008^[5]. Grune and Jacobs's textbook gives a comprehensive account^[11].