删除ANTLR中的左递归

Question

正如在删除左递归中所解释的,有两种方法可以删除左递归.

• 修改原始语法以使用某些过程删除左递归
• 最初编写语法不要有左递归

人们通常用什么来移除(没有)ANTLR的左递归？我使用flex/bison进行解析器,但我需要使用ANTLR.我唯一担心的是使用ANTLR(或普通的LL解析器)是去除递归.

• 实际上,在ANTLR中删除左递归有多严重？这是使用ANTLR的一个显示器吗？或者,在ANTLR社区中没有人关心它？
• 我喜欢AN生成AST的想法.在获得AST快速简便的方法方面,哪种方法(2中删除左递归方法)更可取？

添加

我用以下语法做了一些实验.

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;} ;

Answer 1

考虑类似典型参数列表的内容:

parameter_list: parameter
              | parameter_list ',' parameter
              ;

由于您不关心任何类似优先级或与参数关联的内容,因此转换为正确递归相当容易,但会增加额外的生产:

parameter_list: parameter more_params
              ;

more_params:
           | ',' parameter more_params
           ;

对于最严重的情况,您可能想花一些时间在龙书中.快速检查一下,主要在第4章中介绍.

至于严肃性,我很确定ANTLR根本不会接受包含左递归的语法,这会将其置于"绝对必要"范畴.

Answer 2

实际上，在 ANTLR 中去除左递归有多严重？这是使用 ANTLR 的阻碍吗？

我认为您对左递归有误解。它是语法的属性，而不是解析器生成器或解析器生成器与规范之间的交互的属性。当规则右侧的第一个符号等于与规则本身对应的非终结符时，就会发生这种情况。

要理解这里的固有问题，您需要了解递归下降 (LL) 解析器的工作原理。在 LL 解析器中，每个非终结符的规则由对应于该规则的函数实现。所以，假设我有这样的语法：

S -> A B
A -> a
B -> b

然后，解析器将（大致）如下所示：

boolean eat(char x) {
  // if the next character is x, advance the stream and return true
  // otherwise, return false
}

boolean S() {
  if (!A()) return false;
  if (!B()) return false;
  return true;
}

boolean A(char symbol) {
  return eat('a');
}

boolean B(char symbol) {
  return eat('b');
}

但是，如果我将语法更改为以下内容会发生什么？

S -> A B
A -> A c | null
B -> b

据推测，我希望这个语法代表一种语言，如c*b. LL 解析器中的相应函数如下所示：

boolean A() {
  if (!A()) return false;  // stack overflow!  We continually call A()
                           // without consuming any input.
  eat('c');
  return true;
}

所以，我们不能有左递归。将语法改写为：

S -> A B
A -> c A | null
B -> b

并且解析器更改如下：

boolean A() {
  if (!eat('c')) return true;
  A();
  return true;
}

（免责声明：这是我对 LL 解析器的基本近似，仅用于演示此问题的目的。其中有明显的错误。）