java.lang.StackOverflowError with large input strings

[georg wiltschek]

Hi there,

I'm trying to write a parser for quantified boolean formulae, and very
short ones already pass, but up from a couple hundred KB, I get a
stack overflow:

Exception in thread "main" java.lang.StackOverflowError
        at Qbf_parserTokenManager.jjMoveStringLiteralDfa4_0(Qbf_parserTokenManager.java:126)
        at Qbf_parserTokenManager.jjMoveStringLiteralDfa3_0(Qbf_parserTokenManager.java:118)
        at Qbf_parserTokenManager.jjMoveStringLiteralDfa2_0(Qbf_parserTokenManager.java:96)
        at Qbf_parserTokenManager.jjMoveStringLiteralDfa1_0(Qbf_parserTokenManager.java:78)
        at Qbf_parserTokenManager.jjMoveStringLiteralDfa0_0(Qbf_parserTokenManager.java:53)
        at Qbf_parserTokenManager.getNextToken(Qbf_parserTokenManager.java:361)
        at Qbf_parser.jj_ntk(Qbf_parser.java:229)
        at Qbf_parser.Expression(Qbf_parser.java:46)
        at Qbf_parser.OpExpression(Qbf_parser.java:77)
        at Qbf_parser.Expression(Qbf_parser.java:65)
        at Qbf_parser.OpExpression(Qbf_parser.java:77)
        at Qbf_parser.Expression(Qbf_parser.java:65)

This goes on for a couple of pages, but always repeats itself...

So I'm wondering now if that's my fault, or if there's some kind of
limit for the input string size (and maybe a workaround for that)? You
can have a look at the code here:
http://fwef323.pastebin.com/m117e7991 and my test QBFs here
http://molly.inode.at/~georg/possibility.zip . I'm using version 4.1d1
on 64bit Ubuntu Jaunty, but also tried the latest version of javacc.

I would be really glad about any ideas regarding this,

Thanks in advance,
Georg

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@...
For additional commands, e-mail: users-help@...

[Legéndi Richárd]

A temporary workaround may be to increase the default Java stack size. By
default it's 256k on Unix afaik.

Use something like -Xss1m or more as a JVM argument, maybe that solves the problem.

Richard

georg wiltschek wrote:

> Hi there,
>
> I'm trying to write a parser for quantified boolean formulae, and very
> short ones already pass, but up from a couple hundred KB, I get a
> stack overflow:
>
> Exception in thread "main" java.lang.StackOverflowError
>         at Qbf_parserTokenManager.jjMoveStringLiteralDfa4_0(Qbf_parserTokenManager.java:126)
>         at Qbf_parserTokenManager.jjMoveStringLiteralDfa3_0(Qbf_parserTokenManager.java:118)
>         at Qbf_parserTokenManager.jjMoveStringLiteralDfa2_0(Qbf_parserTokenManager.java:96)
>         at Qbf_parserTokenManager.jjMoveStringLiteralDfa1_0(Qbf_parserTokenManager.java:78)
>         at Qbf_parserTokenManager.jjMoveStringLiteralDfa0_0(Qbf_parserTokenManager.java:53)
>         at Qbf_parserTokenManager.getNextToken(Qbf_parserTokenManager.java:361)
>         at Qbf_parser.jj_ntk(Qbf_parser.java:229)
>         at Qbf_parser.Expression(Qbf_parser.java:46)
>         at Qbf_parser.OpExpression(Qbf_parser.java:77)
>         at Qbf_parser.Expression(Qbf_parser.java:65)
>         at Qbf_parser.OpExpression(Qbf_parser.java:77)
>         at Qbf_parser.Expression(Qbf_parser.java:65)
>
> This goes on for a couple of pages, but always repeats itself...
>
> So I'm wondering now if that's my fault, or if there's some kind of
> limit for the input string size (and maybe a workaround for that)? You
> can have a look at the code here:
> http://fwef323.pastebin.com/m117e7991 and my test QBFs here
> http://molly.inode.at/~georg/possibility.zip . I'm using version 4.1d1
> on 64bit Ubuntu Jaunty, but also tried the latest version of javacc.
>
> I would be really glad about any ideas regarding this,
>
> Thanks in advance,
> Georg

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@...
For additional commands, e-mail: users-help@...

[Sreenivasa Viswanadha]

Hmm, that's weird. Can youi give the top of the stack trace? Did you try
increasing the stack size (like -Xss1M) to the vm? your grammar looks
pretty straightforward. Which JVM are you using? Just do java -version and
send us the output.

Sreeni.

