解析时ANTLR4相互左递归错误

Question

我有这个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]

我尝试了很多方法,但无法修复它.有什么问题,如何解决？

Answer 1

Antlr是一个LL(*)解析器,它在许多方面比LL(k)解析器 "更好" ,但仍有许多不利之处.其中一个原因是它不能处理左递归(实际上,版本4可以处理同一规则中的左递归).错误的含义是你有一个语法的左递归,一个LL解析器的祸根.

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

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

由于*运算符意味着0或更多,我可以用0实例化它,所以解析器将执行此操作:"尝试constantFixedExpression,所以它需要尝试term,所以它需要尝试factor,所以它需要尝试constantFixedEXpression,所以它[...] "而你已经拥有了无限循环.

幸运的是,无上下文的形式语法有一个等效的转换来删除左递归!它可以通过以下方式表达:

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*3将被解析2+(2*3)而不是(2+2)*3.该<assoc=right>建筑是指在右关联的运营商,因此1^2^3将被解析1^(2^3),而不是(1^2)^3.

正如您所看到的,使用左递归指定运算符要容易得多,因此Antlr 4在这些时刻有很大帮助!我建议重新编写语法以使用此功能.