[antlr-interest] parser generator error and tail recursion

[Koen Vanderkimpen]

Hi,

I recently changed some things in the java 1.5 grammar (antlr v3) to get 
nicer ast trees.

For example:

I changed
    multiplicativeExpression
        :   unaryExpression ( ( '*' | '/' | '%' ) unaryExpression )*
        ;
to
    multiplicativeExpression
     :     unaryExpression multiplicativeOp multiplicativeExpression
          -> ^(multiplicativeOp unaryExpression multiplicativeExpression)
     |    unaryExpression
     ;

This has tail recursion, works fine, and generates more usable expression 
trees, with the operator as root and the left and right operands as 
children. (multiplicativeOp is of course a rule with the possible operators)

I did the same on some higher level rules, and it also works fine for 
additive and shift expressions.

When I come to the level of relational expressions however, the parser 
generator tells me of an internal error and that it "could not even do k=1" 
for a certain rule. This happens only when I have 4 of those tail recursive 
rules in one hierachy, wherever they appear. It never happens when I have 3 
or less of them. If I were to change one of the rules like this:

    multiplicativeExpression
        : unaryExpression (multiplicativeOp multiplicativeExpression)?

it also still works without the error. But what is the difference between 
that and the other? Except for the fact that I can't build the tree how I 
want to build it with the latter rule.

Can anyone tell me how I can make antlr work and parse the expression 
1*2*3+4*5 to a tree of the following shape (for all possible expressions):

        +
    *       *
  *  3   4  5
1 2

I will post an ast tree generating java 1.5 grammar once I get it working 
decently.

Greetz,

Koen Vanderkimpen