[antlr-interest] setting k Value Versus Predicates
gokul007 at gmail.com
Mon Feb 15 02:58:44 PST 2010
Thanks a lot for the nice explanation. I have always heard LL(1) is
the fastest parser. If LL(*) happens to be so close with LL(1), that would
reduce a lot of maintenance overhead involved in creation of LL(1). Atleast
i found the grammar check and compilation times improved for grammars with
lesser value of k.
But does that mean, a LL(*) parser in ANTLR will be faster than a
equivalent Flex/Bison parser, since LL(1) and LL(*) are comparable in
performance with ANTLR? Excuse me, if i am asking too dumb questions.
On Mon, Feb 15, 2010 at 11:42 AM, Loring Craymer <lgcraymer at yahoo.com>wrote:
> With token caching and optimal pattern matching, it should be possible to
> almost eliminate any performance differential. Ter's current implementation
> does not do that--he generates DFAs that match tokens in order of appearance
> in the input stream--but the big wins from left factoring are to remove
> non-LL(*) decisions. That said, refactoring to reduce the k values of
> decisions is good practice, so temporarily setting k for this purpose can be
> helpful--just don't expect much in the way of performance improvement.
> *From:* Gokulakannan Somasundaram <gokul007 at gmail.com>
> *To:* Loring Craymer <lgcraymer at yahoo.com>
> *Cc:* Gavin Lambert <antlr at mirality.co.nz>; antlr-interest at antlr.org
> *Sent:* Sun, February 14, 2010 7:55:08 PM
> *Subject:* Re: [antlr-interest] setting k Value Versus Predicates
>> With ANTLR 3, the default is k='*' and it is best not to set k. Syntactic
>> predicates are still needed to disambiguate decisions with potentially
>> infinite lookahead (usually due to recursion or looping).
> I can't understand the statement "It is best not to set k". Say there are
> left factoring opportunities, which we won't come to know, unless it is
> thrown as an error(after setting k)...
> I think, you are assuming that the grammar cannot be left factored further.
> Or are you saying there is no difference in performance between LL(*) and
> LL(1)? Please clarify.
More information about the antlr-interest