[Rust] Rust 中的解析器组合因子（parser combinators）

2021-04-02 23:51:04+08:00 by - NiQin [blog: 泥芹]

💥 内容涉及著作权，均归属作者本人。若非作者注明，默认欢迎转载：请注明出处，及相关链接。

Summary: 正则表达式，有着内在的问题，这意味着只能使用简短的表达。现在，一个更好的解析方法正在成为主流，可用作所有流行语言的工作库，它被称为“析器组合因子（parser combinators）”，可满足 99% 的实际场景。解析器组合因子（parser combinators），是一种用高阶函数构造的，可组合计算的方法。如果解析过程不是你产品或者你开发库的主要目标，那么解析器组合因子很可能对你的任务有足够的表现力和可执行力。

Topics: rust 正则表达式解析器组合因子组合器 regular-expression parser-combinator regex

本文为翻译，原文题目是 Parser combinators in Rust。由英国布里斯托尔市的 doma 团队，于 2021 年 3 月 30 日（星期二）撰写。

内容提要

不使用正则表达式（regular expressions）做解析；
解析器组合因子（parser combinators），是一种用高阶函数构造的，可组合计算的方法。例如：
- many1(digit1)
- alt((tag("hello")，tag("sveiki")))
- pair(description, preceded(space0, tags))
解析器组合因子（parser combinators）易于使用，并且可快速高效地获得结果；
解析器组合因子可满足 99% 的实际场景。仅当，你开发库的唯一目标是解析过程时，才会不太适合（译注：是指实现偏复杂了）。

解析在计算中的担当

数据处理，是计算的支柱。要运行一个算法，首先，必须在内存中建立一些数据结构。然后，对数据结构进行填充，一般方法是获取一些原始数据，并将其加载到内存中。数据科学家处理原始数据时，要清理数据，并创建格式良好的数据集。然后由编程语言设计人员标记源代码文件，将它们解析为抽象语法树。最后， web 采集人员正确采集 HTML，并提取感兴趣的值。

通俗地讲，每个步骤都可以称为“解析（parsing）”。本篇文章讨论了如何快速完成完整地、可组合地，以及正确地解析。具体包括那些方面？

快速地解析，意味着从实用的角度考虑了数据转换的问题，不需要理论上的最优解。我们的目标是，尽可能地快速编写正确的解析器。
可组合解析，意味着实现的解析器，可能由“较小”的组件组成。这些“较小”的解析器组件，以后可以在“更大”的解析器中用作组件。
完整地解析，意味着输入数据将被完全使用。如果输入数据可能偏差或错误，开发者应在实现的解析器中对其进行编码，而不是调整输入数据。

那么，我们如何实现呢？我们先来谈谈什么是不应该做的。

忘记正则吧

“谢谢”已经近乎“消亡”的 Perl 语言的流行，整整一代计算机程序员都在徒劳地尝试用正则表达式解析非正则语言（译注：链接为 stackoverflow 站点 11 年前发表的热帖，是关于使用正则解析 HTML 的，被查阅次数超过 310 万次）。正则表达式，不过是有限状态自动机的编码。

有限状态自动机

箭头最上方的项，是关于字母字符的正则表达式。实心圆表示状态，如 q1 表示“接受状态”。箭头，则表示状态转换。

非确定的有限状态自动机，可以相当优雅地接受许多有意义的语言表达。经典的子是，正则表达式例不接受 “ab”、“aabb”、“aaabbb”……类似地，不能用正则表达式解决插入语的匹配难题，而需要使用最简单的堆栈机器模型。

堆栈机器模型

