<p>Better late than never.</p>

<p>If I understand correctly, Earley is top-down, and will spend time and memory creating Earley items for <em>every</em> production at a given S(i). This means that for natural language, in S(0) we create and check an Earley item for every possible word that starts a sentence, and there are quite a lot of those.</p>

<p>But GLR is bottom up, so assuming efficiently hashed table/state lookups, the first token selects the next transition(s) in constant time.</p>

<p>This is true specifically for natural languages, with the huge number of distinct productions. But not really meaningful for programming languages, with the very small set of productions.</p>

CC BY-SA 4.0
2018-11-01T05:12:50.353Z
2018-11-01T05:12:50.353Z
Jeff
<p>When I look at Earley parsing, it looks very elegant, and I wonder why GLR techniques become popular? Does anyone know what was wrong with Earley parsing that Tomita created GLR?
Performance? Any publications on these discussion is highly appreciated.</p>

CC BY-SA 3.0
2015-03-24T09:21:11.350Z
GLR allows for deterministic parsing on portions of the grammar.  See for instance Elkhound (http://scottmcpeak.com/elkhound/), where this idea is embraced.  For natural languages however, it's not that clear that GLR is any better than Earley.
Sylvain
CC BY-SA 3.0
2015-03-26T03:50:11.650Z
@Sylvain: sounds like an answer to me...
Joshua Grochow
<parsing>
Why Tomita created GLR and didn't use Earley?
Wickoo
# Why Tomita created GLR and didn't use Earley?

(Asked by: username_0 on 2015-03-23)

When I look at Earley parsing, it looks very elegant, and I wonder why GLR techniques become popular? Does anyone know what was wrong with Earley parsing that Tomita created GLR?
Performance? Any publications on these discussion is highly appreciated.

**Tags:** parsing
> **Comments:**
> **username_1**: GLR allows for deterministic parsing on portions of the grammar.  See for instance Elkhound (http://scottmcpeak.com/elkhound/), where this idea is embraced.  For natural languages however, it's not that clear that GLR is any better than Earley.  
> **username_2**: @Sylvain: sounds like an answer to me...  

---

## 1 answers

### Answer by username_3 on 2018-11-01. Score: 7

Better late than never.

If I understand correctly, Earley is top-down, and will spend time and memory creating Earley items for *every* production at a given S(i). This means that for natural language, in S(0) we create and check an Earley item for every possible word that starts a sentence, and there are quite a lot of those.

But GLR is bottom up, so assuming efficiently hashed table/state lookups, the first token selects the next transition(s) in constant time.

This is true specifically for natural languages, with the huge number of distinct productions. But not really meaningful for programming languages, with the very small set of productions.


---

