 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / January 2007java.lang.StackOverflowError
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 ;) > hi all men, i'm new here, but got an issue. i use eclipse as IDE. > [quoted text clipped - 9 lines] > 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 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: [CODE] 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); } } [/CODE] > 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 [quoted text clipped - 11 lines] > productionSet = givenGrammar.getProductionSet(); > startSymbol = givenGrammar.getStartSymbol(); [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 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 > 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 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? On Jan 25, 10:29 am, xar...@gmail.com wrote: > 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. > On Jan 25, 10:29 am, xar...@gmail.com wrote: >> yes man, u're right. i'm writing an universal parser for type 1 [quoted text clipped - 10 lines] > > 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.  SignatureDaniel Dyer https://watchmaker.dev.java.net - Evolutionary Algorithm Framework for Java > On Wed, 24 Jan 2007 23:49:12 -0000, Andrew Thompson > > On Jan 25, 10:29 am, xar...@gmail.com wrote: ... > >> ...could i avoid the stackoverflow by resizing the stack? > > > Probably not*. There is something like 64 Meg. .. > ..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. > 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. [quoted text clipped - 4 lines] > 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 >> 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. [quoted text clipped - 14 lines] > 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 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 :) > 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 > hi all men, i'm new here, but got an issue. i use eclipse as IDE. > [quoted text clipped - 9 lines] > 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. Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.