堆栈自动机，可以同时处于几种状态。没有转换状态，对任何输入都“视觉增强”。(@\* 将字符 '(' 与任何堆栈状态匹配；仅当堆栈为空时，ε@ε 在自动机到达 p 状态时即刻匹配。

因此，正则表达式远远不能提供足够的工具，以用来处理上下文无关语法。但是它们可能足够强大，可以清理数据或提取一些值。但是，为什么我们说您永远不应该使用它们呢？实用性原因！

让我们看看 Regex Cookbook 中的一个例子（来自于于 medium 站点），这样我们就晓得，这是一个在业界使用的实际案例。以下是作者提供的正则表达式之一：

^(((h..ps?|f.p):\/\/)?(?:([\w\-\.])+(\[?\.\]?)([\w]){2,4}|(?:(?:25[0-5]|2[0-4]\d|[01]?\d\d?)
\[?\.\]?){3}(?:25[0-5]|2[0-4]\d|[01]?\d\d?)))*([\w\/+=%&_\.~?\-]*)$

许多人都能从表面上理解这个正则表达式。似乎，这个正则表达式与链接有关，但即使我们求助于正则的自动化诠释（译注：一个正则表达式解释和测试站点），事情也没有变得更清楚。嗯，根据作者的说法，这个正则表达式应该检测“无效的” URL。现在让我们分析下这个正则表达式的失败之处，其它复杂庞大的正则表达式，也是类似地。

错误：不能匹配 https://ctflearn.com/（注意没有空格）。
需要外部标记，因此没有即插即用：不匹配 ␣https://ctflearn.com/（注意前导空格）。
外部标记，特定于此表达式：不匹配 https://ctflearn.com,（注意后面的逗号）。
修复它？不可能的：在每个可打印字符周围匹配可选字符，将使它从一个大的、可读性差的代码段，变成一个巨大的、完全不可读的代码段。你的大脑甚至半猜不出 h..ps 和 f.p 的半点含义。
它不能用于提取值。正则表示法不“将数据解析为数据结构”，他们只接受或拒绝字符串。因此，需要对它们的输出，进行额外的后续处理。

正则表达式，有着内在的问题。对我们来说，这意味着只能使用简短的表达。作者将它们专门用于 grep、find，以及 vim`。

现在，很高兴，一个更好的解析方法正在成为主流，可用作所有流行语言的工作库。从标题中可以猜到，它被称为“析器组合因子（Parser combinators）”。

可组合解析的逐步实现

遵循我们往期博客的精神，让我们来解决一些实际问题。考虑到完全地进行实践，您必须编写一个交互式 TODO 应用程序。它实现以下命令：

add ${some word}* ${some #hashtag}*（附加项 ID）
done ${some item ID}（将附加项 ID 标记为已解析）
search ${some word or some #hashtag}+（搜索，并返回匹配项 ID 列表）

让我们首先定义一个枚举，表示已解析的数据。省略了那些无聊的部分：

pub enum Entry {
    Done (Index),
    Add (Description, Vec<Tag>),
    Search (SearchParams),
}

现在，让我们使用 nom 库（译注：面向字节的、零拷贝的解析器组合因子库），享受富有表现力的、声明式的解析。它有宏 API，以及函数 API。由于在 v5 中，nom 库的宏 API 非常容易出错，因此我们将使用函数 API。并且，我们已经用 v6 测试过了。

我们将逐行解析命令。首先，声明一行的顶级解析；然后，遇到第一个解析器组合因子：alt。

pub fn command(input: &str) 
-> IResult<&str, Entry> { /* A */
    alt((done, add, search))(input) /* B */
}

在（A）中（译注：以下注释标记 A 的部分），我们声明的函数 command，是一个解析器。IResult 捕获解析的类型（本例中为 str&），以及输出数据结构（本例中为 Entry）。

在（B）中，我们使用 nom::branch::alt 组合了三个解析器：add、done 和 search。它尝试从最左边开始，应用这些解析器中的每一个，直到一个成功为止。

现在，让我们看看三个解析器中最简单的一个：

fn done(input: &str) -> IResult<&str, Entry> {
    let (rest, value) = preceded( /* A */
        pair(tag("done"), ws), /* B */
        many1(digit1) /* C */
    )(input)?; 
    Ok((
      rest,
      Entry::Done( /* D */
        Index::new( vec_to_u64(value) )
      ) 
    ))
}

我们直接看到的第一个组合因子是 preceded。它忽略解析（B），只保留（C）的输出。但（B）仍将接受输入！一般来说，它将两个计算组合成一个组合器，组合器将运行两个计算，返回第二个计算的结果。这和按顺序运行它们，是不一样的。因为这里我们建立了一个计算，我们稍后会运行它！

有趣的是，如果我们在编写 Haskell 代码，那么在解析器库（译注：参阅 Megaparsec 文档）中就找不到 preceded 组合器。这是因为，我们在上一段中所描述的，被称为“右应用箭头”，或者，正如 Ben Clifford 的精彩演讲“右侧的麻雀”中所说：

λ> :t (*>)
(*>) :: Applicative f => f a -> f b -> f b

另外两个组合因子，是相当一目了然的。pair 将解析器组合成一个序列，具有一个接收单个空格的 ws 解析器。ws 具有一个简单定义：one_of(" \t")。many1 至少重复一次 digit1 解析才能成功，其中 digit1 是在 nom 库中实现的。

现在，在确保我们的解析器可以被其他人使用方面，让我们对其理解做以巩固。

我们已经讨论过，要实现这一点，我们需要返回 IResult。我们要记住，IResult 仍然是一个 Result 类型，所以它的构造函数仍然是 Err 和 Ok：

Result 中的 Err 变量，通过 ? 修饰符构造，将通过解析（A）传递出现的任何潜在错误。
Result 中的 Ok 变量在（D）中构造，通过将 many1 输出（数值的动态数组），转换成一个无符号 64 位整数。转换用 vec_to_u64 函数完成的，为了简洁起见，这里省略了。

IResult<in, out> 中，Ok 值的具体形式是 Ok((rest: in, value: out))。其中 rest 是要解析的剩余输入，value 是解析器的输出结果。您可以看到（A）中 preceded 解析，遵循了完全相同的模式。

下面的部分，是一些更高级的解析器。关于在如何快速地使用解析器组合因子方面，它们将巩固您的知识：

fn add(input: &str) -> IResult<&str, Entry> {    
  let (rest, (d, ts)) = preceded( /* B */
    pair(tag("add"), ws),                     
    pair(description, preceded(space0, tags)) /* A */
  )(input)?;
  Ok( (
    rest,
    Entry::Add( Description::new(&d), ts )
  ) )
}

fn search(input: &str) -> IResult<&str, Entry> {
  let (rest, mash) = preceded(
    pair(tag("search"), ws),
    separated_list(
      tag(" "),
      alt((tag_contents, search_word)) /* C */
    )
  )(input)?;
  Ok((rest, mash_to_entry(mash)))
}

fn mash_to_entry(mash: Vec<SearchWordOrTag>) -> Entry /* D */
{ /* ... */ }

使用组合因子进行解析，是如此的简单明了，甚至很难找到需要澄清的东西，但这里有几个补充：

重复 preceded 步骤，将重点放在需要解析的数据上，请参见（A）和（B）中的绑定。
有时，您必须解析异构数据。根据我们的经验，最好的方法是：创建一个单独的数据类型，用来封装这种异构性（本例中为 SearchWordOrTag）。然后，在 alt 选项上,使用 separated_list 解析器，具体如（C）中所示。最后，当您有一个匹配的数组时，您可以根据需要，使用转换函数将其折叠成更整洁的数据结构（参见（D））。

帮助您开始舒适地熟悉这个令人惊讶的、基于组合因子的解析方法论方面，本文应该做了足够的指导。以下是一些结束前想法：