Let's stop parser Hell

[Dmitry Olshansky]

On 08-Jul-12 14:48, Tobias Pankrath wrote:
> On Sunday, 8 July 2012 at 09:14:32 UTC, Dmitry Olshansky wrote:
>> On 08-Jul-12 13:05, Tobias Pankrath wrote:
>>>>> Yup, LL(*) is my favorite so far.
>>>>
>>>> That's Terence Parr's discovery, right? I've always liked ANTLR, so if
>>>> PEGs turn out to have issues LL(*) sounds like a promising alternative.
>>>
>>> We should also consider using GLR if LL(*) doesn't work.
>>
>> GLR ... are you serious? It still does parsing in n^3 if I'm not
>> mistaken.
>
> Since GLR can parse any CFG the upper bound is in O(n^3), but the actual
> performance seems to depend on the grammar.
>
>  From Elkhound [1]
>> It should be competitive with Bison for LALR (fragements of) grammars,
>> and degrade gracefully from there. On the scale of grammar
>> nondeterminism, from none
>> (LALR) to some to lots, "some" is the niche Elkhound is going after.
>> These goals are driven by Elkhound's primary application, the Elsa C++
>> Parser. In essence, Elkhound came about because I wanted to apply
>> automatic parsing technology to parsing C++, but found exiting systems
>> inadequate.
>
> So it seems to me that it is not worse than PEG if you have a grammar with
> reasonable many ambiguities.
>
> Performance is one thing, but you should be able to express your
> language in the underlying formalism without too many hurdles.
>

The problem is that say LL(*) can be easily tweaked in place to run 
various semantic actions as it parse the source. I think GLR is harder 
to make do anything other then "parse & say it's fine".


-- 
Dmitry Olshansky