解析器组合子（Parser Combinators）把小型解析函数作为基本单元，通过高阶函数组合成更复杂的解析器，用来处理正则表达式（regex）不易表达的语法。从最基础的解析操作开始，逐步把简单的匹配逻辑拼接起来，形成能够分析嵌套结构的完整解析流程，而不是直接依赖现成的模式匹配工具。

字符串 "Hello, world!" 会被解析成一个对象：{ greeting: "Hello", who: "world" }。

Parser<T> 的类型定义是 (input: string) => [T, string]：它接收输入字符串，返回一个二元组，里面是解析出的 T 值和剩下的字符串。

例如，pInteger 处理 "10 20 30" 时，会在 "10" 之后切开，返回数字 10 和剩余字符串 " 20 30"。

接着看 "Hello 100"。依次用 pHello、pIgnoreWhitespace、pInteger 去解析，每个解析器都接着上一个剩下的字符串继续：pHello 先返回 "Hello" 和 " 100"；pIgnoreWhitespace 返回 null 和 "100"；pInteger 返回 100 和空字符串 ""。

如果把这几步打包，就得到 pHello100，它返回 ["Hello", null, 100] 和空剩余字符串。用 pSeq(pHello, pIgnoreWhitespace, pInteger) 也能做到，它的类型是 Parser<[string, null, number]>。再用 pMap 把结果变形，就能得到 { greeting: "Hello", who: 100 }。

又例如 pSeq(pNumber, pSemicolon) 重复匹配 "10;20;30;"：第一次返回 [10, ";"] 和 "20;30;"，第二次返回 [20, ";"] 和 "30;"，第三次返回 [30, ";"] 和空字符串。

然后是一个真实世界的例子：ping Cloudflare 的输出。原始输出以 PING 1.1.1.1 (1.1.1.1) 56(84) bytes of data. 开头，随后是 7 条回复，如 64 bytes from 1.1.1.1: icmp_seq=1 ttl=52 time=389 ms（seq 从 1 到 7，ttl 都是 52，时间依次是 389、68.7、47.1、48.6、85.8、84.8、87.4 毫秒），接着是 --- 1.1.1.1 ping statistics ---、8 packets transmitted, 7 received, 12.5% packet loss, time 7008ms 以及 rtt min/avg/max/mdev = 47.129/115.880/388.750/112.515 ms。

我们想把它解析成结构化数据：header 里含 targetIp: "1.1.1.1"、resolvedIp: "1.1.1.1"、icmpPayloadSize: 56、totalPacketSize: 84；packets 是 7 个对象，各有 byteCount: 64、from: "1.1.1.1"、seq、ttl: 52、time；statistics 含 packetsTransmitted: 8、packetsReceived: 7、packetLoss: 12.5、time: 7008，以及 rtt: { min: 47.129, avg: 115.88, max: 388.75, mdev: 112.515 }。

这里有个有趣的对偶：用 list.reduce((acc, n) => acc + n) 把 ["Hello", " ", 100] 合并成 "Hello 100"，这叫 fold（折叠）；而 pSeq(...)("Hello 100") 把 "Hello 100" 拆成 ["Hello", " ", 100]，这在函数式里叫 unfold（展开）。fold 用累加器把许多东西合成一个，unfold 则用中间状态把一个东西拆成许多。

Parser Combinators

解析（parsing）指的是把文本这类结构化程度较低的输入，转换成对象这类结构化程度更高的数据。

很多人熟悉用正则表达式解析文本，也有人知道 tree-sitter——一个为代码编辑器语法高亮提供支持的重量级解析库。但正则在处理复杂任务时会变得混乱，tree-sitter 又常常杀鸡用牛刀。在这片中间地带，解析器组合子（parser combinators）正合适。知道它的人不多，所以请容我为你展示！

部分解析器

我们要看的最小解析单元是部分解析器（partial parser）。它决定从输入字符串的哪里切开，然后返回一个由「解析出的东西」和「剩余字符串」组成的二元组。

它可以是任意函数，只要返回这样的二元组就行！它内部甚至也可以用正则。

