budshome (blog: 芽之家) shared the aphorism --
为何天意总让年轻人承载悲痛?我不知道。但我想年龄会加深所有的情感,包括悲痛。 -- 电影《利刃出鞘》

[Rust] Rust 中的解析器组合因子(parser combinators)

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

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。现在让我们分析下这个正则表达式的失败之处,其它复杂庞大的正则表达式,也是类似地。

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

正则表达式,有着内在的问题。对我们来说,这意味着只能使用简短的表达。作者将它们专门用于 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 组合了三个解析器:adddonesearch。它尝试从最左边开始,应用这些解析器中的每一个,直到一个成功为止。

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

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 类型,所以它的构造函数仍然是 ErrOk

  • 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))。

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

  • 请密切注意空格,这可能有点棘手。尤其是我们不知道 nom 库中的自动化标记选项时。
  • 查阅和您正在使用的 nom 库版本对应的文档,特别是选择一个组合器章节(注意!目录中指向组合器的宏版本,而不是函数版本)。
  • 如果你愿意的话,你可以查看这个极速编写的代码,它激发了本篇博文的灵感。代码的作者是 Chris Höppner 和 Jonn Mostovoy。

如果解析过程不是你产品或者你开发库的主要目标,那么解析器组合因子很可能对你的任务有足够的表现力和可执行力。我们希望你喜欢这篇文章,并且用解析器组合因子快乐地做解析。

谢谢您的阅读。

原文链接:Parser combinators in Rust


Rust 生态与实践

