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

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

  •  19-09-2019
  •  | 
  •  

题

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

  • 使用boost库（在此处插入适当的boost库）
  • 不要创建 DSL 使用（在此处插入最喜欢的脚本语言）
  • 安特尔比较好

假设开发商...

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

所以我的问题是：

  • 适合这些公用事业的适当情况是什么？
  • 是否有（合理的）情况，没有比Yacc和Lex（或衍生品）更好的问题替代方案？
  • 在实际解析问题中，人们期望有一次在YACC和LEX中遇到任何短暂的启动，而最近的解决方案可以更好地解决这些问题？
  • 对于尚不熟悉这些工具的开发人员而言，他们要花时间学习语法/成语值得吗？这些与其他解决方案相比如何？
有帮助吗？

解决方案

lex/yacc 和衍生工具今天看起来如此普遍的原因是它们比其他工具存在的时间要长得多，它们在文献中的覆盖率要高得多，而且它们传统上随 Unix 操作系统一起提供。它与它们与其他词法分析器和解析器生成器工具的比较关系不大。

无论您选择哪种工具，总会有一个显着的学习曲线。因此，一旦您使用某个工具几次并相对熟悉它的使用，您就不太可能愿意花费额外的精力来学习另一种工具。这是很自然的事。

此外，在 lex/yacc 创建的 20 世纪 60 年代末和 1970 年代初，硬件限制对解析提出了严峻的挑战。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，由于某种原因安装其他工具不可行

其他提示

是否值得学习这些工具将在很大程度上取决于您编写了多少解析代码，或者您对按照一般顺序编写更多代码的兴趣有多大。我已经使用过它们很多次，并且发现它们非常有用。

您使用的工具并没有像许多人想象的那样产生很大的影响。对于我必须处理的大约 95% 的输入，它们之间的差异很小，因此最好的选择就是我最熟悉和最舒服的。

当然，lex 和 yacc 生成（并要求您用 C（或 C++）编写操作。如果您对它们不满意，可以使用使用和生成您喜欢的语言的工具（例如Python 或 Java）无疑是更好的选择。就我而言，我不建议尝试将这样的工具与您不熟悉或不舒服的语言一起使用。特别是，如果您在产生编译器错误的操作中编写代码，那么在跟踪问题时，您从编译器获得的帮助可能会比平常少得多，因此您确实需要足够熟悉该语言才能识别问题只有关于编译器注意到哪里有问题的最小提示。

在之前的项目中，我需要一种能够以相对非技术人员易于使用的方式生成对任意数据的查询的方法。这些数据是 CRM 类型的内容（例如名字、姓氏、电子邮件地址等），但它旨在针对许多不同的数据库工作，所有数据库都具有不同的模式。

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

基本上，它允许我们指定诸如“ingroup('GroupA') 而不是 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，但我确实使用了解析器生成器（目前我已经忘记了它的名字......）

我认为避免创建新语言只是为了支持特定于领域的语言是一个很好的建议。采用现有语言并通过领域功能对其进行扩展将更好地利用您的时间。

如果您出于其他原因尝试创建一种新语言，也许是为了研究语言设计，那么这些工具就有点过时了。较新的生成器（例如 antlr），甚至较新的实现语言（例如 ML），使语言设计变得更加容易。

如果有充分的理由使用这些工具，那可能是因为它们的遗产。您可能已经有了需要增强的语言框架，并且已经在其中一个工具中实现了该框架。您还可能会受益于有关这些旧工具的大量教程信息，但没有为更新和更灵活的语言实现方式编写的语料库。

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

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