[antlr-interest] ANTLR not generating correct end condition on greedy=false loop.

[Terence Parr]

On Friday, January 16, 2004, at 12:24 PM, Daniel Shane wrote:

> Hi,
>
> Why does this grammar result in an invalid condition to break out of 
> the
> loop:
>
> a: LCURLY any RCURLY;
> b: PLUS any MINUS;
>
> any: ( options { greedy=false; } : . )*;
>
> On input
>
> { fdsfa + fdsfds - fdsfds }
>
> The condition for end of loop is all tokens that can follow any (in 
> this
> case MINUS and RCURLY) even if its quite obvious from the grammar that 
> when
> inside rule a, rule b can never trigger.

Yup.  This is because ANTLR is not a full LL(k) parser (which is highly 
nonlinear).  There is no context information--just lookahead 
information in an SLL(k) parser.  ANTLR can only see the global 
FOLLOW(any), which is the union of all possible contexts.  Sorry about 
that...  One solution is to simply embed the any look inside a and b.

>  This of course will give an invalid
> parse because the loop will stop at - and it will expect a RCURLY.
>
> To make this grammar work I have to write:
>
> a: LCURLY ( options { greedy=false; } : . )*  RCURLY;
> b: PLUS ( options { greedy=false; } : . )*  MINUS;
>
> so that the end condition is ok. Is there a way to make the above 
> grammar
> work? Is there a good reason for this kind of limitation?

Oh, ok, you got the solution.  The reason is per the above that 
manually splitting/duplicating rules automatically results in some 
pretty big parsers so people tend to build SLL(k) not LL(k).  Same goes 
for LR vs LALR/SLR parsers.  LR is a damn big parser often times.

Ter
--
Professor Comp. Sci., University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Co-founder, http://www.jguru.com
Co-founder, http://www.knowspam.net enjoy email again!
Co-founder, http://www.peerscope.com pure link sharing




 

Yahoo! Groups Links

To visit your group on the web, go to:
 http://groups.yahoo.com/group/antlr-interest/

To unsubscribe from this group, send an email to:
 antlr-interest-unsubscribe at yahoogroups.com

Your use of Yahoo! Groups is subject to:
 http://docs.yahoo.com/info/terms/