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 个标记的列表非常有用。但是一旦列表变得足够长，它就会导致 WhosebugException，因为生成的 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 方法中执行一个循环（查看生成的解析器代码，有时很有启发性）。

Antlr 解析器 StackOverflowException

Antlr parser StackOverflowException

c#

parsing

xamarin.ios

antlr4

xamarin