Let's stop parser Hell

[Roman D. Boiko]

On Sunday, 8 July 2012 at 21:03:41 UTC, Jonathan M Davis wrote:
> It's been too long since I was actively working on parsers to 
> give any details, but it is my understanding that because a 
> hand-written parser is optimized for a specific grammar, it's 
> going to be faster.

My aim is to find out any potential bottlenecks and ensure that 
those are possible to get rid of. So, let's try.

I believe it would not hurt generality or quality of a parser 
generator if it contained sews for inserting custom (optimized) 
code where necessary, including those needed to take advantage of 
some particular aspects of D grammar. Thus I claim that 
optimization for D grammar is possible.

> Also, look at dmd and dmc vs other compilers. They use 
> hand-written parsers and are generally much faster than their 
> competitors.

Due to which particular design or implementation decisions? Would 
it be possible to name a few which are relevant in this context?

> One thing to remember about hand-written parsers vs generative 
> ones though is that they usually are completely different in 
> terms of the type of parser that you write (e.g. hand-written 
> parsers are generally recursive-decent parser whereas 
> generative ones usually use bottom-up parsers).

So far discussion goes in favor of LL(*) parser like ANTLR, which 
is top-down recursive-descent. Either Pegged will be optimized 
with LL(*) algorithms, or a new parser generator created.