D Parsing (again)/ D grammar

[Vladimir Kazanov via Digitalmars-d]

On Thursday, 2 October 2014 at 20:28:47 UTC, Philippe Sigaud via 
Digitalmars-d
>
> No github repo. I could put it alongside Pegged, I suppose. I 
> used git
> internally, though.
>
>  I was a bit disheartened by the speed I got, so did not 
> publish nor
> announced it here.

I have a huge collection of projects I never published :-) We all 
do, I guess.

> I think, as many things in CS, that people developed parsing
> algorithms before multicores existed.
> Spawning threads or fibers for some alternatives (A | B) seems 
> nice to
> me. I got interesting results with a purely multithreaded 
> parser that
> spawned children for each choice.

No, this is not exactly what I mean. Multithreading can be 
perfectly fine in some cases, very fruitful sometimes. Say, in 
NLP, when one has to process long or highly ambiguous strings, 
and the parse tree can become huge and is of importance in 
itself... Yes. In programming language parsing this is just a 
small step towards further stages within a longer pipeline. It 
has to be fast enough to make multithreading on this step an 
overkill.

> Well, when all resulting implementations have speed problems...

Well... This is why I want to study the original implementation. 
I had read the story of red-black trees some time ago - it took a 
while to get it right, more to make it elegant.

BTW, there's one an interesting related work that probably should 
be taken as a positive example of generalized parsing: the 
Elkhound parser generator. It uses a hybrid LALR/GLR approach, 
thus achieving better performance. There's much more to it, I 
didn't go too deep into it.

> I found an article by the GLL authors explaining how they coded 
> their
> algorithm for more speed, but I couldn't wrap my head around it.

By now, I have read the original Tomita's GLR paper, Antlr ALL(*) 
paper, a few recent GLR papers, three papers on GLL and a few 
related ones . It took... A while. I sort of understand the idea, 
but still not sure about the details :-)

What's the name of the paper you read? "Modelling GLL Parser 
Implementation"?