ANTLR的解析器StackOverflowException

我在ANTLR的語法分析器我Xamarin.ios C＃項目如下：ANTLR的解析器StackOverflowException

mathToken 
    : DIGIT    #Digit 
    | NULL    #Null 
    | LESSTHAN   #LessThan 
    | GREATERTHAN  #GreaterThan 
    | anyLessThanOrEqual #LessThanOrEqual 
    // about 30 more options here 

mathTokenList 
    : mathToken mathTokenList #CompoundMathTokens 
    | mathToken     #SingleMathToken 
    ;

這對於10代幣，100，甚至1000的列表但是，一旦名單的偉大工程得到足夠長的時間，它會導致一個StackOverflowException，所生成的MathTokenList遞歸調用自身，一些聽衆代碼頂部：

MyNamespace.HandleToken(MyTokenClass parserToken, List<MyOtherTokenClass> buildingList) in MyNamespace.ManualFileParser.cs:58 
MyNamespace.CustomStringReaderParseListener.VisitDefault(Antlr4.Runtime.Tree.TerminalNodeImpl node) in MyNamespace.CustomStringReaderParseListener.cs:228 
MyNamespace.CustomStringReaderParseListener.VisitTerminal(Antlr4.Runtime.Tree.TerminalNodeImpl node) in MyNamespace.CustomStringReaderParseListener.cs:94 
Antlr4.Runtime.Parser.Consume() 
Antlr4.Runtime.Parser.Match(int ttype) 
Antlr.StringReaderParser.mathToken() 
Antlr.StringReaderParser.mathTokenList() // lots of calls here . . . seems to be 
Antlr.StringReaderParser.mathTokenList() // one for each token. 
Antlr.StringReaderParser.mathTokenList() // (in antlr generated code)

是否有可能進行重組解析器語法來避免這種問題？或者我需要做更多的事情，以便解析器永遠不會看到很長的mathTokens列表？

在解析器看到它們之前，我可以通過組合數字列表來爲這個問題提供創可貼。但它最終可能會與其他一些令牌類型一起發生。

來源

2016-11-13 William Jockusch

什麼，當你嘗試這種情況： 'mathTokenList ：mathToken mathToken + #CompoundMathTokens | mathToken #SingleMathToken ;' ？ –

你不能完全避免這個問題。每個規則調用實際上是生成的解析器中的函數調用（遞歸下降解析器原理）。如果你的輸入只夠複雜，你肯定會達到可用的堆棧限制。在大多數（所有？）編譯器中，您可以增加應用程序的堆棧空間，但這也僅在某種程度上有所幫助。

但是，@BartKiers建議您可以通過使用循環而不是遞歸來降低調用計數（這是編程中常用的一個原則）。 mathTokenList規則看起來很像您將如何在yacc/bison中定義列表。在ANTLR你可以使用循環運營商代替，使這個更好的閱讀和更少的資源密集型：

mathTokenList: mathToken+;

是去這裏的路。這將在您的mathTokenList方法中執行的循環中結束（查看生成的解析器代碼，有時非常有啓發性）。

來源

2016-11-13 09:18:06

ANTLR的解析器StackOverflowException

回答

相關問題