On Thursday, 2 October 2014 at 15:47:04 UTC, Vladimir Kazanov
wrote:
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.
What has steered you down the path of writing your own parser
generator as opposed to using an existing one such as ANTLR?
Were there properties you wanted that it didn't have, or
performance, or...?
