## 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ₙ

``` 1 |`EARLEYPARSER {`
|`  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`
|`}`
|` `
75 |`MAKE_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 |`}`
```