以 pInteger 为例：它是一个 Parser<number>，用 /^\d+/ 匹配输入开头的数字；如果没匹配到就抛错，否则取出匹配到的数字部分，返回 [Number(digits), input.substring(digits.length)]。

串联

单个解析器函数本身做不了太多事；但把多个解析器按顺序应用，就能一步步吃掉整个输入。

比如 pHello 检查输入是否以 "Hello" 开头，若是则返回 ["Hello", input.substring(5)]。pIgnoreWhitespace 用 /^\s+/ 匹配开头空白，返回 [null, input.substring(spaces.length)]。pInteger 则如前所述解析整数。

手动串联时，先 pHello("Hello 100") 得到 "Hello" 和 " 100"；再把剩余部分交给 pIgnoreWhitespace 得到 null 和 "100"；最后交给 pInteger 得到 100 和空字符串。打印出来就是 "Hello"、null、100，剩余输入为空。

串联

更有意思的是，部分解析器的真正威力在于：我们可以把这个串联过程本身包装成一个新的解析器。

pHello100 的类型是 Parser<[string, null, number]>。它内部依次调用 pHello、pIgnoreWhitespace、pInteger，把各自的结果组成 [[hello, space, number], rest3] 返回。

pSeq

我们还可以进一步泛化，提供一个专门做串联的函数！毕竟「把剩余字符串喂给下一个解析器」这件事非常通用，并不依赖某一个解析器具体做什么。

要把类型写对有点棘手，但 TypeScript 完全能表达这种可变参数类型。pSeq 的定义大致是：接收一组解析器 Parsers<T>，返回一个 Parser<T>；运行时依次对每个解析器传入当前剩余字符串，收集结果值，最后返回结果数组和最终剩余字符串。

组合子

因为 pSeq 把许多解析器合并成一个新的解析器，我们叫它解析器组合子（parser combinator）。

请停下来欣赏一下其中的函数式疯狂：pSeq 是一个接收解析器的函数，而解析器本身又是函数；它返回另一个解析器，而这也是一个函数。只有到这一步，我们才真正通过拿数据去调用最终得到的函数来启动解析。

这就像我们在搭建一个由嵌套函数构成的结构，从而创建出复杂的程序。挺酷的！

顺便一提

如果你觉得「把一个字符串拆成很多 token」和 .reduce 有点关系，那你的直觉很好。我们这里做的其实是它的对偶，在函数式圈子里叫 unfold（展开），而 reduce 被称为 fold（折叠）。

fold 用中间状态——累加器——把一串东西合并成一个；unfold 则用中间状态把一个东西拆成许多。

数学真有趣！

元组不太好用

如果解析的目的是从原始字符串里得到结构化的、通常还便于人阅读的数据，那么像 ["Hello", null, 100] 这样的元组很难作为最终目标。

我们当然可以在结果上做一次映射，把它变成更方便的形状：比如从 pHello100("Hello 100") 得到结果后，取出 result[0] 作为 greeting，result[2] 作为 who，组成 { greeting: "Hello", who: 100 }。

pMap

但这并不符合解析器组合子的精神！和之前一样，我们也可以把映射本身包装成一个新的组合子。

pMap 接收一个解析器和一个函数；解析完成后，该函数会被应用到结果上。它的实现是：先调用 parser(input) 得到 [value, rest]，再返回 [fn(value), rest]。

于是 pGreeting = pMap(pHello100, ([greeting, _, who]) => ({ greeting, who }))，用它解析 "Hello 100" 就会得到 { greeting: "Hello", who: 100 }。

pRepeat

在进入实际例子前，我再展示第三个基础组合子：pRepeat——它接收一个解析器，反复应用，直到无法继续为止。

它就是正则里 * 的组合子版本！

pRepeat 的实现是不断尝试 parser(rest)，成功就把值推进 values、更新 rest，失败（抛错）时返回 [values, rest]。

以 pNumber 和 pSemicolon 为例：pNumber 和 pInteger 一样解析整数；pSemicolon 检查是否以 ";" 开头并返回 [";", input.substring(1)]。那么 pNumberCsv = pRepeat(pSeq(pNumber, pSemicolon)) 解析 "10;20;30;" 会得到 [[[10, ";"], [20, ";"], [30, ";"]], ""]。

来写一个解析器！

