[antlr-interest] ANTLR not generating correct end condition on greedy=false loop.
Terence Parr
parrt at cs.usfca.edu
Sat Jan 17 18:55:13 PST 2004
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/
More information about the antlr-interest
mailing list