logo标签列表

Antlr的优势（与lex/yacc/bison相比）

c++antlryaccbison
157

我过去在各种项目中使用了lex和yacc（通常更常用的是bison），通常是用于翻译器（例如将EDIF子集流式传输到EDA应用程序中）。此外，我不得不支持基于lex/yacc语法几十年前编写的代码。因此我知道这些工具的使用方法，但并不是专家。

我曾经在各个论坛中看到过关于Antlr的积极评论，我很好奇我可能错过的东西。所以如果你两者都使用过，请告诉我Antlr的优点或更高级的功能。我的当前限制是我在一个C++商店工作，任何我们发布的产品都不包括Java，因此生成的解析器必须遵循该规则。

5个回答
154

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

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

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

ANTLR无法按原样处理此语法。 要使用ANTLR（或任何其他LL解析器生成器），您需要将此语法转换为不是左递归的内容。 但是，Bison没有问题处理这种形式的语法。 您需要将“+”和“-”声明为左结合运算符，但这不是左递归所必需的。 更好的例子可能是dispatch：

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

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

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

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

5
您认为Antlr的最大、可能是唯一的优势是它在构建阶段生成的s-r和r-r等错误更少吗？我打算尝试一下，但最终可能还是会坚持用我熟悉的工具... - Don Wakefield
3
没错，就是这样。 :-) 我并不太同意普遍观点认为ANTLR比Bison更容易，所以我认为我会支持你的决定。 - Daniel Spiewak
2
“actuals”规则是否需要第二条规则来指示简单的“expr”是实际参数？否则，解释得很好。 - Jonathan Leffler
9
最近我发现了一条10年前的评论，虽然时间有点久远，但它对输出做出了一个合理的观察：http://compilers.iecc.com/comparch/article/98-11-040 ：“ANTLR / PCCTS是LL类型的，这使得语法编写更加困难，但生成的代码易读。 Yacc则是LALR类型的（当然您知道），这使得语法编写更容易，但生成的代码可能像象形文字一样难以阅读。” - Don Wakefield
79
我刚刚完成了ANTLR下一个版本v3.4的直接左递归支持。它处理LR表达式规则以及类似于C声明符规则等内容。 :) - Terence Parr
显示剩余4条评论
134
YACC/Bison与ANTLR之间最显著的区别是它们可以处理的语法类型不同。 YACC/Bison处理LALR文法，而ANTLR处理LL文法。
通常，长期使用LALR文法的人会发现使用LL文法更加困难，反之亦然。这并不意味着文法或工具本质上更难处理。你觉得哪个工具更容易使用将主要取决于你对文法类型的熟悉程度。
就优势而言，LALR文法在某些方面比LL文法更有优势，而LL文法在其他方面则比LALR文法更有优势。
YACC/Bison生成表驱动解析器，这意味着“处理逻辑”包含在解析程序的数据中，而不是解析器的代码中。回报是即使是非常复杂的语言的解析器也具有相对较小的代码占用空间。这在20世纪60年代和70年代时期更为重要。表驱动解析器生成器可以追溯到这个时期，当时小的代码占用空间是一个主要需求。
ANTLR生成递归下降解析器，这意味着“处理逻辑”包含在解析器的代码中，因为文法的每个产生式规则都由解析器代码中的一个函数表示。回报是通过阅读代码更容易理解解析器在做什么。此外，递归下降解析器通常比表驱动解析器快。但是对于非常复杂的语言，代码占用空间将更大。这在20世纪60年代和70年代时是一个问题。由于硬件限制，当时只实现了相对较小的语言（例如Pascal）。
ANTLR生成的解析器通常在10,000行以上。手写的递归下降解析器通常也在同样水平。Wirth的Oberon编译器可能是最紧凑的编译器之一，其中包括约4000行代码和代码生成，但Oberon是一种非常简洁的语言，只有约40个产生式规则。

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

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

6
我喜欢它，因为它解释了不同机制背后的历史，使人们能够立即理解。 - zinking
40

ANTLR的几个优点：

  • 可以输出多种语言的解析器 - 运行生成的解析器不需要Java。
  • 出色的GUI使语法调试变得容易（例如，您可以在GUI中直接看到生成的AST，不需要额外的工具）
  • 生成的代码实际上是可读的（这是ANTLR的目标之一），并且它生成LL解析器无疑有助于此方面。
  • 终端符号的定义也是无上下文限制的（与（f）lex中的正则表达式相反） - 因此允许例如定义包含正确闭合括号的终端符号

我的.02$

11

ANTLR 的另一个优点是你可以使用 ANTLRWORKS，虽然我不能说这是一个绝对的优势，因为其他生成器也可能有类似的工具。

另一个 ANTLR 的好处是它可以使用 ANTLRWORKS 工具，尽管我不能说这是一个绝对的优势，因为其他生成器也可能有类似的工具。请注意保留原文中的 HTML 标签。
11
  • Bison和Flex的内存占用较小，但是没有图形化IDE。
  • antlr的内存占用较大，但是有antlrworks，一个图形化IDE。

Bison/Flex的内存使用通常为1兆字节左右。与之相比，假设要解析的文件中每个标记令牌使用512字节的内存，则在32位系统上，若有400万标记令牌，就会超出虚拟内存。

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

7
我很好奇。你能指出关于每个标记消耗512字节内存的文档吗？我不记得看到过这样的讨论。我的谷歌关键词选择也没有给我满意的答案... - Don Wakefield
3
你是在讨论生成解析器时解析器生成器的内存占用，还是在讨论源语言输入进行解析时生成的解析器的内存占用？语法中数百万个标记绝对不可取。如果你认真尝试出售这样的想法，你应该被关进精神病院。至于解析器本身的输入文件，可能会有一些情况下这些文件包含极大量的标记，但大多数语言都是模块化的，你不需要在单个文件中解析整个输入，各个模块更小。 - trijezdci
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接