D Parsing (again)/ D grammar

[Vladimir Kazanov via Digitalmars-d]

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.