java.lang.StackOverflowError

[xareon]

hi all men, i'm new here, but got an issue. i use eclipse as IDE.

i'm writing a console program that work on a Label stack, where Label
is a class that i've defined by using a string and an int. i also wrote
a class with a method that takes a string as input, and recursively
pushes/pops elements of the stack.

the code is correct, (i checked it for various input strings with
length less than 10), but i get a java.lang.StackOverflowError for
bigger input strings (like 12 or more charachters in), as JVM couldn't
run all that operations (**** recursion!). is there a way to fix this
issue, maybe running the code stand-alone, instead of doing it from
eclipse or trying something else? thank you all

 

[Oliver Wong]

hi all men, i'm new here, but got an issue. i use eclipse as IDE.

i'm writing a console program that work on a Label stack, where Label
is a class that i've defined by using a string and an int. i also wrote
a class with a method that takes a string as input, and recursively
pushes/pops elements of the stack.

the code is correct, (i checked it for various input strings with
length less than 10), but i get a java.lang.StackOverflowError for
bigger input strings (like 12 or more charachters in), as JVM couldn't
run all that operations (**** recursion!). is there a way to fix this
issue, maybe running the code stand-alone, instead of doing it from
eclipse or trying something else? thank you all

Yes, it is possible to run your program standalone outside of Eclipse,
but I doubt that'll fix your problem. There are tutorials for compiling and
running java programs from the commandline for various OSes at
http://java.sun.com/docs/books/tutorial/getStarted/cupojava/index.html

Depending on what your program is doing, you are probably making more
recursive calls than you need to, and so the fix would be to redesign your
program so it doesn't make so many recursive calls.

- Oliver

 

[Bla]

hi all men, i'm new here, but got an issue. i use eclipse as IDE.

i'm writing a console program that work on a Label stack, where Label
is a class that i've defined by using a string and an int. i also wrote
a class with a method that takes a string as input, and recursively
pushes/pops elements of the stack.

the code is correct, (i checked it for various input strings with
length less than 10), but i get a java.lang.StackOverflowError for
bigger input strings (like 12 or more charachters in), as JVM couldn't
run all that operations (**** recursion!). is there a way to fix this
issue, maybe running the code stand-alone, instead of doing it from
eclipse or trying something else? thank you all

There is an option when running a java program, that says sth about memory for
the stack.
I can't remember the option now, but you'll find it easily on google.
But of course you'll eventually hit the limit.

 

[xareon]

thanks for your answers mate. well, before redisigning my code (that
could take really a lot of time for me, because i really can't find
another algorithm to make this) i wanna try to resize the memory of the
stack as Bla says, but can't find how to do that.

however, here is some code, mind that all is working fine for
stringToCheck that has 11 or less characters, then for 12 or more i get
the StackOverflowError:

public boolean check(int scanIndex)
	{
		productionSet = givenGrammar.getProductionSet();
		startSymbol = givenGrammar.getStartSymbol();

		if(sententialFormStack.isEmpty())
		{

			for (i = scanIndex; i < productionSet.size(); i++)
			{
				currentLeftSide = productionSet.elementAt(i).getLeftSide();
				currentRightSide = productionSet.elementAt(i).getRightSide();

				if (currentLeftSide.equals(startSymbol) &&
currentRightSide.length() <= stringToCheck.length())
				{
					if(currentLeftSide.equals(stringToCheck))
					{
						return true;
					}

					sententialFormStack.push(new Ancestor(startSymbol, i));
					return check(0);
				}
			}

			return false;
		}


		else
		{
			currentSententialForm =
sententialFormStack.peek().getSententialForm();
			currentScanIndex =
sententialFormStack.peek().getProductionIndexUsedToUnfold();


			for(i = scanIndex; i < productionSet.size(); i++)
			{
				currentLeftSide = productionSet.elementAt(i).getLeftSide();
				currentRightSide = productionSet.elementAt(i).getRightSide();


				totalLength = currentSententialForm.length() +
currentRightSide.length() - currentLeftSide.length();

				if(currentSententialForm.contains(currentLeftSide) && totalLength
<= stringToCheck.length())
				{
					newSententialForm =
currentSententialForm.replaceFirst(currentLeftSide, currentRightSide);


					if(newSententialForm.equals(stringToCheck))
					{
						return true;
					}

					sententialFormStack.peek().setProductionIndexUsedToUnfold(i);
					sententialFormStack.push(new Ancestor(newSententialForm, -1));

					return check(0);
				}
			}


			if(currentSententialForm.equals(startSymbol))
			{

				return false;
			}

			sententialFormStack.removeElementAt(sententialFormStack.size()-1);
			currentScanIndex =
sententialFormStack.peek().getProductionIndexUsedToUnfold();
			sententialFormStack.peek().setProductionIndexUsedToUnfold(-1);
 
			return check(currentScanIndex+1);
			
		}
	}

 

