[antlr-interest] Re: Determinig the real ambiguities

[Terence Parr]

On Jul 15, 2004, at 1:00 PM, thrutchy wrote:
> 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.

Correct.

> Syntactic predicates look like they can mask warnings.

Yup.  It indicates you know what you are doing :)

> 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.

It is. ;)  However, the new ANTLR 3.0 prototype handles this situation 
trivially.  It tries more and more lookahead until it realizes it needs 
arbitrary lookahead and then it builds a tight little DFA that walks 
out until it sees the C or D and then it knows which production will 
succeed using real parsing.  Here is one of my unit tests:

     public void testAStarBOrAStarC() throws Exception {
         Grammar g = new Grammar(
                 "grammar t;\n"+
                 "a : (A)* B | (A)* C;");
         String expecting =
                 ".s0-A->:s2=>1\n" +
                 ".s0-B->:s1=>2\n";
         checkDecision(g, 1, expecting, null); // loopback
         expecting =
                 ".s0-A->:s2=>1\n" +
                 ".s0-C->:s1=>2\n";
         checkDecision(g, 2, expecting, null); // loopback
         expecting =
                 ".s0-A->.s1\n" +
                 ".s0-B->:s2=>1\n" +
                 ".s0-C->:s3=>2\n" +
                 ".s1-A->.s1\n" +
                 ".s1-B->:s2=>1\n" +
                 ".s1-C->:s3=>2\n";
         checkDecision(g, 3, expecting, null); // rule block
     }

The decision 3 is for the rule block (last one) and it builds the DFA 
described linearly in text, but if you draw it out, you'll see that it 
correctly predicts alts 1 and 2.  "=>1" means predict alt 1. ".s1" is 
state 1 and ":s3" is accept state 3.

Ter
--
CS Professor & Grad Director, University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Cofounder, http://www.jguru.com
Cofounder, http://www.knowspam.net enjoy email again!
Cofounder, 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/