[antlr-interest] Re: Determinig the real ambiguities
Terence Parr
parrt at cs.usfca.edu
Thu Jul 15 13:19:21 PDT 2004
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/
More information about the antlr-interest
mailing list