Related Articles

  1. [WebAssembly] Rust 和 Wasm 的融合,使用 yew 构建 WebAssembly 博客应用的体验报告
  2. [Rust] Rust 官方周报 399 期(2021-07-14)
  3. [WebAssembly] Rust 和 Wasm 的融合,使用 yew 构建 web 前端(5)- 构建 HTTP 请求、与外部服务器通信的两种方法
  4. [Rust] Rust 官方周报 398 期(2021-07-07)
  5. [Rust] Rust 官方周报 397 期(2021-06-30)
  6. [Rust] Rust 官方周报 396 期(2021-06-23)
  7. [Rust] Rust 官方周报 395 期(2021-06-16)
  8. [Rust] Rust 1.53.0 明日发布,关键新特性一瞥
  9. [Rust] 使用 tide、handlebars、rhai、graphql 开发 Rust web 前端(3)- rhai 脚本、静态/资源文件、环境变量等
  10. [Rust] 使用 tide、handlebars、rhai、graphql 开发 Rust web 前端(2)- 获取并解析 GraphQL 数据
  11. [Rust] 使用 tide、handlebars、rhai、graphql 开发 Rust web 前端(1)- crate 选择及环境搭建
  12. [Rust] Rust 官方周报 394 期(2021-06-09)
  13. [Rust] Rust web 前端库/框架评测,以及和 js 前端库/框架的比较
  14. [WebAssembly] Rust 和 Wasm 的融合,使用 yew 构建 web 前端(4)- 获取 GraphQL 数据并解析
  15. [WebAssembly] Rust 和 Wasm 的融合,使用 yew 构建 web 前端(3)- 资源文件及小重构
  16. [WebAssembly] Rust 和 Wasm 的融合,使用 yew 构建 WebAssembly 标准的 web 前端(2)- 组件和路由
  17. [WebAssembly] Rust 和 Wasm 的融合,使用 yew 构建 WebAssembly 标准的 web 前端(1)- 起步及 crate 选择
  18. [Rust] Rust 官方周报 393 期(2021-06-02)
  19. [Rust] Rust 官方周报 392 期(2021-05-26)
  20. [Rust] Rust 中,对网址进行异步快照,并添加水印效果的实践
  21. [Rust] Rust 官方周报 391 期(2021-05-19)
  22. [Rust] Rust,风雨六载,砥砺奋进
  23. [Rust] 为什么我们应当将 Rust 用于嵌入式开发?
  24. [Rust] Rust 官方周报 390 期(2021-05-12)
  25. [Rust] Rust + Android 的集成开发设计
  26. [Rust] Rust 1.52.1 已正式发布,及其新特性详述
  27. [Rust] 让我们用 Rust 重写那些伟大的软件吧
  28. [Rust] Rust 1.52.0 已正式发布,及其新特性详述
  29. [Rust] Rust 官方周报 389 期(2021-05-05)
  30. [GraphQL] 基于 actix-web + async-graphql + rbatis + postgresql / mysql 构建异步 Rust GraphQL 服务(4) - 变更服务,以及小重构
  31. [Rust] Rust 1.52.0 稳定版预发布测试中,关键新特性一瞥
  32. [Rust] Rust 生态中,最不知名的贡献者和轶事
  33. [Rust] Rust 基金会迎来新的白金会员:Facebook
  34. [Rust] Rustup 1.24.1 已官宣发布,及其新特性详述
  35. [Rust] Rust 官方周报 388 期(2021-04-28)
  36. [Rust] Rust 官方周报 387 期(2021-04-21)
  37. [GraphQL] 构建 Rust 异步 GraphQL 服务:基于 tide + async-graphql + mongodb(4)- 变更服务,以及第二次重构
  38. [Rust] Rustup 1.24.0 已官宣发布,及其新特性详述
  39. [Rust] basedrop:Rust 生态中,适用于实时音频的垃圾收集器
  40. [Rust] Rust 编译器团队对成员 Aaron Hill 的祝贺
  41. [Rust] Jacob Hoffman-Andrews 加入 Rustdoc 团队
  42. [机器人] 为什么应将 Rust 引入机器人平台?以及机器人平台的 Rust 资源推荐
  43. [Rust] rust-lang.org、crates.io,以及 docs.rs 的管理,已由 Mozilla 转移到 Rust 基金会
  44. [Rust] Rust 官方周报 386 期(2021-04-14)
  45. [Rust] Rust 编译器(Compiler)团队 4 月份计划 - Rust Compiler April Steering Cycle
  46. [GraphQL] 基于 actix-web + async-graphql + rbatis + postgresql / mysql 构建异步 Rust GraphQL 服务(3) - 重构
  47. [Rust] 头脑风暴进行中:Async Rust 的未来熠熠生辉
  48. [GraphQL] 基于 actix-web + async-graphql + rbatis + postgresql / mysql 构建异步 Rust GraphQL 服务(2) - 查询服务
  49. [GraphQL] 基于 actix-web + async-graphql + rbatis + postgresql / mysql 构建异步 Rust GraphQL 服务 - 起步及 crate 选择
  50. [Rust] Rust 2021 版本特性预览,以及工作计划
  51. [Rust] Rust 用在生产环境的 42 家公司
  52. [Rust] 构建最精简的 Rust Docker 镜像
  53. [Rust] Rust 官方周报 385 期(2021-04-07)
  54. [Rust] 使用 Rust 做异步数据采集的实践
  55. [Rust] Android 支持 Rust 编程语言,以避免内存缺陷
  56. [Rust] Android 平台基础支持转向 Rust
  57. [Rust] Android 团队宣布 Android 开源项目(AOSP),已支持 Rust 语言来开发 Android 系统本身
  58. [Rust] RustyHermit——基于 Rust 实现的下一代容器 Unikernel
  59. [Rust] Rustic:完善的纯粹 Rust 技术栈实现的国际象棋引擎,多平台支持(甚至包括嵌入式设备树莓派 Raspberry Pi、Buster)
  60. [Rust] Rust 迭代器(Iterator trait )的要诀和技巧
  61. [Rust] 使用 Rust 极致提升 Python 性能:图表和绘图提升 24 倍,数据计算提升 10 倍
  62. [Rust] 【2021-04-03】Rust 核心团队人员变动
  63. [Rust] Rust web 框架现状【2021 年 1 季度】
  64. [Rust] Rust 官方周报 384 期(2021-03-31)
  65. [Rust] Rust 中的解析器组合因子(parser combinators)
  66. [生活] 毕马威(KPMG)调查报告:人工智能的实际采用,在新冠疫情(COVID-19)期间大幅提升
  67. [Python] HPy - 为 Python 扩展提供更优秀的 C API
  68. [Rust] 2021 年,学习 Rust 的网络资源推荐(2)
  69. [Rust] 2021 年,学习 Rust 的网络资源推荐
  70. [生活] 况属高风晚,山山黄叶飞——彭州葛仙山露营随笔
  71. [Rust] Rust 1.51.0 已正式发布,及其新特性详述
  72. [Rust] 为 Async Rust 构建共享的愿景文档—— Rust 社区的讲“故事”,可获奖
  73. [Rust] Rust 纪元第 382 周最佳 crate:ibig 的实践,以及和 num crate 的比较
  74. [Rust] Rust 1.51.0 稳定版本改进介绍
  75. [Rust] Rust 中将 markdown 渲染为 html
  76. [生活] 国民应用 App 的用户隐私数据窥探
  77. [GraphQL] 构建 Rust 异步 GraphQL 服务:基于 tide + async-graphql + mongodb(3)- 重构
  78. [GraphQL] 构建 Rust 异步 GraphQL 服务:基于 tide + async-graphql + mongodb(2)- 查询服务
  79. [GraphQL] 构建 Rust 异步 GraphQL 服务:基于 tide + async-graphql + mongodb(1)- 起步及 crate 选择
  80. [Rust] Rust 操控大疆可编程 tello 无人机

