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

``````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 {
}
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
}``````