yacc/byacc/bison和lex/flex的适当用法

Question

我阅读的大多数与这些工具相关的帖子通常建议使用其他方法来获得相同的效果。例如，提到这些工具的问题通常至少有一个答案包含以下内容之一：

• 使用boost库（插入适当的boost库）
• 不要创建DSL使用（插入喜欢的脚本语言）
• Antlr更好

---

假设开发人员...

• ...熟悉C语言
• ...知道至少一种脚本语言（例如Python、Perl等）
• ...几乎每个项目都必须编写一些解析代码

---

因此，我的问题是：

• 哪些情况适合使用这些工具？
• 是否存在任何（合理的）情况，没有比yacc和lex（或其派生物）更好的解决方案来解决问题？
• 在实际解析问题中，有多少次可以预计会遇到yacc和lex的任何缺点，这些缺点通过更近期的解决方案更好地解决？
• 对于尚未熟悉这些工具的开发人员而言，值得投资时间学习它们的语法/习惯用法吗？这些工具与其他解决方案相比如何？

- bpw1621

Answer 1

lex/yacc及其衍生工具如此普遍的原因在于它们存在的时间比其他工具更长，它们在文献中的覆盖范围更广，而且它们传统上随Unix操作系统一起提供。这与它们与其他词法分析器和解析器生成器工具的比较关系很小。

无论选择哪种工具，学习曲线总是会很大。因此，一旦你使用了某个工具几次并对其使用相对舒适，你不太可能愿意承担学习另一个工具的额外努力。这是很自然的。

此外，在20世纪60年代末和70年代初创造lex/yacc时，硬件限制对解析构成了严峻挑战。Yacc使用的基于表的LR解析方法当时是最合适的，因为它可以通过使用相对较小的通用程序逻辑和将状态保存在磁带或磁盘上的文件中来实现小内存占用。代码驱动的解析方法（例如LL）具有更大的最小内存占用量，因为解析器程序的代码本身表示语法，因此它需要完全适合RAM以执行，并在RAM中保留状态。

当内存变得更加充裕时，许多研究都致力于不同的解析方法，例如LL和PEG以及如何使用这些方法构建工具。这意味着许多在lex/yacc系列之后创建的替代工具使用不同类型的语法。然而，切换语法类型也需要很大的学习曲线。一旦你熟悉一种语法类型，例如LR或LALR语法，你就不太可能想要切换到使用另一种语法类型的工具，例如LL语法。

总体而言，lex/yacc工具族通常比更近期的工具更为基础，后者通常具有复杂的用户界面来图形化地可视化语法和语法冲突，甚至通过自动重构来解决冲突。

因此，如果你没有任何解析器工具的先前经验，如果你必须学习新工具，那么你应该考虑其他因素，例如语法和冲突的图形可视化、自动重构、良好文档的可用性、生成的词法分析器/解析器可以输出的语言等等。不要仅仅因为“这是每个人似乎都在使用的”而选择任何工具。

以下是我能想到使用lex/yacc或flex/bison的原因：

• 开发人员已经熟悉lex/yacc或flex/bison
• 开发人员最熟悉和舒适的是LR/LALR语法
• 开发人员有很多涵盖lex/yacc的书籍，但没有涵盖其他工具的书籍
• 开发人员即将获得一份工作机会，并被告知lex/yacc技能将增加他的就业机会
• 开发人员无法从项目成员/利益相关者那里获得使用其他工具的支持
• 环境中已安装了lex/yacc，并且由于某种原因不可行安装其他工具

- Jim Barker

---

这个答案会更好，如果将缩写/首字母缩略词（LL/LR/PEG/LALR）进行扩展。 - user3003999

Answer 2

是否值得学习这些工具，主要取决于您编写多少解析代码，或者您对编写该类代码的兴趣程度。我经常使用它们，并发现它们非常有用。

您使用的工具并没有像许多人所说的那样有很大差别。对于我需要处理的约95%输入，它们之间的差异很小，因此最好的选择只是我最熟悉和舒适的那个工具。

当然，lex 和 yacc 会产生（并要求您在其中编写操作） C（或C ++）代码。如果您不习惯使用它们，则使用和生成您喜欢的语言（例如Python或Java）的工具无疑是更好的选择。我个人不建议尝试使用自己不熟悉或不舒服的语言来使用这样的工具。特别是，如果您在操作中编写出现编译器错误的代码，则可能无法从编译器中获得比通常更少的帮助以跟踪问题，因此您真正需要熟悉该语言，以仅通过最小的提示即可识别出编译器检测到的问题。

- Jerry Coffin

Answer 3

在以前的项目中，我需要一种能够轻松让相对非技术人员使用的方式来生成任意数据的查询的方法。这些数据是CRM类型的（例如名字、姓氏、电子邮件地址等），但是它们需要针对多个具有不同模式的数据库进行操作。

因此，我开发了一个小型DSL来指定查询（例如[FirstName]='Joe' AND [LastName]='Bloggs'将选择所有名为“Joe Bloggs”的人）。它还有一些更复杂的选项，例如“optedout(medium)”语法，它将选择所有已选择退出接收特定媒介（电子邮件、短信等）消息的人。还有“ingroup(xyz)”将选择特定组中的所有人等。

基本上，它允许我们指定像“ingroup('GroupA') and not ingroup('GroupB')”这样的查询，这将被转换为类似于以下的SQL查询：

SELECT
    *
FROM
    Users
WHERE
    Users.UserID IN (SELECT UserID FROM GroupMemberships WHERE GroupID=2) AND
    Users.UserID NOT IN (SELECT UserID GroupMemberships WHERE GroupID=3)

正如您所见，这些查询并不是尽可能高效的，但我想这就是机器生成的结果。

我没有使用flex/bison，但我确实使用了一个解析器生成器（名称我暂时想不起来了...）

- Dean Harding

Answer 4

我认为避免创建新语言来支持特定领域语言是一个相当好的建议。花时间用现有的语言并加入领域功能会更好。

如果你试图为其他原因创建新语言，比如研究语言设计，那么这些工具已经有点过时了。像antlr这样的新生成器，甚至像ML这样的新实现语言，使语言设计变得更加容易。

如果有充分的理由使用这些工具，那可能是因为它们的传统。你可能已经有了一个需要增强的语言框架，而这个框架已经在这些工具中实现了。你也可能从大量关于这些旧工具的教程信息中受益，而对于实现语言的更新和更流畅的方法，这方面的资料就不那么丰富了。

- SingleNegationElimination

Answer 5

我们在办公室里实现了一整个编程语言。我们用它来做这件事。我认为它旨在提供一种快速简便的方法来编写解释器。你可以想象使用它们来编写几乎任何类型的文本解析器，但很多时候要么A）自己快速编写更容易，要么B）需要比它们提供的更多的灵活性。

- jdizzle