ANTLRパーサStackOverflowExceptionが

Question

私はXamarin.ios C＃プロジェクトのための私のANTLRパーサー文法で次き：

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しかし、リストに一度十分な長さを取得、それが一番上にいくつかのリスナーのコードで、自分自身を再帰的に呼び出して生成MathTokenListとして、StackOverflowExceptionがにつながる：

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の本当に長いリストを見ないようにするために、もっと関わる何かをする必要がありますか？

私は、パーサがそれらを見る前に数字のリストを組み合わせることで、問題にバンドエイドを付けることができました。しかし、それは最終的には他のトークンタイプで再発する可能性があります。

Answer 1

この問題を完全に回避することはできません。各ルール呼び出しは、実際には生成されたパーサー（再帰的降下パーサの原理）の関数呼び出しです。あなたの入力が十分に複雑な場合は、確かに利用可能なスタック制限に達するでしょう。ほとんどの（すべての）コンパイラでは、アプリのスタックスペースを増やすことができますが、これはある程度まで助けになります。

@BartKiersは、再帰の代わりにループを使用することで呼び出し回数を減らすことを提案しました（プログラミングでよく使用される原則）。 mathTokenListのルールは、yacc/bisonでリストを定義する方法に非常によく似ています。 ANTLRでは、代わりにループ演算子を使用することができます。これにより、読みやすく、リソースの消費量を少なくすることができます。

mathTokenList: mathToken+; 

ここに行く方法です。これはあなたのmathTokenListメソッドで実行されているループで終了します（生成されたパーサーコードを見てください、時にはかなり啓発されます）。 `mathTokenList ：あなたはこのしようとするとどうなります