Geek Answers Handbook

Stack overflow parses very large expressions in ANTLR4

I am working on an implementation and an existing DSL in ANTLR4. An existing source body has some VERY big expressions. It seems that recursion in ALL (*) logic means that there is a limit to how large the expression that I can parse.

Grammar example: (enough to reproduce the error here)

  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
    ;

Input Example:

V0 AND 0 OR
V1 AND 1 OR
...  (MANY rows elided)
V3999 AND 3999 OR
V4000 AND 4000

Stack trace:

Exception in thread "main" 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)

...

Limiting the size of expressions is not an option. They compile well using current technology, so we will have to support it.

Do I have to consider left recursion to avoid overuse of the stack? Or is there a simpler answer?

+4
source share
1 answer

ANTLR 4.2 , # 401. , ANTLR 4 .

0

More articles:


All Articles