Out of memory in grammar bounding

[GoogleCodeExporter]

This should go through really fast because all sizes are fixed. Instead, it
blows up.

var string:75;
cfg q2 := \104 \116 \116 \112 \058 \047 \047 \057 \056;
cfg q3 := \046;
cfg q4 := \049 \051 \048;
cfg q5 := \046;
cfg q6 := \050 \052 \057;
cfg q7 := \046;
cfg q8 := \053 \055 \047 \098 \050 \101 \118 \111 \108 \117 \116 \105  
\111 \110 \047 \097 \100 \109 \105 \110;
cfg q9 := \046;
cfg q10 := \112 \104 \112;
cfg q11 := \063;
cfg q12 := \099 \116 \114 \108 \061 \105 \116 \101 \109 \115 \038  
\102 \105 \108 \116 \101 \114 \061 \114 \101 \115 \116 \111 \114 \101  
\038 \098 \108 \111 \103 \061 \049;
cfg q1 := q2 q3 q4 q5 q6 q7 q8 q9 q10 q11 q12;
cfg flax0 := q1;

assert string in flax0; 

Original issue reported on code.google.com by [email protected] on 3 Feb 2010 at 6:19

[GoogleCodeExporter]

The problem is in GrammarStringBounder.lowerBounds.
For safety and simplicity it assumes that lower bound on any nonterminal is 0 
or 1.
This bound can be dramatically improved if we checked what the nonterminal 
expands to
and, if it expands to a constant string, then use the length of that string as 
both
the lower and the upper bound. More aggresively, we could check if the all 
strings
generated from the nonterminal are of constant size (or maybe there's just one 
string
genenerated).   

Original comment by [email protected] on 26 Feb 2010 at 8:03