Antlr 的优点(与 lex/yacc/bison 相比)

我过去曾在各种项目中使用 lex 和 yacc (通常是 bison) ，通常是翻译程序(例如流入 EDA 应用程序的 EDIF 子集)。此外，我还必须支持基于几十年前的 lex/yacc 语法的代码。虽然我不是专家，但我知道怎么使用工具。

过去我在各种论坛上看到过关于 Antlr 的积极评论，我很好奇我可能会错过什么。所以如果你两种都用过请告诉我 Antlr 哪种更好或者更先进。我目前的约束条件是，我在一家 C + + 工厂工作，我们发布的任何产品都不包括 Java，因此产生的解析器必须遵循这一规则。

49203 次浏览
小开
最佳答案

更新/警告: 此答案可能已过期！

一个主要区别是 ANTLR 生成 LL (*)解析器，而 YACC 和 Bison 都生成 LALR 解析器。这是许多应用程序的一个重要区别，其中最明显的是操作符:

expr ::= expr '+' expr
| expr '-' expr
| '(' expr ')'
| NUM ;

ANTLR 完全不能按原样处理这种语法。要使用 ANTLR (或任何其他 LL 编译器编译程式) ，您需要将这种语法转换为非左递归的语法。然而，Bison 对这种形式的语法没有问题。您需要将’+’和’-’声明为左关联运算符，但是对于左递归并不严格要求这一点。一个更好的例子可能是派遣:

expr ::= expr '.' ID '(' actuals ')' ;


actuals ::= actuals ',' expr | expr ;

注意，expr和 actuals规则都是左递归的。当需要生成代码时，这会产生一个高效得多的 AST，因为它避免了多个寄存器和不必要的溢出(左倾树可以折叠，而右倾树不能)。

就个人口味而言，我认为 LALR 语法更容易构造和调试。缺点是您必须处理一些比较隐晦的错误，比如 shift-reduce 和(可怕的) reduce-reduce。这些是 Bison 在生成解析器时捕获的错误，因此它不会影响最终用户体验，但是它可以使开发过程更有趣一些。因为这个原因，ANTLR 通常被认为比 YACC/Bison 更容易使用。

小开

ANTRL 的另一个优势是您可以使用 蚂蚁，尽管我不能说这是一个严格的优势，因为其他生成器可能也有类似的工具。

小开

ANTLR 的一些优点:

  • 可以输出不同语言的解析器-运行生成的解析器不需要 Java。
  • Awesome GUI 使语法调试变得容易(例如，您可以在 GUI 中看到生成的 AST 的权利，不需要额外的工具)
  • 生成的代码实际上是人类可读的(这是 ANTLR 的目标之一) ，并且它生成 LL 解析器的事实在这方面肯定有所帮助。
  • 终端的定义也是与上下文无关的(与(f) lex 中的 regex 相反)——因此，例如，允许定义包含正确闭合括号的 终端机

我的0.02美元

小开

YACC/Bison 和 ANTLR 之间最显著的区别是这些工具可以处理的语法类型。YACC/Bison 处理 LALR 语法，ANTLR 处理 LL 语法。

通常，使用 LALR 语法很长时间的人会发现使用 LL 语法更困难，反之亦然。这并不意味着语法或工具在本质上更难使用。你觉得哪种工具更容易使用，主要取决于对语法类型的熟悉程度。

就优势而言，有些方面 LALR 文法优于 LL 文法，还有些方面 LL 文法优于 LALR 文法。

YACC/Bison 生成表驱动的解析器，这意味着“处理逻辑”包含在解析器程序的数据中，而不是包含在解析器的代码中。这样做的好处是，即使是用于非常复杂的语言的解析器也只占用相对较小的代码空间。这在20世纪60年代和70年代更为重要，当时硬件非常有限。表驱动的解析器生成器可以追溯到这个时代，小的代码占用是当时的主要需求。

ANTLR 生成递归下降解析器，这意味着“处理逻辑”包含在解析器的代码中，因为语法的每个产生规则都由解析器代码中的一个函数表示。这样做的好处是，通过阅读解析器的代码，可以更容易地理解解析器在做什么。此外，递归下降解析器通常比表驱动的解析器更快。但是，对于非常复杂的语言，代码占用将更大。这是上世纪六七十年代的一个问题。那时候，由于硬件的限制，只有像 Pascal 这样相对较小的语言是这样实现的。

ANTLR 生成的解析器通常在10.000行以上的代码附近。手写递归下降解析器通常大致相同。Wirth 的 Oberon 编译器可能是最紧凑的一个，包括代码生成在内的约4000行代码，但 Oberon 是一种非常紧凑的语言，只有大约40条生产规则。

正如已经有人指出的那样，ANTLR 的一大优点是图形化 IDE 工具 ANTLRworks。这是一个完整的语法和语言设计实验室。它可视化您的语法规则，因为您输入它们，如果它发现任何冲突，它将显示您的冲突是什么和什么原因。它甚至可以自动重构和解决冲突，如左递归。一旦有了无冲突的语法，就可以让 ANTLRworks 解析语言的输入文件，为您构建解析树和 AST，并在 IDE 中以图形方式显示该树。这是一个非常大的优势，因为它可以为您节省许多工作时间: 在开始编码之前，您将发现语言设计中的概念性错误！我没有发现任何这样的工具为 LALR 语法，似乎没有任何这样的工具。

即使对于那些不希望生成解析器而是手工编写解析器的人来说，ANTLRworks 也是语言设计/原型开发的一个很好的工具。很可能是现有的最好的工具。不幸的是，如果您想要构建 LALR 解析器，这对您没有帮助。仅仅为了利用 ANTLRworks 而从 LALR 切换到 LL 可能是值得的，但是对于一些人来说，切换语法类型可能是一个非常痛苦的经历。换句话说: YMMV。

小开
  • Bison 和 Flex 可以减少内存占用，但是没有图形化 IDE。
  • Antlr 使用更多的内存，但是您有 antlworks，一个图形化 IDE。

Bison/Flex 内存使用量通常是一个 mbyte 左右。与 antlr 相比，假设它对要解析的文件中的每个标记使用512字节的内存。400万个令牌，并且您在32位系统上的虚拟内存已经用完。

如果您希望解析的文件很大，antlr 可能会耗尽内存，因此如果您只想解析配置文件，那么它将是一个可行的解决方案。否则，如果要解析包含大量数据的文件，请尝试使用 Bison。


提交答案