删除 ANTLR 中的左递归

正如中所解释的删除左递归 https://stackoverflow.com/questions/2652060/removing-left-recursion，有两种方法可以去除左递归。

• 使用某些程序修改原始语法以删除左递归
• 本来写语法就没有左递归

人们通常使用什么来通过 ANTLR 删除（不具有）左递归？我使用 flex/bison 作为解析器，但我需要使用 ANTLR。我唯一担心使用 ANTLR（或一般的 LL 解析器）是左递归删除。

• 从实际意义上讲，ANTLR 中删除左递归有多严重？这是使用 ANTLR 的一个障碍吗？或者，ANTLR 社区中没有人关心它？
• 我喜欢 ANTLR 的 AST 生成的想法。就快速、简单地获得 AST 而言，哪种方法（两种删除左递归方法中）更可取？

Added

我对以下语法做了一些实验。

E -> E + T|T
T -> T * F|F
F -> INT | ( E )
  

删除左递归后，我得到以下结果

E -> TE'
E' -> null | + TE'
T -> FT'
T' -> null | * FT'
  

我可以提出以下 ANTLR 表示。尽管它相对非常简单和直接，但似乎没有左递归的语法应该是更好的方法。

grammar T;

options {
    language=Python;
}

start returns [value]
   : e {$value = $e.value};
e returns [value]
   : t ep  
     {
       $value = $t.value
       if $ep.value != None:
         $value += $ep.value
     }
   ;
ep returns [value]
   : {$value = None}
   | '+' t r = ep 
     {
       $value = $t.value
       if $r.value != None:
            $value += $r.value
     }
   ;
t returns [value]
  : f tp 
    {
      $value = $f.value
      if $tp.value != None:
        $value *= $tp.value
    }
  ;
tp returns [value]
  : {$value = None}
  | '*' f r = tp 
    {
      $value = $f.value;
      if $r.value != None:
        $value *= $r.value
    }
  ;
f returns [int value]
  : INT {$value = int($INT.text)}
  | '(' e ')' {$value = $e.value}
  ;

INT :   '0'..'9'+ ;
WS: (' '|'\n'|'\r')+ {$channel=HIDDEN;} ;
  

考虑一个典型的参数列表：

parameter_list: parameter
              | parameter_list ',' parameter
              ;

由于您不关心优先级或与参数的关联性等任何内容，因此很容易转换为右递归，但代价是添加额外的产生式：

parameter_list: parameter more_params
              ;

more_params:
           | ',' parameter more_params
           ;

对于最严重的情况，你可能需要花一些时间在《龙之书》上。快速检查一下，这主要在第 4 章中介绍。

就严肃性而言，我很确定 ANTLR 根本不会接受包含左递归的语法，这会将其归入“绝对必要”类别。