bugGrammatica - Bugs: bug #11737, Grammatica 1.4 runs into an stack...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #11737: Grammatica 1.4 runs into an stack overflow error

Submitted by:  Michael Knaup <mknaup>
Submitted on:  Wed 26 Jan 2005 09:55:28 AM UTC  
 
Severity: 2 - NormalItem Group: Software
Status: FixedAssigned to: Per Cederberg <cederberg>
Open/Closed: Closed

(Jump to the original submission Jump to the original submission)

Sat 14 Mar 2009 09:34:39 AM UTC, comment #6:

Version 1.5 was released on 2009-03-07. Closing this issue.

Per Cederberg <cederberg>
Project AdministratorIn charge of this item.
Tue 24 Feb 2009 10:16:45 PM UTC, comment #5:

This is fixed in subversion trunk, since the implementation now uses a memory-conservative NFA implementation for most regular expresions. This should avoid any stack overflows when parsing complex regexes with long matches.

Will be released in version 1.5.beta1.

Per Cederberg <cederberg>
Project AdministratorIn charge of this item.
Sat 21 May 2005 09:39:23 PM UTC, comment #4:

Ok, the issue was in the StringLiteral production with a quote char mismatch with the [^\"] part. By adding a single \' character at the end of the line, the grammar is parsed with the correct error messages.

The reason for the stack overflow then, is the Grammatica regular expression (RE) interpreter. This interpreter is currently based on recursive calls, so it cannot match infinitely large regular expression strings. The stack overflow occured as the number of characters matched by the regular expression (in this case \'[^\']*\') grew beyond the maximum limit.

It seems the default stack size is smaller on JDK 5.0/Windows than on JDK 1.4/Linux, which is the reason for not being able to reproduce this problem previously. Anyway, this is clearly a limitation in the Grammatica RE implementation and as such should be fixed.

The solution is to completely rewrite the RE interpreter to use a limited amount of stack and heap memory. This is unfortunately not trivial and will not happen within a short timeframe. Bug #8202 describes the conversion of the existing RE implementation into a NFA, which is probably the best solution to this issue.

This bug has been marked postponed and as dependent on #8202.

Per Cederberg <cederberg>
Project AdministratorIn charge of this item.
Sat 21 May 2005 08:54:38 PM UTC, comment #3:

Sorry about that, reopening this bug. Just found the mail with the full test code. Also managed to reproduce this with JDK 5.0 on Windows XP.

Per Cederberg <cederberg>
Project AdministratorIn charge of this item.
Sat 21 May 2005 08:21:57 PM UTC, comment #2:

Closing this bug as I cannot reproduce this error. I need the xpath1.grammar file that exposed this problem in order to localize it.

Per Cederberg <cederberg>
Project AdministratorIn charge of this item.
Wed 26 Jan 2005 02:45:49 PM UTC, comment #1:

Thanks for the bug report. Could you please also attach or send me the erroneous grammar file so that I can have a look at it? I suspect the grammar contains some error, but Grammatica should of course report that properly and not be throwing exceptions around.

Per Cederberg <cederberg>
Project AdministratorIn charge of this item.
Wed 26 Jan 2005 09:55:28 AM UTC, original submission:

Trying to create a c# parser for xpath grammar grammatica runs into an endless loop which causes a stack overflow. The output is as follows:
E:\Tools\grammatica-1.4>java -jar lib\grammatica-1.4.jar test\src\grammar\xpath1.grammar --csoutput test\xpath --csnamespace XPATHGrammar
Exception in thread "main" java.lang.StackOverflowError
at java.util.ArrayList.get(Unknown Source)
at net.percederberg.grammatica.parser.re.CharacterSetElement.inUserSet(C
haracterSetElement.java:323)
at net.percederberg.grammatica.parser.re.CharacterSetElement.inSet(Chara
cterSetElement.java:229)
at net.percederberg.grammatica.parser.re.CharacterSetElement.match(Chara
cterSetElement.java:207)
at net.percederberg.grammatica.parser.re.RepeatElement.findMatches(Repea
tElement.java:309)
at net.percederberg.grammatica.parser.re.RepeatElement.findMatches(Repea
tElement.java:321)
at net.percederberg.grammatica.parser.re.RepeatElement.findMatches(Repea
tElement.java:321)
at net.percederberg.grammatica.parser.re.RepeatElement.findMatches(Repea
tElement.java:321)
at net.percederberg.grammatica.parser.re.RepeatElement.findMatches(Repea
tElement.java:321)

I can't find the java source to correct my grammar or the software problem. Can anyone help?
Thanks,
Michael

Michael Knaup <mknaup>

 

No files currently attached

 

Digest:
   bug dependencies.

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by cederberg (Posted a comment)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 11 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sat 14 Mar 2009 09:34:39 AM UTCcederbergOpen/ClosedOpen=>Closed
      Discussion LockUnlocked=>Locked
    Tue 24 Feb 2009 10:16:45 PM UTCcederbergStatusPostponed=>Fixed
    Sat 21 May 2005 09:39:23 PM UTCcederbergSeverity5 - Major=>2 - Normal
      StatusNone=>Postponed
      Dependencies-=>Depends on bugs #8202
    Sat 21 May 2005 08:54:38 PM UTCcederbergStatusNeed Info=>None
      Open/ClosedClosed=>Open
    Sat 21 May 2005 08:21:57 PM UTCcederbergStatusNone=>Need Info
      Assigned toNone=>cederberg
      Open/ClosedOpen=>Closed

    Back to the top


    Powered by Savane 3.1-cleanup1