ANTLR Decision can match input using multiple alternatives

Question

I have this simple grammer:

expr: factor;

factor: atom (('*' ^ | '/'^) atom)*;

atom: INT
    | ':' expr;

INT: ('0'..'9')+

when I run it it says :

Decision can match input such as '*' using multiple alternatives 1,2

Decision can match input such as '/' using multiple alternatives 1,2

I can't spot the ambiguity. How are the red arrows pointing ? Any help would be appreciated.

Ib

My grammar experience is very rusty, but you've got a left recursion (expr -> factor -> atom -> expr) with a potential right recursion as well... and do your really mean to match input like :(1/2) * :3 ? Can you give examples of the input you want to have parsed? – Vinia

It's not left recursive atom -> ':' expr. I'm working at a bigger grammer that has the same problem so I posted an equivalent example of my problem – Ib

Right, my mistake, still, it will help if you post an example of what you want to be considered valid. – Vinia

Answer 1

Let's say you want to parse the input:

:3*4*:5*6

The parser generated by your grammar could match this input into the following parse trees:

and:

(I omitted the colons to keep the trees more clear)

Note that what you see is just a warning. By specifically instructing ANTLR that (('*' | '/') atom)* needs to be matched greedily, like this:

factor
  :  atom (options{greedy=true;}: ('*'^ | '/'^) atom)*
  ;

the parser "knows" which alternative to take, and no warning is emitted.

EDIT

I tested the grammar with ANTLR 3.3 as follows:

grammar T;

options {
  output=AST;
}

parse
  :  expr EOF!
  ;

expr
  :  factor
  ;

factor
  :  atom (options{greedy=true;}: ('*'^ | '/'^) atom)*
  ;

atom
  :  INT
  |  ':'^ expr
  ;

INT : ('0'..'9')+;

And then from the command line:

java -cp antlr-3.3.jar org.antlr.Tool T.g

which does not produce any warning (or error).

Thy

Isn't greedy the default option ? – Ib

@JohnRetallack, yes, it is. That is why with or without the options{greedy=true;} the AST from my 1st image is created, only when specifying it explicitly, ANTLR does not emit the warning. – Thy

@JohnRetallack, check my EDIT to see how I ran the test. – Thy

I've tested your version with my antlr (antlr 3.2) and it still has the warning, it must be a bug, I'll try with 3.3 as well – Ib

@JohnRetallack, yeah, I just checked v3.2 and I also see the warning. Although the bug may also be in v3.3 (that it should still emit this warning, but doesn't). If I were you, I'd see if the grammar could perhaps be changed so that there is no such ambiguity anymore (if possible)... – Thy

can you point me in the right direction of how I could change the grammer above so I would get rid of this issue ? – Ib

@JohnRetallack, sorry, by "changing", I didn't mean reordering rules so that the ambiguity would be removed. The ambiguity is there, you'll have to rewrite the ':' expr into something else. I don't know what it is supposed to represent, so I can't comment on how you should rewrite it... – Thy

Thank you for your help. By the way I just started reading your blog post "Creating your own programming language with ANTLR.", it's the best introduction of ANTLR I read so far. – Ib