[antlr-interest] [3.0b4] StackOverflowError report

John B. Brodie jbb at acm.org
Tue Oct 24 15:23:57 PDT 2006


>Additional info, the equivalent grammar:
>
>> start : r0 EOF ;
>> r0 : N r0  ;
>> r1 : N  ;
>
>does not cause a stack overflow. So what's wrong with the r0 : r1 r0  
>grammar?

...snipped...
...a grammar that causes stack overflow

> grammar TestParser;
> options { superClass = GeneratedParser; }
> @parser::header {
>   import grammatotron.*; }
>
> start : r0 EOF ;
> r0 : r1 r0  ;
> r1 : N  ;
>
>
> N : 'n';
> V : 'v';
>
> Exception in thread "main" java.lang.StackOverflowError
> 	at org.antlr.runtime.BaseRecognizer.combineFollows 
> (BaseRecognizer.java:388)
> 	at  
> org.antlr.runtime.BaseRecognizer.computeContextSensitiveRuleFOLLOW 
> (BaseRecognizer.java:376)
> 	at org.antlr.runtime.BaseRecognizer.recoverFromMismatchedElement 
> (BaseRecognizer.java:478)
> 	at org.antlr.runtime.BaseRecognizer.recoverFromMismatchedToken 
> (BaseRecognizer.java:445)
> 	at org.antlr.runtime.BaseRecognizer.mismatch(BaseRecognizer.java:98)
> 	at org.antlr.runtime.BaseRecognizer.match(BaseRecognizer.java:80)
> 	at TestParser.r1(TestParser.java:92)
> 	at TestParser.r0(TestParser.java:63)
> 	at TestParser.r0(TestParser.java:67)

observe that the stack overflow occurs while trying to recover from a syntax
error...

observe that both of the above grammars get syntax errors when run.

this happens because there is no base-case for the r0 recursive rule. that is,
an r0 *ALWAYS* has another r0 as its tail.  thus we are expected to parse an
INFINITE sequence of N's followed by an EOF. Impossible.

do you mean r0 : r1 + ; or r0 : (r1 r0) | r1 ; <-- both are equivalent.
or perhaps  r0 : r1 * ; or r0 : (r1 r0) | /*empty*/ ; <-- both are equivalent.

i do not know why error recovery terminates under the `r0 : N r0 ;` rule but
not under the `r0 : r1 r0 ;` rule.

Hope this helps...
   -jbb


More information about the antlr-interest mailing list