Let's stop parser Hell

[Dmitry Olshansky]

On 07-Jul-12 22:29, Chad J wrote:
> On 07/07/2012 01:01 PM, Roman D. Boiko wrote:
>> On Saturday, 7 July 2012 at 16:56:06 UTC, Chad J wrote:
>>> Yeah, it's good to hear this notion reinforced. I had this suspicion
>>> that the packrat parser is not necessarily the best/fastest solution,
>>> mostly because of the large allocation that has to happen before you
>>> get O(n) performance. Thus I figured that pegged might eventually use
>>> different parsing strategies underneath it all, possibly with a lot of
>>> special-casing and clever hand-tuned and profiled optimizations. At
>>> least that's what makes sense to me.
>>
>> At the very least, we could use DFA instead of backtracking where
>> possible. This is the approach implemented in ANTLR, but I wanted to
>> introduce them before I knew about existence of the latter, simply
>> because this would likely produce the fastest parsers possible.
>
> These were my thoughts exactly, although somewhat unsubstantiated in my
> case ;)

Yup the nice thing about ANTLR is the usage of DFA. e.g. it's used for 
disambiguating alternatives that LL(k) could never do.

-- 
Dmitry Olshansky