[antlr-interest] Why i need to use LL(*) ????

Umesh Kalappa umesh.kalappa0 at gmail.com
Tue Sep 4 23:10:27 PDT 2012


Hi Group ,

This is regrading about the  new feature that ANTLR v3 introduced called
 LL(*) Parsing i.e


Natural grammars are sometimes not LL(k) for any fixed k even if the k is
usually small; e.g. C function declarations vs definitions. From the left
edge, the lookahead is not fixed to see the ';' vs '{' to distinguish the
cases:

func : type ID '(' arg* ')' ';'
     | type ID '(' arg* ')' '{' body '}'
     ;
We need arbitrary lookahead because of the arg*. If you have actions at ID,
you can't easily refactor. The lookahead will be 5<=k<=10 usually for this
decision.

Here ,in the above example ,i can left factor out the grammar then using
LL(*) , which is more efficient like

func : type ID '(' arg* ')' funcelse
     ;
funcelse:';'| {' body '}'
     ;

Any inputs regrading this ??

Thanks
~Umesh


More information about the antlr-interest mailing list