如何消除左递归？

Question

我正在尝试为一种保留了递归的简单语言编写语法，但我不太明白如何实现。

基本上我的语法看起来像这样：

expr: expr('@'TYPE)? '.' ID '(' (expr ',')∗ ')'
| expr '+' expr
| ID
| INTEGER
| STRING


INTEGER : ('0'..'9')+;
STRING : '"' ('a'..'z' | 'A'..'Z' | '0'..'9')* '"';
TYPE : ('String' | 'Bool' | 'Int')
ID : ('a'..'z' | 'A'..'Z')('a'..'z' | 'A'..'Z' | '0'..'9')*;

还有更多内容，但这是我试图删除的左递归的重要部分。

我一直在维基百科上查找有关它的信息，这就是我最终得到的结果：

expr: function
| add
| ID
| INTEGER
| STRING

function : ( ('@'TYPE)? '.' ID '(' (expr',')* ')'  function)?;
add : (('+' expr) add)?;

但是antlr仍然说它是左递归的，我无法让它识别我想要的语言。谁能帮我解释一下如何删除左递归？

Answer 1

function 和 add 都匹配 ε（空字符串）。删除规则末尾的 ? 就可以了：

function 
  :  ('@'TYPE)? '.' ID '(' (expr',')* ')'  function
  ;

add 
  :  '+' expr add
  ;

请注意 (expr',')* 规定表达式“列表”必须始终以一个逗号。也许下面的内容更合适：

(expr (',' expr)*)?

匹配 ε 或一个或多个以逗号分隔的 expr。

请注意，左递归语法：

expr ::= expr '+' expr
      |  expr '-' expr
      |  expr '*' expr
      |  expr '/' expr
      |  '-' expr
      |  function
      |  INTEGER
      |  STRING
      |  IDENTIFIER
      |  '(' expr ')'

可以翻译为：

expr
  :  addExpr
  ;

addExpr
  :  multExpr (('+' | '-') multExpr)*
  ;

multExpr
  :  unaryExpr (('*' | '/') unaryExpr)*
  ;

unaryExpr
  :  '-' atom
  |  atom
  ;

atom
  :  function
  |  INTEGER
  |  STRING
  |  IDENTIFIER
  |  '(' expr ')'
  ;

其中 ANTLR 没有问题（即不再有左递归）。