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.
2
-
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$– SylvainMar 24, 2015 at 9:21
-
1$\begingroup$ @Sylvain: sounds like an answer to me... $\endgroup$– Joshua GrochowMar 26, 2015 at 3:50
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
