[antlr-interest] Trouble using backtracking (I think)

[John Woods]

I'm having trouble figuring out why my grammar isn't working as 
expected, and would greatly appreciate any pointers on what I'm 
misunderstanding.

My generated parser behaves as if backtracking isn't working as I would 
expect. And further, when I modify the grammar in a way that I wouldn't 
expect to have an effect, backtracking appears to start working.

I've simplified the grammar as much as I could and still reproduce the 
problem. And the simplified input I'm trying to parse is "(a = b)" 
(without the quotes).

Here's the test grammar:

     grammar Test;

     options {
         language = Java;
         output = AST;
         backtrack = true;
     }

     input
         : expression
         | '(' input ')'
         ;

     expression
         // Swapping the following two lines makes it
         // work for input "(a = b)". But why won't it
         // work with backtracking the way it is?
         : lower_term
         | term '=' term
         ;

     term
         : lower_term
         | UPPER
         ;

     lower_term
         : LOWER
         // Removing "term*" from the following line, or
         // removing the line altogether makes it work.
         // Why is that? Seems unrelated to given input.
         | LOWER '(' term* ')'
         ;

     UPPER: 'A'..'Z';
     LOWER: 'a'..'z';

     WHITESPACE: (' '|'\t'|'\n'|'\r'|'\f') { skip(); };

When I try to parse the input "(a = b)", I get the following error:

     BR.recoverFromMismatchedToken
     line 1:3 mismatched input '=' expecting ')'

It appears that the parser attempts to parse the "expression" rule using 
the "lower_term" alternative only, and when that fails, it seems like 
backtracking isn't coming back and attempting the other alternative of 
"term '=' term".

I'm using ANTLR version 3.0.1 (August 13, 2007).

Finally, here's the test driver:

     import java.io.*;
     import org.antlr.runtime.*;
     import org.antlr.runtime.tree.*;

     public class Test {
         public static void main(String[] args) throws Exception {
             String string = "(a = b)";
             ByteArrayInputStream byteArrayInputStream =
                 new ByteArrayInputStream(string.getBytes());
             ANTLRInputStream antlrInputStream =
                 new ANTLRInputStream(byteArrayInputStream);
             TestLexer testLexer =
                 new TestLexer(antlrInputStream);
             CommonTokenStream commonTokenStream =
                 new CommonTokenStream(testLexer);
             TestParser testParser =
                 new TestParser(commonTokenStream);
             CommonTree commonTree =
                 (CommonTree)testParser.input().getTree();
             System.out.println(commonTree.toStringTree());
         }
     }