Let's stop parser Hell

[Andrei Alexandrescu]

On 7/7/12 6:24 AM, Roman D. Boiko wrote:
> On Saturday, 7 July 2012 at 09:06:57 UTC, Roman D. Boiko wrote:
>> http://stackoverflow.com/questions/11373644/performance-of-parsers-peg-vs-lalr1-or-llk
>>
>
> So far it looks like LALR parsers may have lower constant factors than
> Packrat.
>
> The difference could be minimized by paying attention to parsing of
> terminal symbols, which was in my plans already. It is not necessary to
> strictly follow Packrat parsing algorithm.
>
> The benefits of Pegged, in my view, are its support of Parsing
> Expression Grammar (PEG) and compile-time evaluation. It is easily
> extensible and modifiable.

Isn't also the fact that lexing and parsing are integrated? With 
traditional LALR you need a separate tokenizer.

> When I implemented recursive-descent parser by hand in one of early
> drafts of DCT, I strongly felt the need to generalize code in a way
> which in retrospect I would call PEG-like. The structure of my
> hand-written recursive-descent parser was a one-to-one mapping to an
> implemented subset of D specification, and I considered it problematic,
> because it was needed to duplicate the same structure in the resulting AST.
>
> PEG is basically a language that describes both, the implementation of
> parser, and the language syntax. It greatly reduces implicit code
> duplication.
>
> I think that generated code can be made almost as fast as a hand-written
> parser for a particular language (probably, a few percent slower).
> Especially if that language is similar to D (context-free, with
> fine-grained hierarchical grammar). Optimizations might require to
> forget about strictly following any theoretical algorithm, but that
> should be OK.

All that sounds really encouraging. I'm really looking forward to more 
work in that area. If you stumble upon bugs that block you, let us know 
and Walter agreed he'll boost their priority.


Andrei