Antlr 的优点（相对于 lex/yacc/bison）[关闭]

StackOverflow https://stackoverflow.com/questions/212900

  •  03-07-2019
  •  | 
  •  

题

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

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

有帮助吗？

解决方案

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

一个主要区别是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更容易使用。

其他提示

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解析器，这对你没有帮助。简单地从LALR切换到LL以利用ANTLRworks可能是值得的，但对于某些人来说，切换语法类型可能是一种非常痛苦的经历。换句话说：YMMV。

ANTLR 的几个优点：

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

我的 .02$

ANTRL的另一个优点是你可以使用 ANTLRWORKS ，虽然我不能说这是一个严格的优势，因为其他发电机也可能有类似的工具。

  • Bison 和 Flex 会占用更小的内存，但没有图形 IDE。
  • antlr 使用更多内存，但您有 antlrworks，一个图形 IDE。

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top