解析ANTLR4中非常大的表達式的堆棧溢出

我正在ANTLR4中重新實現和現有的DSL。現有的源代碼有一些非常大的表達式。看起來ALL（*）邏輯中的遞歸意味着我可以解析的表達式有多大的限制。解析ANTLR4中非常大的表達式的堆棧溢出

樣品語法：（剛夠這裏重現錯誤錯誤）

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)

...

限制t他的表情的大小不是一種選擇。他們用當前的技術編譯得很好，所以我們必須支持它。

爲了避免極高的堆棧利用率，我需要將這個左遞歸分解掉嗎？或者，有更簡單的答案嗎？

來源

2014-01-17 Mike Cargal

你可以嘗試更大的JVM堆棧： http://stackoverflow.com/questions/3700459/how-to-increase-to-java-stack-size – FreeJack

我已經做到了，它的確與衆不同，但最終只是推斷了一點，所以我很難將其稱爲解決方案。 –

ANTLR 4.2將通過合併pull request #401來改善這種情況。由於它尚未發佈，我建議從源代碼構建最新版本的ANTLR 4並再次嘗試輸入。

來源

2014-01-17 20:27:47

看起來很有希望。我會看一看。我已經做了左遞歸移除，並且在一個簡單的測試中，對性能改進感到震驚，所以我期望只保留版本而沒有左遞歸。你的改變會導致性能接近與我通過去除左遞歸所得到的結果一樣快嗎？如果性能在那裏，我寧願回到更簡單的語法（和更簡單的AST）。 –

我已經在GitHub上構建了最新的源代碼。看起來，這可能會防止（或肯定會改善）堆棧溢出的情況。我正在編譯單個表達式，並且Java內存利用率正在逐漸增加。也就是說，看起來我可能會創建一個強制性的案例，給出O（n4）（或接近那個）的表現。具有左遞歸的語法運行速度非常快（可能是亞秒;我沒有計時）;然而，用左遞歸語法運行已經運行了6個多小時，並且還沒有完成。 –

@MikeCargal你能發給我你的語法和樣本輸入來證明問題嗎？我想對它進行一些測試。另外，我們能夠創造的唯一的O（n 4）情況涉及一個非常明顯的結構不明確的規則。我們對無歧義文法所見最糟糕的是O（n³）。 –

解析ANTLR4中非常大的表達式的堆棧溢出

回答

相關問題