title: Stack overflow parsing very large expressions in ANTLR4
body: <p>I am working reimplementing an existing DSL in ANTLR4.  The existing body of source has some VERY large expressions.  It appears that recursion in the ALL(*) logic means that there is a limit on how large an expression I can parse.</p>
  <p>Sample grammar: (just enough to reproduce the error here error)</p>
  <pre><code>  grammar A4Test;
  
    fragment DIGIT : [0-9];
  
    fragment ALPHA : [a-zA-Z];
  
  
    WS  :   [ \t\r\n\u000D'] {skip();};
      
    ID  :   ALPHA (ALPHA|DIGIT)*;
          
    NUMBER : '-'?(DIGIT+|(DIGIT*'.'DIGIT+));
       
    e : expr;
            
    expr : '(' expr ')'
      |   expr 'OR' expr
      |   expr 'AND' expr
      |   ID
      |   NUMBER
      ; 
   
  </code></pre>
  <p>Sample Input:</p>
  <pre><code>V0 AND 0 OR
  V1 AND 1 OR
  ...  (MANY rows elided)
  V3999 AND 3999 OR
  V4000 AND 4000
  </code></pre>
  <p>Stack Trace:</p>
  <pre><code>Exception in thread &quot;main&quot; java.lang.reflect.InvocationTargetException
      at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
      at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
      at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
      at java.lang.reflect.Method.invoke(Method.java:606)
      at org.antlr.v4.runtime.misc.TestRig.process(TestRig.java:249)
      at org.antlr.v4.runtime.misc.TestRig.process(TestRig.java:211)
      at org.antlr.v4.runtime.misc.TestRig.main(TestRig.java:143)
  Caused by: java.lang.StackOverflowError
      at java.util.Arrays.equals(Arrays.java:1869)
      at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
      at java.util.HashMap.getEntry(HashMap.java:471)
      at java.util.LinkedHashMap.get(LinkedHashMap.java:301)
      at org.antlr.v4.runtime.misc.DoubleKeyMap.get(DoubleKeyMap.java:62)
      at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
      at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:199)
      at org.antlr.v4.runtime.atn.ATNConfigSet.add(ATNConfigSet.java:175)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1126)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1111)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1164)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1111)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1164)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1111)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1164)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1111)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1164)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1111)
      at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1164)
  </code></pre>
  <p>...</p>
  <p>Limiting the size of expressions is not an option.  They compile fine with the current technology, so we'll have to support it.</p>
  <p>Will I have to factor out the left recursion on this to avoid the extremely high stack utilization?  Or, is there a simpler answer?</p>