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.

  • 5
    $\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 Mar 24 '15 at 9:21
  • 1
    $\begingroup$ @Sylvain: sounds like an answer to me... $\endgroup$ – Joshua Grochow Mar 26 '15 at 3:50

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, privacy policy and cookie policy

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