Let's stop parser Hell

Dmitry Olshansky dmitry.olsh at gmail.com
Sat Jul 7 12:17:28 PDT 2012


On 07-Jul-12 22:23, Andrei Alexandrescu wrote:
> 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.
>

I'll have to point out that the whole point about integrated lexing is 
moot. It's more of liability then benefit. At very least it's just 
implementation curiosity not advantage.

>> 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


-- 
Dmitry Olshansky




More information about the Digitalmars-d mailing list