[antlr-interest] LL(k)

[Mark Wright]

> Hi,
> 
>  
> 
> Could anybody give me a clue what the consequences are of specifying
> a k value in the options section of an ANTLR grammar, performance
> wise?

Hello Patrick,

I think the answer depends on whether I read ahead to where you
you mention semantic predicates or not, and you didn't actually
say what type of semantic predicate, so from the context of
the question I am assuming you mean dis-ambiguating semantic
predicates:

- without dis-ambiguating semantic predicates:
A: Either k is * or high enough and the grammar simple enough
for ANTLR to figure out the grammar, in which case the performance
should be good.  Or otherwise, the performance is likely to be
worse as its then necessary to resort to other approaches to
parse the grammar.

- with dis-ambiguating semantic predicates:
A: By reducing k to force the dis-ambiguating semantic predicates to be
called, the performance is likely to be slower than a grammar that
does not use dis-ambiguating semantic predicates.  The
dis-ambiguating semantic predicates are likely to be called
repetitively, so you may wish to cache the results.  I posted a
little program to this list to demonstrate that earlier:

http://www.antlr.org/pipermail/antlr-interest/2008-February/026385.html

> And what will it do to the recognition power of the generated
> parser?

- without dis-ambiguating semantic predicates:
ANTLR is either going to be able to generate a parser, or not.

- with dis-ambiguating semantic predicates:
ANTLR can handle very complex grammars with dis-ambiguating semantic
predicates.

> I'm defining a grammar but I'm having an hard time with the prediction
> DFAs in my parser when I'm using LL(*). These don't seem to consider
> semantical predicates in their prediction. When I specify a k=2 value
> all works fine.
> 
>  
> 
> Gr, patrick.

You could add logging to the dis-ambiguating semantic predicates as
demonstrated in the above program so you could see whether they
are being called or not.

Regards, Mark

--