antlr - 由于递归规则调用，规则具有非 LL(*) 决策

Question

我有一个错误（如标题中所述），其中一条规则我不知道如何解决。

我写了以下规则：

FunctionArguments returns FunctionArgs::IFunctionArguments :
    FunctionArgumentsNormal
    | FunctionArgumentsForIter
    ;

FunctionArgumentsNormal returns FunctionArgs::IFunctionArguments :
    {FunctionArgs::FunctionArguments} args+=Expression (',' args+=Expression)* 
    | {FunctionArgs::FunctionArguments} argNames+=NamedArguments (',' argNames+=NamedArguments)*
    ;

FunctionArgumentsForIter returns FunctionArgs::IFunctionArguments :
    {FunctionArgs::FunctionArgumentsIterator} exp=Expression 'for' iterators=ForIterator
    ;

您能否通过左分解此表达式来帮助我解决它或请提供任何其他解决方案？

Answer 1

在 LL 语法中，您不能有左递归。问题是 LL 解析器可以选择进行这样的推导： FunctionArguments -> FunctionArgumentsNormal -> FunctionArguments -> FunctionArgumentsNormal ...您的语法包含所谓的间接左递归。您可以在此 wikipedia-article 中找到一个示例，该示例还包含有关如何修复它的解决方案：Left-Recursion。一个好的起点是（我想您已经这样做了）以非常简单的方式编写语法，而不需要示例中包含的所有注释和内容。如果您有简单形式的语法：

S -> A | B
B -> "terminal1" B
  |  b
A -> a "terminal2"

进行必要的重写要容易得多。