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
