Thursday, July 10, 2008

Antlr Frustrations

I just spent a frustrating morning fighting to get Suneido's query grammar to work with Antlr.

I kept getting "no viable alternative" and "no start rule (no rule can obviously be followed by EOF)"

I searched on the web but didn't find any answers.

I made more or less random changes to my grammar and if I cut out the more complex stuff it would work but that wasn't much help.

I started trying small examples, like:

expr : m (('+'|'-') m)* ;
m : ID
| '(' expr ')' ;
ID : ('a'..'z')+ ;
WS : (' '|'\t'|'\r'|'\n')+ {skip();} ;

which is pretty much straight out of the book but exhibited the same problems.

I started to wonder if something was messed up in my copy of Antlr or something.

Eventually, I found a post that explained it. The problem is that Antlr identifies "start" rules (ones that can end with EOF) by looking for rules that are not used anywhere else in the grammar. When you have recursion on the "start" rule (expr in this case), it doesn't work. The above example could be fixed by adding:

prog : expr ;

It makes sense once you know the problem, but it certainly wasn't obvious at first. And I don't recall the book mentioning it anywhere. It seems like an obvious "gotcha". I can't be the only person to get caught by this. It would have been nice if the error message said something like "make sure your start rule is not used in another rule".

Or else just make it work. Obviously, the rule you start with should be endable by EOF, whether or not it's used elsewhere. That's probably a little tricky to handle, but compared to the complexity of Antlr it's nothing.

This kind of frustration is one of the downsides of using someone else's tools and libraries.

Various other stupid mistakes on my part added to the frustration, but eventually I got things starting to work.


kan said...

thank you for the post. i have the same problem, and now I know what that is.

jam said...

Hi, thanks for this post. It has solved my problem. It is funny since it is very easy to get this error message when you write short grammar. I got this error after re-using portion of code from working grammar and thus it was even more surprising.

Paul said...

Thanks a lot. The error message of Antlr is everything else but self-explantory

Matt McKnight said...

Cheers. Nice post to discover on the stroke of midnight when my own powers of analysis are failing me.

Anonymous said...

Thank you for this! You really took away my headache!

parrt said...

Hi guys...sounds like somebody should add this as a FAQ entry to the ANTLR wiki ;)

Kai said...

You can also mark the others with 'fragment'

Senseless example:

exp : thing;

thing : 'a' exp | 'b'

Mils said...

Excellent post.
I had this same issue. I am new to Antlr, and would have struggled to find the cause of this error!

Anonymous said...

You saved my mind, thanks.

Anonymous said...

Thanks +1

Anonymous said...

You need to make sure the rule is not used by another rule.

expr: primary EOF;

primary: NUMBER | STRING | '(' expr ')';

The above will still give you the warning. You need to add another rule.

root: expr EOF;

expr: primary;

primary: NUMBER | STRING | '(' expr ')';

This will remove the waring.

Eli said...

Thanks, very nice post.

Andreas said...

Thanks! I got frustrated by that too!