inator: 一个邪恶的解析库

您提供邪恶的计划；我们提供 -inator！

或者，可证明最优的零拷贝解析器与非确定性有限自动机

为什么？

可计算理论已经知道很久了，每个决策问题（任何有是/否答案的事情）都有一个独特的、可证明最优的有限自动机表示。这是正则表达式搜索器如grep背后的洞察力，但据我所知，任何超过决策问题的事情在理论上是不可优化的。

如何？

这个库使用与grep等工具相同的高级机制，但增加了一些额外的功能

给定一个如“在B之后解析A”或“将这个放在括号里”这样的规范（以及无限种类似的东西），我们写一个图，包含一组初始节点，一组接受节点和一些标记有输入字符的有向边。从这个，可计算理论的部分开始：我们可以将这个最小化到一个具有可证明的最小状态数量的图，它将告诉我们“这是有效的语法吗？”

然后，尽管我们不能证明优化您的代码，但我们让您编写函数，有效地搭车到我们刚刚创建的最优决策图。具体来说，每次您说“解析这个令牌”时，您都可以调用一个函数来处理到目前为止的数据，使用那个令牌，返回下一个状态。

最后，您可以将这个最优图转换为Rust源文件：我们不仅能够证明实现是最优的，而且可以利用Rust的二进制优化器使其运行得尽可能快。

整个过程看起来像什么？

令人惊讶的是，它看起来就像只是写下您想要的东西。这是“将这个放在括号里”的定义

pub fn parenthesized(p: Parser<char>) -> Parser<char> {
    ignore('(') + p + ignore(')')
}

所以，如果p是一个接受ABC的解析器，那么parenthesized(p)将接受(ABC)。就这么简单。

这里的关键思想是，解析器是数据，您可以像传递、修改和组合其他任何东西一样传递、修改和组合它们。

请参阅 example 文件夹，其中包含一个使用 inator 的自包含包的示例，该包从元组表示（()、(A,) 或 (A, B, C, ...)）读取字符，忽略空白字符。在该示例中，整个解析器可以定义在一行中，但我将其拆分开来以说明，首先，你可以这样做——你不需要一个一次性的巨型解析器——其次，为了尽可能详细地解释如何使用这个库。

还有什么其他酷炫的功能吗？

是的！由于我们实际上只是坐在决策问题自动机上，你可以取一个规范并将其反转，以生成无限个随机字符串流，这些字符串都保证可以正确解析。如果你正在编写一种语言，这意味着可以 自动生成所有可能的有效源文件。

而且，你猜对了，这也会编译成Rust源代码，所以你的属性测试可以非常有效。

为什么不尝试其他解析库呢？

请尝试其他解析库！这是 我最喜欢的，主要是因为它是纯Rust，没有宏，没有新语法，没有输入复制，解析器作为数据，自动输入生成，而且——嗯——我写了它，但我不太熟悉其他库，所以我不敢保证推荐这个库。

我的主要目标是个人工具，但它比我预期的要好得多，所以我非常希望看到你使用它并给出反馈！

致谢

首先，感谢 Haskell 的解析库（以及 UPenn 的 Haskell 课程）让我知道解析器甚至可以以这种方式工作。大部分语法都是受 Haskell 启发的。

其次，感谢 Rajeev Alur 和 Penn 的 CIS 262，他们正式向我介绍了非确定性有限自动机。

第三，感谢 Rust。