13

正如删除左递归中所解释的，有两种方法可以删除左递归。

  • 使用一些过程修改原始语法以删除左递归
  • 原来写的文法没有左递归

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

  • 实际上，在 ANTLR 中去除左递归有多严重？这是使用 ANTLR 的亮点吗？或者，在 ANTLR 社区中没有人关心它？
  • 我喜欢 AST 生成 ANTLR 的想法。在快速简便地获得 AST 方面，哪种方法（在 2 种删除左递归方法中）更可取？

添加

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

E -> E + T|T
T -> T * F|F
F -> 整数 | (五)

左递归删除后，我得到以下一个

E -> TE'
E'-> 空 | + TE'
T -> 英尺'
T'-> 空 | *英尺'

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

语法 T；

选项 {
    语言=Python；
}

开始返回 [值]
   : e {$value = $e.value};
e 返回 [值]
   : EP  
     {
       $value = $t.value
       如果 $ep.value != 无：
         $value += $ep.value
     }
   ;
ep 返回 [值]
   ：{$值=无}
   | '+' tr = ep
     {
       $value = $t.value
       如果 $r.value != 无：
            $value += $r.value
     }
   ;
t 返回 [值]
  : f tp
    {
      $value = $f.value
      如果 $tp.value != 无：
        $value *= $tp.value
    }
  ;
tp 返回 [值]
  ：{$值=无}
  | '*' fr = tp
    {
      $value = $f.value;
      如果 $r.value != 无：
        $value *= $r.value
    }
  ;
f 返回 [int 值]
  : INT {$value = int($INT.text)}
  | '('e')' {$value = $e.value}
  ;

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

5 回答 5

12

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

parameter_list: parameter
              | parameter_list ',' parameter
              ;

由于您不关心参数的优先级或关联性之类的东西，因此很容易将其转换为右递归，但会增加额外的产生式：

parameter_list: parameter more_params
              ;

more_params:
           | ',' parameter more_params
           ;

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

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

于 2010-06-08T18:15:08.607 回答
6

实际上，在 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 解析器的初步近似，仅用于有关此问题的演示目的。其中有明显的错误。）

于 2010-06-08T18:11:23.197 回答
3

我不能代表 ANTLR，但总的来说，消除形式左递归的步骤：

A -> A B
  -> B

是将其更改为：

A -> B+

（注意B必须至少出现一次）

或者，如果 ANTLR 不支持 Kleene 闭包，您可以执行以下操作：

A -> B B'

B' -> B B'
   ->

如果您提供有冲突的规则示例，我可以提供更好、更具体的答案。

于 2010-06-08T18:15:36.993 回答
1

如果您正在编写语法，那么您当然会尝试编写它以避免特定解析器生成器的陷阱。

通常，根据我的经验，我会得到一些感兴趣的（遗留）语言的参考手册，它已经包含语法或铁路图，它就是这样。

在这种情况下，从语法中删除几乎所有左递归都是手动完成的。左递归删除工具没有市场，如果你有一个，它将专门用于与你所拥有的语法不匹配的语法语法。

在许多情况下，进行这种移除主要是一件汗水的事情，而且通常不会有很多事情。因此，通常的方法是拿出你的语法刀并使用它。

我不认为你如何删除左递归会改变 ANTLR 获取树的方式。您必须先进行左递归删除，否则 ANTLR（或您正在使用的任何 LL 解析器生成器）根本不会接受您的语法。

我们当中有些人不希望解析器生成器对我们可以为上下文无关语法编写的内容施加任何严格的限制。在这种情况下，您想使用 GLR 解析器生成器之类的东西，它可以轻松处理左递归或右递归。不通情理的人甚至可以坚持自动生成 AST，而语法编写者不费吹灰之力。有关可以两者兼得的工具，请参阅DMS Software Reengineering Toolkit。

于 2010-06-08T17:55:59.253 回答
1

这只是正交相关的，但我刚刚发表了一篇关于一种新的解析方法的论文的预印本，我称之为“pika 解析”（cf packrat parsing），它直接处理左递归语法，而不需要重写规则。

https://arxiv.org/abs/2005.06444

于 2020-05-14T04:39:48.120 回答