[Oliver Wong]

thanks for your answers mate. well, before redisigning my code (that
could take really a lot of time for me, because i really can't find
another algorithm to make this) i wanna try to resize the memory of the
stack as Bla says, but can't find how to do that.

however, here is some code, mind that all is working fine for
stringToCheck that has 11 or less characters, then for 12 or more i get
the StackOverflowError:

public boolean check(int scanIndex)
{
productionSet = givenGrammar.getProductionSet();
startSymbol = givenGrammar.getStartSymbol();[/QUOTE]
[rest of code snipped]

While it's clear to me that you're doing some sort of CFG-level parsing, I 
don't immediately recognize the algorithm you're using. Maybe this will be 
helpful to you? http://en.wikipedia.org/wiki/Recursive_descent_parser

    - Oliver

 

[xareon]

well man, i see that you've kinda found the point
the one i wrote is supposed to be a parsing method for type 1 grammars.
the algorithm i used is a depth-first search on the unfolding tree
starting from the axiom of the grammar (startSymbol). i didn't use any
specific algorithm, but i tried to build it from myself, that's what i
do:

i have some object types that i defined in some classes, let me show
you which they are:
Production, that's made up of a couple of strings, (leftSide,
rightSide), each representing the right or left side of a production A
-> B
Grammar, that's made up of a string (startSymbol) and a
Vector<Production> (productionSet)
Ancestor, that's made up of a string (sententialForm) and an int
(productionIndexUsedToUnfold).

then i defined in my class a sententialFormStack, that's a
Stack<Ancestor>, and it's the stack of the sentential forms for which i
may have some other unfloding possibilities that i have to analyze to
check whether my stringToCheck belongs to the language generated from a
given grammar.

the method parse, takes as input an integer (scanIndex), and that's the
pointer to the productionSet that defines where do i have to start my
research for unfolding possibilities.

that's what i do: if the stack is empty, i search in the productionSet
a production like startSymbol => sententialForm, where |sententialForm|
<= |stringToCheck| (because we know that type 1 grammars generate
bigger or same-length words each unfolding step). as soon as i find a
"good" production, i push into the stack the ancestor(startSymbol, i),
where i is the index of the production used to unfold the axiom
startSymbol. then starts a recursive calling of check.

if the stack is not empty, i'm in "the middle" of the unfolding tree:
then i look at the element at the top of the stack, and search in the
productionSet some left sides that are into the sententialForm where i
got into. where i find them, i continue the unfolding, checking each
time if the stringToCheck matches the currentSententialForm. if i find
it, i push it into the stack with the index of the production used, if
i cannot find no more productions to unfold currentStringToCheck, then
i remove the element at the top of the stack and continue my parsing
from the index of the production i used to get the old sententialForm.

the algorithm is working correct, as i could check trying to run it
with some stringToChecks and some givenGrammars, only for inputs that
don't have to make to much pushes/pop into the stack. otherwise i get a
stackoverflow error (i think it's due to too many recursive callings).
i hope i won't have to change algorithm, i've been working on it for a
while :s

 

[Oliver Wong]

well man, i see that you've kinda found the point
the one i wrote is supposed to be a parsing method for type 1 grammars.
the algorithm i used is a depth-first search on the unfolding tree
starting from the axiom of the grammar (startSymbol). i didn't use any
specific algorithm, but i tried to build it from myself, that's what i
do: [...]
the algorithm is working correct, as i could check trying to run it
with some stringToChecks and some givenGrammars, only for inputs that
don't have to make to much pushes/pop into the stack. otherwise i get a
stackoverflow error (i think it's due to too many recursive callings).
i hope i won't have to change algorithm, i've been working on it for a
while :s

Usually when someone writes a parser, it's for a single specific
grammar. It sounds like you're writing some sort of universal parser for
which the inputs is a grammar, and a string, and it checks whether or not
the string complies to the grammar.

If you want help with your algorithm design (which is independent of
what programming language you implement the algorithm in), try posting on
the comp.compilers newsgroup.

- Oliver

 

[xareon]

yes man, u're right. i'm writing an universal parser for type 1
grammar, and i'll follow your hint and try to post in comp.compilers.
however, tell me: could i avoid the stackoverflow by resizing the
stack? i read somewhere that i could fix my problem by setting a bigger
stack, that eclipse should set really small by default value as some
people say. it's something about commands -Xms -Xmx -Xss, but i
couldn't manage to make them work (i just run the program via console
and get the same error). do you know something about?

 

[Andrew Thompson]

yes man, u're right. i'm writing an universal parser for type 1
grammar, and i'll follow your hint and try to post in comp.compilers.
however, tell me: could i avoid the stackoverflow by resizing the
stack?

Probably not*. There is something like 64 Meg.
assigned to a typical Java app., and if this method
goes bananas over 12 chars, it indicates much
deeper problems in the code.

* Throwing more memory at it, will not help.

Fix the algroithm, and the program should work.

Andrew T.

 

[Daniel Dyer]

Probably not*. There is something like 64 Meg.
assigned to a typical Java app., and if this method
goes bananas over 12 chars, it indicates much
deeper problems in the code.

* Throwing more memory at it, will not help.

Fix the algroithm, and the program should work.

You're right, resizing the stack probably won't help (apart from maybe to
disguise the real problem). However, the the 64mb you refer to is heap
space not stack space. If heap space were exhausted the result would be
an OutOfMemoryError. The default thread stack size is only 256kb, which
still ought to be plenty.

The default stack size can be adjusted with -Xss. I've never had any need
to increase it, though I have reduced it to conserve resources when
spawning more threads than is sensible.

Dan.

 

[Oliver Wong]

yes man, u're right. i'm writing an universal parser for type 1
grammar, and i'll follow your hint and try to post in comp.compilers.
however, tell me: could i avoid the stackoverflow by resizing the
stack? i read somewhere that i could fix my problem by setting a bigger
stack, that eclipse should set really small by default value as some
people say. it's something about commands -Xms -Xmx -Xss, but i
couldn't manage to make them work (i just run the program via console
and get the same error). do you know something about?