Topics

rust(80)

graphql(17)

rust-官方周报(17)

webassembly(15)

async-graphql(9)

wasm(9)

rust-官方博客(8)

yew(8)

tide(7)

rust-web(7)

this-week-in-rust(6)

mysql(5)

rbatis(5)

android(4)

actix-web(4)

mongodb(3)

json-web-token(3)

jwt(3)

cargo(3)

技术延伸(3)

rust-wasm(3)

trunk(3)

handlebars(3)

rhai(3)

用户隐私(2)

学习资料(2)

python(2)

ai(2)

人工智能(2)

postgresql(2)

rust-compiler(2)

rust-基金会(2)

rust-foundation(2)

rustup(2)

rust-toolchain(2)

rust-工具链(2)

rust-游戏开发(2)

rust-区块链(2)

graphql-client(2)

rust-game(2)

tello(1)

drone(1)

无人机(1)

隐私数据(1)

markdown(1)

html(1)

crate(1)

async(1)

异步(1)

旅游(1)

不忘生活(1)

葛仙山(1)

hpy(1)

python-扩展(1)

正则表达式(1)

解析器组合因子(1)

组合器(1)

regular-expression(1)

parser-combinator(1)

regex(1)

官方更新(1)

rust-工作招聘(1)

rust-技术资料(1)

rust-周最佳-crate(1)

rust-web-框架(1)

rust-web-framework(1)

rust-核心团队(1)

rust-core-team(1)

rust-language-team(1)

pyo3(1)

rust-python-集成(1)

python-性能改进(1)

迭代器(1)

iterator-trait(1)

国际象棋(1)

chess(1)

游戏引擎(1)

game-engine(1)

虚拟化(1)

unikernel(1)

rustyhermit(1)

linux(1)

virtualization(1)

sandboxing(1)

沙箱技术(1)

数据采集(1)

异步数据采集(1)

docker(1)

镜像(1)

生产环境(1)

rust-评价(1)

rust-2021-edition(1)

rust-2021-版本(1)

graphql-查询(1)

vision-doc(1)

愿景文档(1)

代码重构(1)

steering-cycle(1)

方向周期(1)

隐私声明(1)

机器人(1)

robotics(1)

rustdoc(1)

rust-编译器(1)

实时音频(1)

real-time-audio(1)

变更服务(1)

mutation(1)

查询服务(1)

query(1)

rust-贡献者(1)

rust-轶事(1)

rust-稳定版(1)

rust-预发布(1)

rust-测试(1)

安全编程(1)

可信计算(1)

安全代码(1)

secure-code(1)

rust-android-integrate(1)

rust-embedded(1)

rust-嵌入式(1)

rust-生产环境(1)

rust-2021(1)

rust-production(1)

网页快照(1)

网页截图(1)

水印效果(1)

图片水印(1)

yew-router(1)

css(1)

web-前端(1)

wasm-bindgen(1)

区块链(1)

blockchain(1)

surf(1)

dotenv(1)

标识符(1)

rust-1.53.0(1)

rusthub(1)

Elsewhere

- Open Source
  1. github/zzy
  2. github/sansx
- Awesome Blog
  1. Sansx's Studio
  2. 曙光磁铁的博客
- Learning & Studying
  1. Rust 学习资料 - 芽之家