151

我过去曾在各种项目中使用过 lex 和 yacc（通常是 bison），通常是翻译器（例如流入 EDA 应用程序的 EDIF 子集）。此外，我不得不支持基于 lex/yacc 语法的代码，这些语法可以追溯到几十年前。因此，尽管我不是专家，但我知道如何使用这些工具。

过去我在各种论坛上看到过关于 Antlr 的正面评价，我很好奇我可能遗漏了什么。因此，如果您两者都使用过，请告诉我 Antlr 中哪个更好或更高级。我目前的限制是我在 C++ 商店工作，我们发布的任何产品都不会包含 Java，因此生成的解析器必须遵循该规则。

4

5 回答 5

151

更新/警告：这个答案可能已经过时了！

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

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

ANTLR 完全无法按原样处理这种语法。要使用 ANTLR（或任何其他 LL 解析器生成器），您需要将此语法转换为非左递归的语法。但是，Bison 对这种形式的语法没有问题。您需要将 '+' 和 '-' 声明为左关联运算符，但这并不是左递归的严格要求。一个更好的例子可能是调度：

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

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

请注意，theexpr和actuals规则都是左递归的。这在代码生成时会产生更有效的 AST，因为它避免了对多个寄存器和不必要的溢出的需要（左倾树可以折叠，而右倾树不能）。

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

于 2008-10-17T16:50:10.670 回答
125

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

通常，长期使用 LALR 语法的人会发现使用 LL 语法更加困难，反之亦然。这并不意味着语法或工具本质上更难使用。您发现哪种工具更容易使用将主要归结为对语法类型的熟悉程度。

就优势而言，LALR 语法在某些方面比 LL 语法具有优势，在其他方面 LL 语法比 LALR 语法具有优势。

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

ANTLR 生成递归下降解析器，这意味着“处理逻辑”包含在解析器的代码中，因为语法的每个产生式规则都由解析器代码中的一个函数表示。回报是通过阅读其代码更容易理解解析器在做什么。此外，递归下降解析器通常比表驱动解析器更快。但是，对于非常复杂的语言，代码占用空间会更大。这是 1960 年代和 1970 年代的一个问题。那时，由于硬件限制，只有相对较小的语言（例如 Pascal）以这种方式实现。

ANTLR 生成的解析器通常在 10.000 行代码左右，甚至更多。手写递归下降解析器通常在同一个球场。Wirth 的 Oberon 编译器可能是最紧凑的编译器，大约 4000 行代码，包括代码生成，但 Oberon 是一种非常紧凑的语言，只有大约 40 条生产规则。

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

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

于 2009-12-14T11:41:17.783 回答
38

ANTLR 的几个优点：

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

我的 .02$

于 2009-05-22T13:46:57.823 回答
10

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

于 2008-12-02T01:19:31.077 回答
10
  • Bison 和 Flex 会导致更小的内存占用，但您没有图形 IDE。
  • antlr 使用更多内存，但您有 antlrworks，一个图形 IDE。

Bison/Flex 内存使用量通常为 MB 左右。与 antlr 进行对比——假设它为要解析的文件中的每个标记使用 512 字节的内存。400 万个令牌，而您在 32 位系统上的虚拟内存不足。

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

于 2012-05-31T10:09:59.997 回答