title: ANTLR, Trouble with expression grammar
body: <p>I've recently started using ANTLR. I'm currently trying to encode an expression grammar with <code>+</code>, <code>-</code>, <code>*</code> and <code>array[index]</code> and a few more constructs.</p>
  
  <p>This is the desired grammar:</p>
  
  <pre><code>Exp -&gt; Exp (+ | - | * | &lt; | &amp;&amp;) Exp
       | Exp [ Exp ]
       | -Exp
       | ( Exp )
       | Exp.length
       | true
       | false
       | Id
       | this
       | ! Exp
  </code></pre>
  
  <p>I first refactored this into <code>AndExp</code>, <code>SumExp</code>, <code>ProdExp</code> and so on to resolve precedence. Roughly like this:</p>
  
  <pre><code>Exp        -&gt; AndExp
  AndExp     -&gt; CmpExp (&amp;&amp; CmpExp)*
  CmpExp     -&gt; SumExp (&lt; SumExp)*
  SumExp     -&gt; ProdExp ((+|-) ProdExp)*
  ProdExp    -&gt; UnaryExp (Times UnaryExp)*
  UnaryExp   -&gt; Minus* PrimaryExp
  PrimaryExp -&gt; Exp.length
              | Exp [ Exp ]
              | ! Exp
              | true
              | false
              | Id
              | this
  </code></pre>
  
  <p>I then realized that this uses left-recursion, and that ANTLR doesn't like that. I went on to <a href="http://en.wikipedia.org/wiki/Left_recursion#Removing_immediate_left_recursion" rel="nofollow">eliminate the left-recursion</a> and I ended up with this grammar:</p>
  
  <pre><code>grammar test;
  
  options {
      language=Java;
      output=AST;
      backtrack=true;
  }
  
  start      : expression;
  
  expression : andExp;
  andExp     : cmpExp (And^ cmpExp)*;
  cmpExp     : sumExp (LessThan^ sumExp)*;
  sumExp     : prodExp ((Plus | Minus)^ prodExp)*;
  prodExp    : unaryExp (Times^ unaryExp)*;
  unaryExp   : Minus* primaryExp;
  
  primaryExp : INT                   primaryPrime
             | 'true'                primaryPrime
             | 'false'               primaryPrime
             | 'this'                primaryPrime
             | ID                    primaryPrime
             | '!' expression        primaryPrime
             | '('! expression ')'!  primaryPrime
             ;
  
  
  primaryPrime
             : '[' expression ']'             primaryPrime
             | '.' ID '(' exprList ')'        primaryPrime
             | '.length'                      primaryPrime
             | 'new' 'int' '[' expression ']' primaryPrime
             | 'new' ID '(' ')'               primaryPrime
             |
             ;
  
  
  exprList   :
             | expression (',' expression)*;
  
  LessThan   : '&lt;';
  Plus       : '+';
  Minus      : '-';
  Times      : '*';
  And        : '&amp;&amp;';
  Not        : '!';
  INT        :    '0' | ('1'..'9')('0'..'9')*;
  ID         :    ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*;
  WS         : ('\t' | ' ' | '\r' | '\n'| '\u000C') { $channel=HIDDEN; } ;
  </code></pre>
  
  <ul>
  <li><p><strong>Q1:</strong> Is backtracking "required" for this type of grammar (I can't get it through ANTLR unless I activate it) or am I missing something simple?</p></li>
  <li><p><strong>Q2:</strong> When adding a few <code>^</code> and <code>-&gt; ^(TOKEN ...)</code> constructs to brush up the tree, I ran into the following annoying situation (because of the <code>primaryPrime</code> which is due to the left factoring):</p>
  
  <pre><code>primaryPrime
      : '[' expression ']' primaryPrime -&gt; ^(ARRAY_EXPR expression)
  //...
  </code></pre>
  
  <p>This turns an <code>array[index]</code> into</p>
  
  <pre><code>array
  ARRAY_EXPR
      index
  </code></pre>
  
  <p>while I really want</p>
  
  <pre><code>ARRAY_EXPR
      array
      index
  </code></pre>
  
  <p>What is the best way to solve this? Am I on the right track here, or should I go with some other approach all together?</p></li>
  </ul>