Right, you could play around with the -Xms etc. settings (you can google
for the details), but as Andrew said, if you're running into errors after
just 12 characters, then you're memory usage is probably exponential
compared to the length of the input. Perhaps the problem you are trying to
solve is inherently exponential, I don't know the theory well enough to say
for sure. If it is exponential, then you're essentially out of luck and this
is an unsolvable problem. If you're lucky, the people at comp.compilers will
tell you it's not exponential, and give you an algorithm for solving it in
quadratic memory.

- Oliver

 

[Andrew Thompson]

...
..However, the the 64mb you refer to is heap
space not stack space. If heap space were exhausted the result would be
an OutOfMemoryError. The default thread stack size is only 256kb, which
still ought to be plenty.

Aahh yes. I knew 64 meg was 'wrong' (hence
the 'somethnig like' caveat) safe in the knowledge
that someone who actually knew, would chime in.

Thanks for the clarification.

Andrew T.

 

[Patricia Shanahan]

Right, you could play around with the -Xms etc. settings (you can google
for the details), but as Andrew said, if you're running into errors after
just 12 characters, then you're memory usage is probably exponential
compared to the length of the input. Perhaps the problem you are trying to
solve is inherently exponential, I don't know the theory well enough to say
for sure. If it is exponential, then you're essentially out of luck and this
is an unsolvable problem. If you're lucky, the people at comp.compilers will
tell you it's not exponential, and give you an algorithm for solving it in
quadratic memory.

Or, worse still, the program is in a recursive call loop, and no amount
of stack space would be enough.

With any recursive algorithm, it is worth asking "What ensures that the
recursion stops?". It is particularly important to answer that question
when debugging stack overflows.

Patricia

 

[xareon]

aw men, here i am after few days. the guys at comp.compilers newsgroup
don't seem to be going to accept my message (the group is moderated
there). however, after some google searches i found that java versions
before 6 running on windows xp, my encounter the 6316197 bug: -Xss
option doesn't modify the current stack size. i had to replace

public static void main(String[] args) {
-body-of-the-main
}

with this new code:

public static void main(String[] args) {
new Thread() {
public void run() {
body-of-the-main
}
}.start();
}

and although it isn't really clear to me what's this part of code, it
fixes the bugs and my program works, so i can set the stack sizer as
big as i want, and don't occour in the stack overflow. as someone
suggested to me, i changed my recursive dfs algorithm in a iterative
dfs one, and with this last one i don't have at all stack overflow
problems, so i can say that it works without problems now. but
iterative code isn't performant as recursive one, and i don't know if
that's the cost i *have to* pay to avoid the risk of getting a stack
overflow.

since i still can't post in comp.compilers, i have to ask it there:
anyone of you has another idea for algorithm for an universal type 1
grammar parser?

thank you all

 

[Oliver Wong]

aw men, here i am after few days. the guys at comp.compilers newsgroup
don't seem to be going to accept my message (the group is moderated
there).

[...]

Yeah, the group is moderated. When I post there, my posts usually appear
either the next day, or the day after that.

- Oliver