[antlr-interest] Indirect left recursion?

Johannes Luber jaluber at gmx.de
Fri Nov 9 04:16:16 PST 2007


Julián Hidalgo wrote:
> Hi
> 
> The following fragment is taken from one of the earliest examples in the
> book (Expr.g):
> 
> expr:   multExpr (('+'|'-') multExpr)*
>     ;
> 
> multExpr
>     :   atom ('*' atom)*
>     ;
> 
> atom:   INT
>     |   ID
>     |   '(' expr ')'
>     ;
> 
> Now my question is: isn't this indirectly recursive? How does ANTLR
> handle it? I haven't read the whole book yet, so forgive me if the
> answer is over there (but I did read the "LL-Incompatible Decisions"
> section and the "Left-recursion" section).

Mutual left-recursion is when there is a path, in which a rule calls
itself again and where the call happens to be on the left edge.

a : b
  | c
  ;

b : a
  | c
  ;

is an example. The book example can turn "expr" only into "'(' expr ')'"
and has thus expr not on the left edge. If you want to solve my example
problem, then you have to inline the other rule and solve the
left-recursion:

a : (a
  | c)
  | c
  ;

That is

a : a
  | c
  ;

and this is

a : c;

Similarly we get

b : c;

Hope that helps,
Johannes


More information about the antlr-interest mailing list