ANTLR4 throws java.lang.StackOverflowError on longer files

Question

I am working on a grammar that parses potentially large markdown-like texts. 'Code' parts of the text are used to build an AST to be evaluated, while the rest of the text is ignored. My way of implementing this was to read the text until the '`' symbol (grave accent) is found, then push a 'Code' mode that takes care of parsing allowed expressions. Next grave accent would pop this mode and continue the loop.

The problem is that I get a stack overflow error when reading larg(er) chunks of text:

Exception in thread "main" java.lang.StackOverflowError
    at org.antlr.v4.runtime.CommonToken.<init>(CommonToken.java:113)
    at org.antlr.v4.runtime.CommonTokenFactory.create(CommonTokenFactory.java:94)
    at org.antlr.v4.runtime.CommonTokenFactory.create(CommonTokenFactory.java:40)
    at org.antlr.v4.runtime.Lexer.emit(Lexer.java:269)
    at org.antlr.v4.runtime.Lexer.nextToken(Lexer.java:180)
    at org.antlr.v4.runtime.BufferedTokenStream.fetch(BufferedTokenStream.java:187)
    at org.antlr.v4.runtime.BufferedTokenStream.sync(BufferedTokenStream.java:170)
    at org.antlr.v4.runtime.BufferedTokenStream.consume(BufferedTokenStream.java:154)
    at org.antlr.v4.runtime.Parser.consume(Parser.java:588)
    at org.antlr.v4.runtime.Parser.match(Parser.java:220)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:160)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.start_line(TestGrammarParser.java:113)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:168)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.start_line(TestGrammarParser.java:113)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:168)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    at decimill.parser.TestGrammarParser.line(TestGrammarParser.java:161)
    ...

Below is a grammar reduced to the absolute minimum that reproduces my problem. In fact, I've put it all into one grammar file to facilitate reproducing the error:

grammar TestGrammar;

@header {
    package decimill.parser;
}

parse
    : start_line
    ;

start_line
    : line
    ;

line
    : ANY line
    | EOL start_line
    | EOF
    ;

EOL     : [\n\r]+;
ANY     : ~[\n\r];

Feeding any text of 300+ lines will cause the error above (at least on my machine). I suspect I am doing something very wrong but since I'm quite new to ANTLR and building custom grammar parsers I cannot figure out what it is. Please help.

Answer 1

ANTLR generates recursive descent parsers. With few exceptions, the evaluation stack depth required for parsing corresponds directly to the depth of rule invocations which you write in the grammar.

Examples:

This requires one stack frame for every character.

line
  : Character line
  | EOF
  ;

This requires one stack frame total.

line
  : Character* EOF
  ;