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

[Loring Craymer]

Use of backtracking forces ANTLR into LL(1) mode; the inserted synpreds then do not help if a first alternative matches the second alternative completely;  thus

LOWER
| LOWER term
translates to

( LOWER )=> LOWER
| LOWER term

so the first alternative is always matched.  This could get fixed in a future version of ANTLR (heavier duty analysis with reordering of alternatives), but you are really better off with not using backtracking.  The current error messages should be good enough (or nearly so) to tell you where you need to either insert synpreds or left-factor your grammar if you forego use of the backtracking option.

--Loring

----- Original Message ----
> From: John Woods <jqwoods at gmail.com>
> To: antlr-interest at antlr.org
> Sent: Tuesday, April 22, 2008 9:00:14 AM
> Subject: [antlr-interest] Trouble using backtracking (I think)
> 
> 
> 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());
>          }
>      }



      ____________________________________________________________________________________
Be a better friend, newshound, and 
know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