Antlr анализатор StackOverflowException

Question

У меня есть следующий в моем парсере грамматике Antlr для моего Xamarin.ios C# проекта:

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?

Я мог бы применить полосу помощи к проблеме, объединив списки цифр, прежде чем парсер их увидит. Но, скорее всего, он будет повторяться в конце концов с другим типом токена.

Answer 1

Вы не можете полностью избежать этой проблемы. Каждое обращение к правилам фактически является вызовом функции в сгенерированном парсере (принцип парсера рекурсивного спуска). Если ваш ввод достаточно сложный, вы наверняка попадете в доступный лимит стека. В большинстве (всех?) Компиляторов вы можете увеличить пространство стеков для своего приложения, но это также помогает только в определенной степени.

Однако, поскольку @BartKiers предложили снизить количество вызовов, используя циклы вместо рекурсий (принцип, часто используемый при программировании). Правило mathTokenList очень похоже на то, как вы определяете список в yacc/bison. В ANTLR вы можете использовать операторы цикла вместо этого, которые делают это лучше читать и менее ресурсоемким:

mathTokenList: mathToken+; 

это путь здесь. Это закончится в цикле, выполняемом в вашем методе mathTokenList (посмотрите на сгенерированный код синтаксического анализатора, иногда довольно просвещенный).