Appendix A. Earley Parser

This is the Earley parsing algorithm described in SPPF-Style Parsing from Earley Recognisers by Elizabeth Scott. This algorithm forms the basis of the parser in CoffeeGrinder.

The input is a grammar Γ = (N, T, S, P) and a string a₁a₂…aₙ

1EARLEYPARSER {
  E₀,…,Eₙ, R, Q′, V=∅
 
  for all (S ::= α) ∈ P {
5    if α ∈ ΣN add (S ::= ·α,0, null) to E₀
    if α = a₁α′ add (S ::= ·α,0, null) to Q′
  }
 
  for 0 ≤ i ≤ n {
10    H=∅, R=Eᵢ, Q=Q′
    Q′=∅
 
    while R ≠ ∅ {
      remove an element, Λ say, from R
15      if Λ = (B ::= α·Cβ, h, w) {
        for all (C ::= δ) ∈ P {
          if δ ∈ ΣN and (C ::= ·δ, i, null) ∉ Eᵢ {
            add (C ::= ·δ, i, null) to Eᵢ and R
          }
20          if δ = aᵢ₊₁δ′ {
            add (C ::= ·δ, i, null) to Q
          }
        }
        if ((C, v) ∈ H) {
25          let y = MAKE_NODE(B ::= αC·β, h, i, w, v, V)
          if β ∈ ΣN and (B ::= αC·β, h, y) ∉ Eᵢ {
            add (B ::= αC·β, h, y) to Eᵢ and R
          }
          if β = aᵢ₊₁β′ {
30            add (B ::= αC·β, h, y) to Q
          }
        }
      }
  
35      if Λ = (D ::= α·, h, w) {
        if w = null {
          if there is no node v ∈ V labelled (D, i, i) create one
          set w=v
          if w does not have family (ϵ) add one
40        }
        if h = i {
          add (D, w) to H
        }
        for all (A ::= τ·Dδ, k, z) in Eₕ {
45          let y = MAKE_NODE(A ::= τD·δ, k, i, z, w, V)
          if δ ∈ ΣN and (A ::= τD·δ, k, y) ∉ Eᵢ {
            add (A ::= τD·δ, k, y) to Eᵢ and R
          }
          if δ = aᵢ₊₁δ′ {
50            add (A ::= τD·δ, k, y) to Q
          }
        }
      }
    }
55  
    V=∅
    create an SPPF node v labelled (aᵢ₊₁, i, i+1)
 
    while Q ≠ ∅ {
60      remove an element, Λ = (B ::= α·ai+1β, h, w) say, from Q
      let y = MAKE_NODE(B ::= αai+1·β, h, i+1, w, v, V)
      if β ∈ ΣN {
        add (B ::= αaᵢ₊₁·β, h, y) to Eᵢ₊₁
      }
65      if β = aᵢ₊₂β′ {
        add (B ::= αaᵢ₊₁·β, h, y) to Q′
      }
    }
  }
70  
  if (S ::= τ·, 0, w) ∈ Eₙ return w
  else return failure
}
 
75MAKE_NODE(B ::= αx·β, j, i, w, v,V) {
  if β=ϵ {
    let s =B
  } else {
    let s = (B::=αx·β)
80  }
 
  if α=ϵ and β≠ϵ {
    let y=v
  } else {
85    if there is no node y ∈ V labelled (s, j, i) create one and add it to V
    if w=null and y does not have a family of children (v) add one
    if w≠null and y does not have a family of children (w, v) add one
  }
  return y
90}