> I'm trying to write a parser for quantified boolean formulae, and very
> short ones already pass, but up from a couple hundred KB, I get a
> stack overflow:
>
> Exception in thread "main" java.lang.StackOverflowError
>         at
> Qbf_parserTokenManager.jjMoveStringLiteralDfa4_0(Qbf_parserTokenManager.java:126)
>         at
> Qbf_parserTokenManager.jjMoveStringLiteralDfa3_0(Qbf_parserTokenManager.java:118)
>         at
> Qbf_parserTokenManager.jjMoveStringLiteralDfa2_0(Qbf_parserTokenManager.java:96)
>         at
> Qbf_parserTokenManager.jjMoveStringLiteralDfa1_0(Qbf_parserTokenManager.java:78)
>         at
> Qbf_parserTokenManager.jjMoveStringLiteralDfa0_0(Qbf_parserTokenManager.java:53)
>         at
> Qbf_parserTokenManager.getNextToken(Qbf_parserTokenManager.java:361)
>         at Qbf_parser.jj_ntk(Qbf_parser.java:229)
>         at Qbf_parser.Expression(Qbf_parser.java:46)
>         at Qbf_parser.OpExpression(Qbf_parser.java:77)
>         at Qbf_parser.Expression(Qbf_parser.java:65)
>         at Qbf_parser.OpExpression(Qbf_parser.java:77)
>         at Qbf_parser.Expression(Qbf_parser.java:65)
>
> This goes on for a couple of pages, but always repeats itself...
>
> So I'm wondering now if that's my fault, or if there's some kind of
> limit for the input string size (and maybe a workaround for that)? You
> can have a look at the code here:
> http://fwef323.pastebin.com/m117e7991 and my test QBFs here
> http://molly.inode.at/~georg/possibility.zip . I'm using version 4.1d1
> on 64bit Ubuntu Jaunty, but also tried the latest version of javacc.
>
> I would be really glad about any ideas regarding this,
>
> Thanks in advance,
> Georg
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: users-unsubscribe@...
> For additional commands, e-mail: users-help@...
>
>

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@...
For additional commands, e-mail: users-help@...

[georg wiltschek]

On Tue, Sep 8, 2009 at 8:01 PM, <sreeni@...> wrote:
> Hmm, that's weird. Can youi give the top of the stack trace?

Here's the full trace: http://trace312321.pastebin.com/m492d571c

> Did you try
> increasing the stack size (like -Xss1M) to the vm? your grammar looks
> pretty straightforward. Which JVM are you using? Just do java -version and
> send us the output.

Increasing the stack size works fine (with something like 3 or 4MB), my JVM is:

java version "1.6.0_14"
Java(TM) SE Runtime Environment (build 1.6.0_14-b08)
Java HotSpot(TM) 64-Bit Server VM (build 14.0-b16, mixed mode)

Thanks for your help,
Georg

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@...
For additional commands, e-mail: users-help@...

[Sreenivasa Viswanadha]

OK. That explains it. You have a single expression that's huge. That can
cause this problem. You may be able to simplify the grammar, but I can't
think of a way of doing it off the top of my head. For now, increasing the
stack size is the only solution I can think of.

Can you also post the test case that causes the problem? Thanks!

>> Hmm, that's weird. Can youi give the top of the stack trace?
>
> Here's the full trace: http://trace312321.pastebin.com/m492d571c
>
>> Did you try
>> increasing the stack size (like -Xss1M) to the vm? your grammar looks
>> pretty straightforward. Which JVM are you using? Just do java -version
>> and
>> send us the output.
>
> Increasing the stack size works fine (with something like 3 or 4MB), my
> JVM is:
>
> java version "1.6.0_14"
> Java(TM) SE Runtime Environment (build 1.6.0_14-b08)
> Java HotSpot(TM) 64-Bit Server VM (build 14.0-b16, mixed mode)
>
> Thanks for your help,
> Georg
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: users-unsubscribe@...
> For additional commands, e-mail: users-help@...
>
>

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@...
For additional commands, e-mail: users-help@...

[georg wiltschek]

On Tue, Sep 8, 2009 at 8:58 PM, <sreeni@...> wrote:
> Can you also post the test case that causes the problem? Thanks!

Yes, they're huge :-) Most of the time, I tested with something like
"(exists [v2] (forall [v1] (forall [v3] (((v1 | v2) | v3)))))", so I
didn't notice. At the moment, I use these test cases:
http://molly.inode.at/~georg/qbfs/

http://molly.inode.at/~georg/qbfs/possibility11_0_4-bin.qbf is the
smallest one, that overflows the stack, without increasing it's size.

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@...
For additional commands, e-mail: users-help@...

[Sreenivasa Viswanadha]

OK. Excessive parenthesization is the reason for this. If you change one
rule - <LP> Expression() <RP> (instead of OpExpression), you can parse
double the size of expression with the same stack size setting.

I can't think of any other easy way to fix the issue without redesigning
the language itself.

> On Tue, Sep 8, 2009 at 8:58 PM, <sreeni@...> wrote:
>> Can you also post the test case that causes the problem? Thanks!
>
> Yes, they're huge :-) Most of the time, I tested with something like
> "(exists [v2] (forall [v1] (forall [v3] (((v1 | v2) | v3)))))", so I
> didn't notice. At the moment, I use these test cases:
> http://molly.inode.at/~georg/qbfs/
>
> http://molly.inode.at/~georg/qbfs/possibility11_0_4-bin.qbf is the
> smallest one, that overflows the stack, without increasing it's size.
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: users-unsubscribe@...
> For additional commands, e-mail: users-help@...
>
>

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@...
For additional commands, e-mail: users-help@...

[georg wiltschek]

On Tue, Sep 8, 2009 at 10:38 PM, <sreeni@...> wrote:
> OK. Excessive parenthesization is the reason for this. If you change one
> rule - <LP> Expression() <RP> (instead of OpExpression), you can parse
> double the size of expression with the same stack size setting.

Tried it, but it still gets me stack overflows. I also think that I'd
lose the possibility to parse something like (v1 & v2 & v3) with that
change.

Anyways,

        <LP>
        Expression()
        (
                Op()
                Expression()
        )?
        <RP>

in the Expression() rule looks nicer somehow and I only have to
increase the stack to 2MB.

> I can't think of any other easy way to fix the issue without redesigning
> the language itself.

Although that would be a nice idea, it's not really an option :-)

Thank you anyways, never thought of just increasing the stack size,
and at least I know, that my code was ok.

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@...
For additional commands, e-mail: users-help@...