[antlr-interest] please help understand strange backtracking behavior

Mikhail Kruk meshko at gmail.com
Fri May 18 13:44:50 PDT 2012

I'm working on a proof of concept SQL parsing grammar, which for now
relies on backtracking.
I'm running into a strange issue which I can't understand and hope
someone can take a look at it and shed some light for me.
I've produced what I think is the minimal grammar demonstrating this
problem and it is attached.

I'm trying to parse the expression

using the condition_expr rule.

What I expect to happen:
ANTLR should
try  condition_is alternative and fail, backtrack and
try condition_is_a_set alternative and fail, backtack and
try condition_between alternative
match TEST(1) as an expr of type function_call with an argument
followed by BETWEEN 1 and 4

What happens:
It tries condition_is and condition_is_a_set and they fail to match,
backtracks and tries to match condition_between, however it goes on a
weird tangent of trying to match the function_call as keyCOUNT and
I don't understand:
1) why this happens
2) why does it stop happening as soon as I make a smallest tweak to
the grammar (e.g. removing condition_is_a_set alternative, or
replacing keyCOUNT with a 'COUNT')
3) what is the easiest way of figuring out problems like this?

I'm going to attach a screenshot of the failed parse tree, perhaps
someone can figure out what is going on by just looking at it w/o
having to run this stuff.

Thank you!!
-------------- next part --------------
A non-text attachment was scrubbed...
Name: t2.g
Type: application/octet-stream
Size: 1728 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20120518/e387dbbf/attachment.obj 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bad.png
Type: image/png
Size: 28132 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20120518/e387dbbf/attachment.png 

More information about the antlr-interest mailing list