[antlr-interest] setting k Value Versus Predicates

[Gokulakannan Somasundaram]

Hi Loring,
      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.

Gokul.

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.
>
> --Loring
>
>
> *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.
>
> Thanks,
> Gokul.
>
>
>