[antlr-interest] Re: Determinig the real ambiguities

thrutchy eric_mahurin at yahoo.com
Thu Jul 15 13:00:31 PDT 2004


So, without the syntactic predicate, it won't work?  I thought it
would try the first alternative and then go to the second if it fails.
 That's not correct?  I guess only syntactic predicates only allow
that type of thing.

Syntactic predicates look like they can mask warnings.  For example,
this masks the warning, but I don't think will work:

a_must_have_c : ((A)? (B)+)=> (A)? (B)+ C D | (B)+ D ;

It would be nice if ANTLR had the smarts to figure out that these two
alternatives really aren't ambiguous (from an infinite lookahead
perspective) and then do the right thing, but I know that could be
quite difficult.  Instead maybe an easier stop-gap solution would be
to provide an option to resolve what it thinks are ambiguities by
predicating the first of every pair of ambiguous alternatives by that
alternative.  For example:

a_must_have_c options{generateAmbigWarnings=predicate;}
    : (A)? (B)+ C D
    | (B)+ D
    ;

would be equivalent to:

a_must_have_c
    : ((A)? (B)+ C D) => (A)? (B)+ C D
    | (B)+ D
    ;

Or you could think of this option as turning on backtracking (like in
regex's) where it thinks it might make a difference.  Probably
something similar could be done for conditional and loop constructs:

(options{generateAmbigWarnings=predicate;}: xyz)(*|+|?)

would be the same as the following if it thinks there is an ambiguity:

((xyz)=>xyz)(*|+|?)

Of course a more concise way to specify this instead of these long
options would be nice.

Eric

--- In antlr-interest at yahoogroups.com, Monty Zukowski <monty at c...> wrote:
> Ok, with this particular example you need a syntactic predicate, also 
> known as "infinite lookahead."  Note that for any value of k this is a 
> real ambiguity.
> 
> a_must_have_c : ((A)? (B)+ C)=> (A)? (B)+ C D
> 			  | (B)+ D ;
> 
> The other thing to do is to factor the rule, sometimes that is 
> practical, sometimes it isn't, depending on your actions & tree 
> building.
> 
> Monty
> 
> 
> On Jul 15, 2004, at 11:42 AM, Bogdanov, Serge wrote:
> 
> >> a_must_have_c : (A)? (B)+ C D | (B)+ D ;
> >
> > How about
> > 	a_must_have_c : A (B)+ C D | (B)+ D;
> >
> >>> Sergey Bogdanov
> > intel massachusetts
> > M/S HD2-246
> > 77 Reed Road,
> > Hudson, MA  01749
> > Tel: (978)553-2724
> >
> >> -----Original Message-----
> >> From: thrutchy [mailto:eric_mahurin at y...]
> >> Sent: Thursday, July 15, 2004 2:30 PM
> >> To: antlr-interest at yahoogroups.com
> >> Subject: [antlr-interest] Determinig the real ambiguities
> >>
> >> Is there a way to turn off the ambiguities warnings that aren't real
> >> and only affection the parser prediction (and thus performance)?
 Here
> >> is an example:
> >>
> >> a_must_have_c : (A)? (B)+ C D | (B)+ D ;
> >>
> >> It thinks these alternatives are ambiguous because they both can
start
> >> with an indeterminate amount of B's, but the ambiguity is resolved
> >> right after that.
> >>
> >> I assume ANTLR will try matching the first alternative and then go to
> >> the second if the input matches the second alternative.  Is that
> > correct?
> >>
> >> I know that there are several ways I can turn off the warnings
> >> (syntactic predicate, options), but it would be nice if ANTLR could
> >> figure out that the alternatives really don't overlap even though it
> >> may predict the wrong alternative.  Eventually, it would be good to
> >> fix as many of these mispredictions as possible, but initially
> >> functionality is what matters.
> >>
> >> Eric
> >>
> >>
> >>
> >>
> >>
> >>
> >> Yahoo! Groups Links
> >>
> >>
> >>
> >>
> >
> >
> >
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
> >
> >
> >
> >
> 
> ANTLR & Java Consultant -- http://www.codetransform.com
> ANSI C/GCC transformation toolkit -- 
> http://www.codetransform.com/gcc.html
> Embrace the Decay -- http://www.codetransform.com/EmbraceDecay.html



 
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