<p>This is only orthogonally relevant, but I just published a preprint of a paper on a new parsing method that I call "pika parsing" (c.f. packrat parsing) that directly handles left recursive grammars without the need for rule rewriting.</p>

<p><a href="https://arxiv.org/abs/2005.06444" rel="nofollow noreferrer">https://arxiv.org/abs/2005.06444</a></p>
Removing Left Recursion in ANTLR
<p>As is explained in <a href="https://stackoverflow.com/questions/2652060/removing-left-recursion">Removing left recursion</a> , there are two ways to remove the left recursion.</p>

<ul>
<li>Modify the original grammar to remove the left recursion using some procedure</li>
<li>Write the grammar originally not to have the left recursion</li>
</ul>

<p>What people normally use for removing (not having) the left recursion with ANTLR? I've used flex/bison for parser, but I need to use ANTLR. The only thing I'm concerned about using ANTLR (or LL parser in genearal) is left recursion removal.</p>

<ul>
<li>In practical sense, how serious of removing left recursion in ANTLR? Is this a showstopper in using ANTLR? Or, nobody cares about it in ANTLR community?</li>
<li>I like the idea of AST generation of ANTLR. In terms of getting AST quick and easy way, which method (out of the 2 removing left recursion methods) is preferable?</li>
</ul>

<h2>Added</h2>

<p>I did some experiment with the following grammar.</p>

<pre>
E -> E + T|T
T -> T * F|F
F -> INT | ( E )
</pre>

<p>After left recursion removal, I get the following one</p>

<pre>
E -> TE'
E' -> null | + TE'
T -> FT'
T' -> null | * FT'
</pre>

<p>I could come up with the following ANTLR representation. Even though, It's relatively pretty simple and straightforward, it seems the grammar that doesn't have the left recursion should be the better way to go.</p>

<pre>
grammar T;

options {
    language=Python;
}

start returns [value]
   : e {$value = $e.value};
e returns [value]
   : t ep  
     {
       $value = $t.value
       if $ep.value != None:
         $value += $ep.value
     }
   ;
ep returns [value]
   : {$value = None}
   | '+' t r = ep 
     {
       $value = $t.value
       if $r.value != None:
            $value += $r.value
     }
   ;
t returns [value]
  : f tp 
    {
      $value = $f.value
      if $tp.value != None:
        $value *= $tp.value
    }
  ;
tp returns [value]
  : {$value = None}
  | '*' f r = tp 
    {
      $value = $f.value;
      if $r.value != None:
        $value *= $r.value
    }
  ;
f returns [int value]
  : INT {$value = int($INT.text)}
  | '(' e ')' {$value = $e.value}
  ;

INT :   '0'..'9'+ ;
WS: (' '|'\n'|'\r')+ {$channel=HIDDEN;} ;
</pre>