[antlr-interest] Stack Overflow for Tree grammar CSharp target

[Greg Smolyn]

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