[antlr-interest] Stack Overflow for Tree grammar CSharp target
Greg Smolyn
greg at smolyn.org
Tue Sep 2 14:51:19 PDT 2008
Hi,
I've got a rather large rule in a tree grammar (using the CSharp2
target, ANTLR 3.1), that when faced with a large input tree tends to
blow up with a StackOverflowException.
This happens only with some pretty crazy (but unfortunately required)
input that forces a very deep recursion.
The rule looks like
expr
: ^( ASSIGN expr expr )
| ^(MULT expr expr)
| ^(AND expr expr)
| ^(TYPEOF expr)
... <snipped about 50 others>...
;
This generates an expr() method with quite a few local variables, and
which can only handle about ~200 recursions (ie. given a tree like
"(* (* (* (* (* (* .... (* 2 3) ... 4) 5) 6) 7) 8) 9)").
There seem to be about 3 local variable references for every case,
which means the thing is putting at least 150 pointers onto the stack
at every recursive step.
For example:
CommonTree ASSIGN76 = null;
CommonTree MULT79 = null;
...
expr_return expr77 = default(expr_return);
expr_return expr78 = default(expr_return);
...
CommonTree ASSIGN76_tree=null;
CommonTree MULT79_tree=null;
Would this be a bug or future optimization? Am I going to have to go
down the path of changing my parser to emit some imaginary AST nodes
that can group these into smaller categories (ie. additiveExprs,
etc). I'd rather not do the latter as it would mean changing a whole
pile of other tree grammars using the generated ASTs.
Interestingly I see that really none of those variables are actually
used outside of their respective case statements. Could not these
variables be moved there, reducing the load for recursive calls?
Would mucking around in the StringTemplates for the csharp2 target be
something worth trying? Or is this something even higher up in the
antlr AST generation?
Thanks for any insights!
-greg
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20080902/9e226a81/attachment.html
More information about the antlr-interest
mailing list