[antlr-interest] parser generator error and tail recursion
Koen Vanderkimpen
koen.vanderkimpen+antlr at cs.kuleuven.be
Tue Nov 14 05:41:09 PST 2006
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
More information about the antlr-interest
mailing list