[antlr-interest] Decision can match input such as "'*'" using multiple alternatives: 1, 2

[John B. Brodie]

Greetings!

On 11/30/2011 11:46 AM, Sergei Politov wrote:
> Hello,
> 
>   I'm new to ANTLR. I tried to port my grammar from Boost.Spirit to ANTLR
> and faced the following warning:
> Decision can match input such as "'*'" using multiple alternatives: 1, 2
> 
>   I made a minimal grammar to reproduce it (also in attach):
> ======================
> grammar X ;
> 
> s : e EOF ;
> e : t ;
> t : f ('*' f)* ;
> f : NUM | '-' e ;
> 
> NUM : '0'..'9'+ ;
> ======================
> 
>   Really I don't understand the described issue.

each use of the Kleene-Closure meta-operator (e.g. the (...)* stuff)
introduces an alternative into the parse. recall that the *
meta-operator is pronounced as "zero or more", so clearly there is a
choice in there somewhere.

your t rule recognizes the same sentential forms as these 2 rules:

t : f t_tail ;
t_tail : /*empty*/ | '*' f t_tail ;

the above are the usual transformation of the * meta-operator into
grammar productions.

and here you can clearly see the alternative.

>   I don't know input that could match in multiple ways.

consider the sentence: -1 * -2 * -3

now where does the "* -3" phrase belong? it is part of the e that begins
with -1? or is it part of the e that begins with -2? your grammar
provides no way to resolve this question and so it is ambiguous.

kinda like should the above be parsed as either
(-1 * -2) * -3
or as
-1 * (-2 * -3)

you might assert that multiplication is associative so it doesn't
matter. but the ANTLR tool doesn't (and in general can't) know that.

> 
>   Please clarify the situation.

To me this is identical to the traditional if-then-else ambiguity, you
might find more information in the usual compiler books about that
topic. (e.g. given "if b1 then if b2 then e1 else e2" where does the
else belong?)

Hope this helps...
   -jbb