title: Left recursive ANTLR grammar
body: <p>I have written a grammar but getting a left recursive error.</p>
  
  <pre><code>grammar Lang;
  
  options
  {
      output  = AST;
      language    = C;
      ASTLabelType= pANTLR3_BASE_TREE;
      backtrack   = true;
  }
  
  start   : primary_expression+
      ;
  
  primary_expression
                  : '{' expression '}'
                  | expression ',' expression
                  ;
  
  expression
                  : logical_or_expression
                  | logical_or_expression '?' expression ':' expression
                  | logical_or_expression '?' ':' expression
                  | logical_or_expression '?' expression
                  ;
  
  logical_or_expression
                  : logical_and_expression
                  | logical_and_expression '|' logical_or_expression
                  ;
  
  logical_and_expression
                  : primary_expression
                  | primary_expression '&amp;' logical_and_expression
                  ;
  </code></pre>
  
  <p>I am getting the following error:</p>
  
  <blockquote>
    <p>[12:41:35] error(210):  The following sets of rules are mutually left-recursive [primary_expression, logical_and_expression, logical_or_expression, expression]<br>
    [12:41:35] Aborting because the following rules are mutually left-recursive:
        [[Lang.primary_expression,index=2,line=19], [Lang.logical_and_expression,index=5,line=36], [Lang.logical_or_expression,index=4,line=31], [Lang.expression,index=3,line=24]]</p>
  </blockquote>
  
  <hr>
  
  <h3>Corrected grammar</h3>
  
  <pre><code>grammar Lang;
  options 
  {
      // Note that in the C implementation, all implementations of trees and
      // adaptors pass around pANTLR3_BASE_TREE, which contains a super pointer
      // to your own implementation of a tree node and tree and so on. Hence
      // the node type is ALWAYS pANTLR3_BASE_TREE and there is no need to define
      // the type (the definition is silently ignored if you leave it there)
      //
      //output    = AST;
      language    = C;
      //ASTLabelType= pANTLR3_BASE_TREE;
      backtrack   = true;
  }
  
  start   : primary_expression+
      ;
  
  primary_expression
                  : '{' expression '}'
                  | expression ',' expression
                  ;
  
  expression
                  : logical_or_expression
                  | logical_or_expression '?' expression ':' expression
                  | logical_or_expression '?' ':' expression
                  | logical_or_expression '?' expression
                  ;
  
  logical_or_expression
                  : logical_and_expression
                  | logical_and_expression '|' logical_or_expression
                  ;
  
  logical_and_expression
                  : STRING
                  | STRING '&amp;' logical_and_expression
                  ;
  
  /* We're going to ignore all white space characters */
  WS  
      :   (' ' | '\t' | '\r'| '\n') {$channel=HIDDEN;}
      ;
  
  STRING
      :   ('a'..'z' | 'A'..'Z' | '0'..'9' | '_')+
      ;
  </code></pre>