title: ANTLR: How the behavior of this grammar which recognizes suffixes of a Java code can be explained?
body: <p>A week ago I started the following project: a grammar which recognizes suffixes of a Java code. </p>
  
  <p>I used the official <code>ANTLR</code> grammar for Java (<code>Java.g4</code>) as a baseline and started to add some rules. However, those new rules also introduced left recursion which I also had to deal with. </p>
  
  <p>After a couple of days of work I had the <a href="http://pastebin.com/Lt5w3hSz">following code</a>. When I started testing I noticed something unusual which I still can't explain. When given the input <code>{ }</code> the parser tells me <code>no viable alternative at input '&lt;EOF&gt;'</code> but when I switch the order of the terminals in the right-handed side of the rule <code>s2</code>, particularly if we change the right-handed side from <code>v2_1 | v2_2 | v2_3 ...</code> to <code>v2_36 | v2_1 | v2_2 ...</code> (the terminal <code>v2_36</code> is moved to the first position), the sequence <code>{ }</code> gets accepted. </p>
  
  <p>My first thoughts were that <code>Antlr</code> does not backtrack because I noticed that with the input <code>{ }</code> the first version of the parser starts to follow the rule <code>v2_3</code> and just reports that nothing is found and does not try to consider other options (that's what I think but maybe it's not true) like <code>v2_36</code> which give exactly the positive answer. </p>
  
  <p>But, after some research, I found out that <code>ANTLR</code> actually does backtrack but only if everything else fails. At least this is true for v3.3 (read it in official <code>ANTLR</code> paper) but I guess it's also true for <code>v4</code>. Now I'm a little bit confused. After spending so many hours on this project I would feel really terrible if I don't make it work. Can someone gives some kind of tip or something? It would be greatly appreciated, thanks.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>Managed to isolate the problem to</p>
  
  <pre><code>grammar Java;
  @parser::members {String ruleName; }
  
  start : compilationUnitSuf EOF;
  
  compilationUnitSuf
      :   {ruleName = "typeDeclarationSuf"; } s2
      ;
  
  s2: '{' '}' v2_81 | '{' '}';
  v2_81 : {ruleName.equals("enumBodyDeclarationsSuf")}? t173 | t173 '}';
  t173: '}' | '{'*;
  
  LBRACKET: '{';
  RBRACKET: '}';
  
  WS  :  [ \t\r\n\u000C]+ -&gt; skip
      ;
  </code></pre>
  
  <p>So why does the predicting algorithm suggest me to follow <code>s2 -&gt; v'{' '}' v2_81 -&gt; ...</code> instead of <code>s2 -&gt; '{' '}'</code>?</p>