[antlr-interest] Why is this ambiguous..

[Peter Kooiman]

Hi Sam 

> Edit: I misread the original email, but I'm still sending this because 
> it resolves the warning given on the rule y. 

;-) Yeah that much is clear, I also fully understand the crazyness of not left-factoring rule "start" into (y C?)+ EOF; 

Just was wondering why the warning on rule "start" as it stands below, I was expecting ANTLR to "auto-left-factor" with the prediction dfa and don´t quite understand why it does not on this occasion. 

Thanks 
Peter 

> Consider the input 'ba', starting with the rule start. It could parse as 
> (y y EOF), with the first y matching B without the A, and the second 
> matching just A. It could also parse as (y EOF), with the first y 
> matching B and the optional A. 

> If you mean for y to always include the A when present, you can use 
> a syntactic predicate, which forces it to choose the second 
> interpretation above: 

> y : B ((A) => A)? | A; 

> Sam 

-----Original Message----- 
From: antlr-interest-bounces at antlr.org 
[mailto:antlr-interest-bounces at antlr.org] On Behalf Of Peter Kooiman 
Sent: Thursday, April 07, 2011 7:50 AM 
To: antlr-interest at antlr.org 
Subject: [antlr-interest] Why is this ambiguous.. 

Hello, 

While working on a grammar I had something that boils down to 

grammar T; 
start: (y | y C)+ EOF; 
y: B (A)? | A; 

A : 'a'; 
B : 'b'; 
C : 'c'; 

This gives an expected warning on rule y, that's fine, ANTLR does the right 
thing and matches A greedily. 
However it also gives a warning on rule start: 

T.g:2:19: Decision can match input such as "B {EOF, B..A}" using multiple 
alternatives: 1, 2 
As a result, alternative(s) 2 were disabled for that input 

I quite understand the need to left factor this, I was just wondering why 
ANTLR gives this warning. It must be staring me in the face but I don't see 
it... 
How is this non-deterministic on input B EOF? Is ANTLR unable to see past 
rule y for some reason? 

Thanks 
Peter 


List: http://www.antlr.org/mailman/listinfo/antlr-interest 
Unsubscribe: 
http://www.antlr.org/mailman/options/antlr-interest/your-email-address