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

Question

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

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

  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
    ; 
 

样本输入：

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 将通过合并pull request #401来改善这种情况。由于尚未发布，我建议从源代码构建最新版本的 ANTLR 4 并再次尝试您的输入。