现在工具够了，可以开始解析真实的现实数据了！

上面是我 ping Cloudflare 的示例输出，里面有很多有用信息。我们把它解析成前面展示过的 PingResult 结构：header 是 PingHeader，packets 是 IcmpPacket 数组，statistics 是 PingStatistics。其中 IcmpPacket 含 byteCount、from、seq、ttl、time；PingHeader 含 targetIp、resolvedIp（括号里的 IP）、icmpPayloadSize: 56、totalPacketSize: 84；PingStatistics 含收发包数、丢包率、总时间和 rtt 的 min/avg/max/mdev。

零碎部件

输出里有些反复出现的东西，比如十进制数或 IP 地址，先来准备这些基础解析器。

pString 接收一个精确文本（如 "PING"），检查输入是否以它开头，返回 [text, input.substring(text.length)]。pInteger 解析整数，如 64。pDecimal 解析带可选小数的数字，如 68.7，正则用 /^\d+(\.\d+)?/。pIpV4Address 先定义 pByte（用 pMap(pInteger, n => { if (n > 255) throw new Error(); return n; }) 确保每段不超过 255），pDot 是 pString(".")，然后用 pMap(pSeq(pByte, pDot, pByte, pDot, pByte, pDot, pByte), ([a, _1, b, _2, c, _3, d]) => \${a}.${b}.${c}.${d}`)拼成 IPv4 字符串。pWhitespace用/^\s+/匹配至少一个空白，返回[null, input.substring(match[0].length)]`。

头部

第一行应该很简单，就是一组 pSeq 解析器，再用 pMap 整理成 PingHeader 形状。

pPingHeaderParts 按顺序串联：pString("PING")、pWhitespace、pIpV4Address、pWhitespace、pString("(")、pIpV4Address、pString(")")、pWhitespace、pInteger、pString("(")、pInteger、pString(")")、pString(" bytes of data.")。

然后 pPingHeader 用 pMap 从结果中取出：目标 IP 是第 3 个结果 c，解析 IP 是第 6 个 f，ICMP 负载大小是第 9 个 i，总包大小是第 11 个 k，组成对应对象。

一个数据包

数据包其实也是一组 pSeq 加一个 pMap。这解析工作真的很简单，对吧！

pIcmpPacketParts 依次是：pInteger、pString(" bytes from ")、pIpV4Address、pString(": icmp_seq=")、pInteger、pString(" ttl=")、pInteger、pString(" time=")、pDecimal、pString(" ms")。

pIcmpPacket 则用 pMap 取出 byteCount（第 1 个 a）、from（第 3 个 c）、seq（第 5 个 e）、ttl（第 7 个 g）、time（第 9 个 i），组成包对象。

统计信息

顺便问一句，你能想象用正则来做这些吗？

先定义 pUselessLine，它串联 pString("--- ")、pIpV4Address、pString(" ping statistics ---")。pStatsLine1 串联：pInteger、pString(" packets transmitted, ")、pInteger、pString(" received, ")、pDecimal、pString("% packet loss, time ")、pInteger、pString("ms")。pStatsLine2 串联：pString("rtt min/avg/max/mdev = ")、四个 pDecimal 与 pString("/") 交替、最后 pString(" ms")。

pPingStatistics 用 pMap 包住 pSeq(pUselessLine, pWhitespace, pStatsLine1, pWhitespace, pStatsLine2)，从结果里取出 packetsTransmitted、packetsReceived、packetLoss、time，以及 rtt: { min, avg, max, mdev }。

Ping 数据包，解析完成！

然后，基本上就大功告成了！只需要再来一个 pSeq 和 pMap 把所有部分包在一起，我们就为 ping 命令构建出了完整的解析器。

这太简单了，对吧？

pPingSummary 的类型是 Parser<PingResult>，它用 pMap 包住 pSeq(pPingHeader, pRepeat(pMap(pSeq(pWhitespace, pIcmpPacket), ([_, packet]) => packet)), pWhitespace, pPingStatistics)，最后从结果中取出 header、packets、statistics 组成最终对象。

去试试吧

在这一篇帖子里，我们就从零开始构建出了一个相当复杂的解析器，还顺带手搓了一个解析器组合子库！

用这种方式创建正确且可维护的解析器，比用正则容易得多；一旦开始嵌套 pSeq，等价的正则会变成一团无法阅读的乱麻，而组合子写法依然干净利落。

如果你还惦记着回溯（backtracking）或前瞻（lookahead）这类更高级的特性，放心，解析器组合子同样能处理这些场景，因为说到底一切都只是组合在一起的函数。

下次需要解析什么东西时，去试试它们吧——解析器组合子是解决解析问题一种非常优雅的方案，应该有更多人使用它们！

讨论整体对这份解析器组合子可视化指南评价偏正面，动画和可视化让许多人第一次真正理解了该概念；但分歧集中在两端：技术定义是否严谨，以及幻灯片分页与排版是否损害阅读。此外，也有人补充了该方法在左递归、回溯和样板代码上的局限。

认为可视化指南直观易懂、适合入门

• 指南篇幅短、只有 17 张幻灯片且代码简单，让不少人第一次真正理解了解析器组合子这个术语背后的含义（较多人） > 指南易懂、代码简单，读完终于真正理解了解析器组合子（@smusamashah）
• 动画和视觉设计受到称赞，被认为把抽象的解析过程变直观，降低了学习门槛（较多人）

批评解析器类型签名与“部分解析器”的区分不准确

• 把解析器定义为必定返回结果的类型并不对，解析器可能失败；所谓“部分解析器”组合之后并不会变成完整解析器，部分与完整的区分并不成立，真正的“部分”其实是指函数并非对所有输入都有定义（少数人） > 这个类型暗示解析器一定会返回结果，但它其实可能失败，组合部分解析器也只会得到部分解析器（@mrkeen）

认为排版、幻灯片分页和小屏幕适配损害阅读

• 不理解为何不做成单页：幻灯片让人难以回看前面章节，也无法搜索，像是在数字媒介里无谓地恢复了纸质限制（较多人） > 幻灯片形式难以回看前面的内容，也不能搜索，像是把纸质媒介的限制带回了数字媒介（@marginalia_nu）
• 正文可用区域太小，在 MacBook 等小屏上滚动区域只占约三分之一，大量内边距和侧栏浪费空间，短章节也要翻页滚动（较多人）
• 建议把字体和标题调小，方便滚动查看底部代码片段（少数人）
• 有人开玩笑说应该把滚轮输入“组合”成翻页事件，折射出对滚动与翻页体验的不满（少数人）

认为应指出解析器组合子的局限与工程代价

• 教程至少应说明该方法的局限：无法处理左递归文法，且在歧义文法上容易大量回溯，最坏会带来指数级性能劣化（少数人） > 这类方法不能处理左递归文法，且在歧义文法上容易大量回溯，最坏会有指数级性能问题（@amelius）
• 与从独立文法文件生成解析器的生成器相比，组合子需要大量映射和解包代码，降低可读性；有人因此在 Rust 库中增加捕获和绑定两种组合子来分离文法与结果构造（少数人）

认为示例解析可以更通用或更严谨

• 认为指南错过了展示通用性的机会：类似 ping 输出冒号后的字段其实是键值数据，加入通用键值解析器会更能体现组合子的优雅（少数人） > 冒号后的内容都是键值数据，加入通用键值解析器会更能体现这种方法的优雅（@9dev）
• 第一个地址不应直接被解析为 IP，因为它也可能是主机名；这正好可以演示如何在多种构造之间做选择（少数人）

认为这本质只是标准函数式编程

• 有人觉得内容看起来就是标准函数式编程，并无特别新奇之处（少数人） > 这在我看来就是标准函数式编程（@TZubiri）

有价值的补充

• Fritz Ruehr 的小诗给出了经典类型：解析器是从字符串到“结果与剩余字符串”对的列表的函数，而不是必定成功返回单个结果（@justinnk）
• 从理论上看，解析之所以能使用组合子，是因为解析过程本身具有单子结构，并形成转移幺半群，也就是计算机科学中的半自动机（@stevefan1999）
• 网站分享功能疑似有 bug：从浏览器点击分享得到的链接域名是 example.com，而非站点域名 t3.at（@BackacheDescent）