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.

  • 6
    $\begingroup$ GLR allows for deterministic parsing on portions of the grammar. See for instance Elkhound (scottmcpeak.com/elkhound), where this idea is embraced. For natural languages however, it's not that clear that GLR is any better than Earley. $\endgroup$
    – Sylvain
    Commented Mar 24, 2015 at 9:21
  • 1
    $\begingroup$ @Sylvain: sounds like an answer to me... $\endgroup$ Commented Mar 26, 2015 at 3:50

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.