解析时的 ANTLR4 相互左递归错误

java recursion antlr

2022-09-01 23:09:00

我有这个ANTLR 4语法：

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

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

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

我收到以下错误：

error（119）： LanguageA.g4：：：以下规则集是相互左递归的 [constantFixedExpresion， factor， term]

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

答案 1

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

这是由语法中的这种结构引起的：

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

由于运算符意味着0或更多，我可以用0实例化它，所以解析器会这样做：“尝试，所以它需要尝试，所以它需要尝试，所以它需要尝试，所以它[...]”，你得到了一个无限循环。*constantFixedExpressiontermfactorconstantFixedEXpression

幸运的是，上下文无关的形式语法具有用于删除左递归的等效转换！它可以泛泛地表示为：

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

或者在Antlr表示法中：

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

有关此过程的更多信息可以在自动机/语法书籍或维基百科中找到。

我将通过重构来纠正语法，以删除左递归作为您的工作。但是，我想在另一点上触摸：Antlr 4可以做左递归！正如我所提到的，版本4可以在同一规则内处理左递归。有一些方法可以指示运算符的优先级和关联性，而不是像您在Antlr4中那样直接解析。让我们看看它是如何工作的：

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

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

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

答案 2