堆栈溢出解析 ANTLR4 中的非常大的表达式

Question

我正在努力在ANTLR4中重新实现现有的DSL。 现有的源代码主体有一些非常大的表达式。 似乎 ALL（*） 逻辑中的递归意味着我可以解析的表达式大小是有限制的。

示例语法：（刚好足以重现此处的错误错误）

  grammar A4Test;
  fragment DIGIT : [0-9];
  fragment ALPHA : [a-zA-Z];

  WS  :   [ trnu000D'] {skip();};
    
  ID  :   ALPHA (ALPHA|DIGIT)*;
        
  NUMBER : '-'?(DIGIT+|(DIGIT*'.'DIGIT+));
     
  e : expr;
          
  expr : '(' expr ')'
    |   expr 'OR' expr
    |   expr 'AND' expr
    |   ID
    |   NUMBER
    ; 
 

示例输入：

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

堆栈跟踪：

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)

。

限制表达式的大小不是一种选择。 他们使用当前的技术编译得很好，所以我们必须支持它。

我是否必须为此分解左递归以避免极高的堆栈利用率？ 或者，有更简单的答案吗？

Answer 1

ANTLR 4.2 将通过合并拉取请求 #401 来改善这种情况。由于它尚未发布，我建议从源代码构建最新版本的 ANTLR 4 并再次尝试输入。