How do you remove left recursion?

I'm trying to write a grammar for a simple language that has left recursion, but I don't really understand how.

Basically my grammar looks like this:

expr: expr('@'TYPE)? '.' ID '(' (expr ',')∗ ')'
| expr '+' expr
| ID
| INTEGER
| STRING


INTEGER : ('0'..'9')+;
STRING : '"' ('a'..'z' | 'A'..'Z' | '0'..'9')* '"';
TYPE : ('String' | 'Bool' |开发者_JAVA百科 'Int')
ID : ('a'..'z' | 'A'..'Z')('a'..'z' | 'A'..'Z' | '0'..'9')*;

There is more to it but that's the important part with the left recursion I'm trying to remove.

I've been looking on the Wikipedia about it, and this is what I ended up with:

expr: function
| add
| ID
| INTEGER
| STRING

function : ( ('@'TYPE)? '.' ID '(' (expr',')* ')'  function)?;
add : (('+' expr) add)?;

However antlr still says it's left recursive and I can't get it to recognize the language I want it to. Could anyone help me out and explain to me how to remove the left recursion?

Both function and add match ε (empty string). Remove the ? at the end of the rules and you're fine:

function 
  :  ('@'TYPE)? '.' ID '(' (expr',')* ')'  function
  ;

add 
  :  '+' expr add
  ;

Note that (expr',')* dictates that a "list" of expressions must always end with a comma. Perhaps the following is more appropriate:

(expr (',' expr)*)?

which matches ε or one or more expr separated by a comma.

Note that the left recursive grammar:

expr ::= expr '+' expr
      |  expr '-' expr
      |  expr '*' expr
      |  expr '/' expr
      |  '-' expr
      |  function
      |  INTEGER
      |  STRING
      |  IDENTIFIER
      |  '(' expr ')'

could be translated into:

expr
  :  addExpr
  ;

addExpr
  :  multExpr (('+' | '-') multExpr)*
  ;

multExpr
  :  unaryExpr (('*' | '/') unaryExpr)*
  ;

unaryExpr
  :  '-' atom
  |  atom
  ;

atom
  :  function
  |  INTEGER
  |  STRING
  |  IDENTIFIER
  |  '(' expr ')'
  ;

where ANTLR has no problems with (ie. no left recursion anymore).