On Thursday, 2 October 2014 at 15:01:13 UTC, Ola Fosheim Grøstad
wrote:
Cool, GLL is the way to go IMO, but I am also looking at
Earley-parsers. What is the advantage of GLL over Earley if you
use a parser generator? I think they both are O(3) or something
like that?
They are somewhat similar in terms of asymptotic complexity on
complicated examples. Constant is better though. But there's a
nice property of all generalized parsers: for LL (for GLL) and
LR (for GLR) parts of grammars they go almost as fast as LL/LR
parsers do. On ambiguities they slow down, of course.
There are four properties I really like:
1. GLL should be faster than Earley's (even the modern
incarnations of it), but this is something I have yet to test.
2. It is fully general.
3. The automatically generated code repeats the original grammar
structure - the same way recursive decent parsers do.
4. The core parser is still that simple LL/RD parser I can
practically debug.
This comes at a price, as usual... I would not call it obvious
:-) But nobody can say that modern Earley's flavours are trivial.
From the discussion I found out that D parser is a hand-made
RD-parser with "a few tricks"(c).
I think D is close to LL(2) for the most part. But I suppose a
GLL parser could allow keywords to be used as symbol names in
most cases? That would be nice.
This is possible, I guess, the same way people do it in GLR
parsers.
