java - 解析时ANTLR4相互左递归错误

我有这个ANTLR 4语法:

constantFixedExpresion : term (('+'|'-') term)+;

term : factor (('*'|'//'|'REM')factor)+;

factor : ('+'|'-')*
           ( wholeNumberConstant
           | constantFixedExpresion
           | 'TOFIXED' (stringConstant | bitCodeConstant)
           | identifier)
         ('FIT'constantFixedExpresion)*;

我收到以下错误:



我尝试了很多方法，但无法解决。有什么问题，我该如何解决？

最佳答案

Antlr是LL(*)解析器，在许多方面都比LL(k) parser“更好”，但仍然有很多缺点。其中之一是它不能处理左递归(实际上，版本4可以在同一规则内处理左递归)。错误的意思是，您的语法左递归，这是LL解析器的祸根。

这是由您的语法中的这种构造引起的:

constantFixedExpression: term ...;
term: factor ...;
factor: ('+' | '-')* (constantFixedExpression | ...) ...;

由于*运算符的含义是0或更大，因此我可以用0实例化它，因此解析器将执行以下操作:“try constantFixedExpression，因此它需要尝试term，所以它需要尝试factor，因此需要尝试constantFixedEXpression，因此[...]”，您将陷入无限循环。

幸运的是，无上下文形式语法具有消除左递归的等效转换!它可以一般性地表达为:

A -> Aa | b
-- becomes --
A -> bR
R -> aR | ε

或以Antlr表示法:

A: Aa | b;
// becomes
A: bR;
R: (aR)?;

有关此过程的更多信息，请参见自动机/语法书籍或Wikipedia。

我将通过重构来纠正您的语法，以除去左递归。但是，我想谈谈另一点:Antlr 4可以进行左递归!正如我提到的，版本4可以在同一规则中处理左递归。除了直接在Antlr4中进行解析时，还有其他方法可以指示运算符的优先级和关联性。让我们看看它是如何工作的:

expr: NUMBER
      |<assoc=right> expr '^' expr
      | expr '*' expr
      | expr '/' expr
      | expr '+' expr
      | expr '-' expr;

这是基本计算器语法的示例。顶部的运算符是优先级最高的运算符，而底部的运算符则优先级较低。这意味着2+2*3将被解析为2+(2*3)而不是(2+2)*3。 <assoc=right>的构造意味着运算符处于右关联状态，因此1^2^3将被解析为1^(2^3)而不是(1^2)^3。

如您所见，使用左递归指定运算符要容易得多，因此在这些时候，Antlr 4很有帮助!我建议重新编写语法以利用此功能。