Appendix A. Earley Parser

EARLEYPARSER {
  E₀,…,Eₙ, R, Q′, V=∅
 
  for all (S ::= α) ∈ P {
    if α ∈ ΣN add (S ::= ·α,0, null) to E₀
    if α = a₁α′ add (S ::= ·α,0, null) to Q′
  }
 
  for 0 ≤ i ≤ n {
    H=∅, R=Eᵢ, Q=Q′
    Q′=∅
 
    while R ≠ ∅ {
      remove an element, Λ say, from R
      if Λ = (B ::= α·Cβ, h, w) {
        for all (C ::= δ) ∈ P {
          if δ ∈ ΣN and (C ::= ·δ, i, null) ∉ Eᵢ {
            add (C ::= ·δ, i, null) to Eᵢ and R
          }
          if δ = aᵢ₊₁δ′ {
            add (C ::= ·δ, i, null) to Q
          }
        }
        if ((C, v) ∈ H) {
          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ᵢ₊₁β′ {
            add (B ::= αC·β, h, y) to Q
          }
        }
      }
  
      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
        }
        if h = i {
          add (D, w) to H
        }
        for all (A ::= τ·Dδ, k, z) in Eₕ {
          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ᵢ₊₁δ′ {
            add (A ::= τD·δ, k, y) to Q
          }
        }
      }
    }
  
    V=∅
    create an SPPF node v labelled (aᵢ₊₁, i, i+1)
 
    while Q ≠ ∅ {
      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ᵢ₊₁
      }
      if β = aᵢ₊₂β′ {
        add (B ::= αaᵢ₊₁·β, h, y) to Q′
      }
    }
  }
  
  if (S ::= τ·, 0, w) ∈ Eₙ return w
  else return failure
}
 
MAKE_NODE(B ::= αx·β, j, i, w, v,V) {
  if β=ϵ {
    let s =B
  } else {
    let s = (B::=αx·β)
  }
 
  if α=ϵ and β≠ϵ {
    let y=v
  } else {
    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
}