本章涵盖

• 解析器组合器简介
• 在没有实现的情况下设计和使用 API

在本章中，我们将设计一个用于创建 解析器 的组合器库。我们将使用 JSON 解析 （http://mng.bz/DpNA） 作为激励用例。与第7章和第8章一样，本章与其说是关于解析，不如说是关于提供对功能设计过程的进一步见解。

什么是解析器？

解析器是一种专门的程序，它将非结构化数据（例如，文本或任何类型的符号、数字或标记流）作为输入，并输出该数据的结构化表示。例如，我们可以编写一个解析器，将逗号分隔的文件转换为列表列表，其中外部列表的元素表示记录，每个内部列表的元素表示每条记录的逗号分隔字段。另一个示例是解析器，它采用 XML 或 JSON 文档并将其转换为树状数据结构。

在解析器组合器库中，就像我们将在本章中构建的那样，解析器不必那么复杂，也不必解析整个文档。它可以做一些基本的事情，比如识别输入中的单个字符。然后，我们使用组合器从基本解析器组装复合解析器，并从这些组合器组装更复杂的解析器。

本章将介绍一种我们称之为 代数设计 的设计方法。这只是我们在过去章节中不同程度地所做的工作的自然演变 - 首先设计我们的界面以及相关的定律，然后让它指导我们选择数据类型表示。

在本章的几个关键点上，我们将提供更多开放式练习，旨在模拟从头开始编写自己的库时可能遇到的场景。如果你利用这些机会放下这本书，花一些时间研究可能的方法，你将从本章中获得最大的收益。当你设计自己的库时，你不会得到一个很好的选择的类型签名序列来填充实现。你必须决定你需要什么类型和组合子，本书第2部分的一个目标是让你自己做这件事。与往常一样，如果您陷入其中一个练习或想要更多想法，您可以继续阅读或查阅答案。与另一个人一起做这些练习或与其他在线读者比较笔记也可能是一个好主意。

解析器组合器与解析器生成器

您可能熟悉 解析器生成器 库，如Yacc（http://mng.bz/w3zZ），或其他语言的类似库（例如，Java中的ANTLR：http://mng.bz/aj8K）。这些库根据语法规范为分析器生成代码。这种方法工作正常，效率很高，但它带来了代码生成的所有常见问题：库生成一个难以调试的整体代码块作为其输出。重用逻辑片段也很困难，因为我们不能引入新的组合器或辅助函数来抽象解析器中的常见模式。

在解析器组合器库中，解析器只是普通的一类值。生成的解析器往往比Yacc和ANTLR等工具生成的解析器慢，我们需要根据解析器组合器重新实现语法。但是，重用解析逻辑是微不足道的，我们不需要任何独立于编程语言的外部工具。

9.1 先设计代数

回想一下，我们将 代数 定义为对某些数据类型进行操作的函数集合， 以及一组 指定这些函数之间关系的定律。在过去的章节中，我们在代数中发明函数、完善函数集和调整数据类型表示之间相当流畅地移动。法律在某种程度上是事后的想法;我们只有在有了代表和 API 充实之后才制定了法律。这种设计风格没有错， 1 但在这里我们将采用不同的方法。我们将从代数（包括其定律）开始，稍后决定表示。这种方法（我们称之为代数设计）可用于任何设计问题，但特别适用于解析，因为很容易想象解析不同类型的输入需要什么组合器。 2 这让我们即使在推迟决定表示时也能密切关注具体目标。

有许多不同类型的解析库。 3 我们的设计是为了表现力（我们希望能够解析任意语法）、速度和良好的错误报告——最后一点很重要。每当我们对它不期望的输入运行解析器时（如果输入格式不正确，就会发生这种情况），它应该生成解析错误。如果存在解析错误，我们希望能够准确指出错误在输入中的位置并准确指出其原因。在解析库时，错误报告通常是事后才想到的，但我们会确保仔细注意它。

好的，让我们开始吧。为了简单和快速起见，我们的库将创建对字符串作为输入进行操作的解析器。 4 我们需要选择一些解析任务来帮助我们为解析器找到一个好的代数。我们首先应该看什么？像解析电子邮件地址、JSON 或 HTML 这样实用的东西？不！这些任务可以稍后完成。一个好的和简单的领域开始是解析重复字母和胡言乱语单词的各种组合，如“abracadabra”和“abba”。尽管这听起来很愚蠢，但我们之前已经看到像这样的简单例子如何帮助我们忽略无关紧要的细节并专注于问题的本质。

因此，让我们从最简单的解析器开始：识别单字符输入“a”的解析器。与过去的章节一样，我们可以为任务 发明一个组合 器——char：

def char(c: Char): Parser[Char]

我们在这里做了什么？我们变出了一个类型， 解析器 ，它在单个参数上参数化，指示解析器的结果 类型 。也就是说，运行解析器不应该简单地产生是/否响应;如果它成功，我们希望得到一个具有某种有用类型的结果，如果它失败，我们期望有关失败的信息。只有当输入恰好是字符“a”时，char（'a'）解析器才会成功，并且它将返回相同的字符“a”作为其结果。

这个关于运行解析器 的讨论清楚地表明，我们的代数需要以某种方式扩展以支持这一点。让我们为它发明另一个函数：

extension [A](p: Parser[A]) def run(input: String): Either[ParseError, A]

等一会;什么是解析错误？这是我们刚刚变出的另一种类型！在这一点上，我们不关心 ParseError 或 Parser 的表示。我们正在指定一个碰巧使用两种类型的 接口 ，我们选择暂时忽略其表示或实现细节。让我们用一个特征来明确这一点：

trait Parsers[ParseError, Parser[+_]]:      ①
 
  extension [A](p: Parser[A]) def run(input: String): Either[ParseError, A]
 
  def char(c: Char): Parser[Char]           ②

（1） 解析器是一个类型参数，它本身是一个协变类型构造函数。

（2）这里解析器类型构造函数应用于Char。

有趣的解析器[+_]类型参数是怎么回事？现在还不太重要，但这是 Scala 对类型参数的语法，类型参数本身就是一个类型构造函数。 5 使 ParseError 成为类型参数允许 Parsers 接口适用于 ParseError 的任何表示形式，而使 Parser[+_] 成为类型参数意味着该接口适用于 Parser 的任何表示形式。下划线只是意味着无论解析器是什么，它都需要一个类型参数来表示结果的类型，如在解析器[Char]中。此代码将按原样编译。我们不需要为 ParseError 或 Parser 选择一个表示，我们可以继续在这个特征的主体中放置额外的组合子。

我们的 char 函数应该满足一个明显的定律：对于任何 char，c

char(c).run(c.toString) == Right(c)

让我们继续。我们可以识别单个字符“a”，但是如果我们想识别字符串“abracadabra”怎么办？我们现在没有办法识别整个字符串，所以让我们添加一下：

def string(s: String): Parser[String]

同样，这应该满足一个明显的定律：对于任何字符串，s

string(s).run(s) == Right(s)
 

如果我们想识别字符串“abra”或字符串“cadabra”怎么办？我们可以为它添加一个非常专业的组合器：

def orString(s1: String, s2: String): Parser[String]

但是在两个解析器之间进行选择似乎更普遍有用，无论它们的结果类型如何，所以让我们做这个多态：

extension [A](p: Parser[A]) def or(p2: Parser[A]): Parser[A]

我们期望 string（“abra”）.or（string（“cadabra”）） 在任一字符串解析器成功时都会成功：

string("abra").or(string("cadabra")).run("abra") == Right("abra")
string("abra").or(string("cadabra")).run("cadabra") == Right("cadabra")

顺便说一下，我们可以给这个或组合器很好的中缀语法，比如 s1 |S2 或 S1 或 S2 。

清单 9.1 向解析器添加中缀语法

trait Parsers[ParseError, Parser[+_]]:
  def char(c: Char): Parser[Char]
  def string(s: String): Parser[String]
 
  extension [A](p: Parser[A])
    def run(input: String): Either[ParseError, A]
 
    infix def or(p2: Parser[A]): Parser[A]       ①
    def |(p2: Parser[A]): Parser[A] = p.or(p2)   ②

（1） 中缀修饰符允许或用作运算符。

（2） |运算符是 OR 的别名。不需要中缀修饰符，因为所有符号名称都是运算符。

我们还没有选择解析器的表示形式，但是给定一个解析器类型的值P，编写导入P.*可以让我们编写像string（“abra”）这样的表达式|字符串（“cadabra”）来创建解析器。这将适用于 解析 器的所有实现。我们将使用 a |b 在本章其余部分的语法自由。

我们现在可以识别各种字符串，但我们没有办法谈论重复。例如，我们如何识别字符串的三个重复（“abra”）|字符串（“Cadabra”） 解析器？再一次，让我们为它添加一个组合器： 6

extension [A](p: Parser[A]) def listOfN(n: Int): Parser[List[A]]

我们在选择 A 时做了 listOfN 参数化，因为它似乎不应该关心我们是否有解析器[字符串]、解析器[字符]或其他类型的解析器。以下是我们对 listOfN 的期望的一些示例：

val p = (string("ab") | string("cad")).listOfN(3)
p.run("ababcad") == Right(List("ab", "ab", "cad"))
p.run("cadabab") == Right(List("cad", "ab", "ab"))
p.run("ababab") == Right(List("ab", "ab", "ab"))

在这一点上，我们只是在收集所需的组合子，但我们还没有尝试将我们的代数细化为一组最小的基元，我们也没有谈论更多的一般定律。接下来我们将开始这样做，但不是放弃游戏，而是请您自己检查一些更简单的用例，并尝试设计具有相关定律的最小代数。这应该是一个具有挑战性的练习，但喜欢挣扎，看看你能想出什么。

以下是需要考虑的其他解析任务，以及一些指导性问题：

• 一个 解析器[Int]，它 识别零个或多个 “a”字符， 其结果值 是 它看到 的“a”字符的数量 - 例如，给定“aa”，解析器的结果是2;给定 “” 或 “b123”（不以 'a' 开头的字符串），它的结果是 0 ;等等。
• 一个 解析器[Int] ，它识别一个或多个 “a”字符 ，其结果值是它看到的 “a”字符的数量 - （这是否以某种方式定义为与“a”重复零次或多次的解析器相同的组合器？当给定一个没有开头“a”的字符串时，解析器应该失败。在这种情况下，您希望如何处理错误报告？API 是否支持在失败的情况下给出显式消息，例如“预期的一个或多个'a'”？
• 识别零个或多个的解析器 “a” 后跟一个或多个 “b” ，这导致看到的字符对计数 - 例如，给定“bbb”，我们得到（0，3），给定“aaaab”我们得到（4，1），依此类推。

还有一些注意事项：

• 如果我们试图解析一个由零个或多个“a”字符组成的序列，并且只对看到的字符数感兴趣，那么必须建立一个，比如说，一个List[Char]只是为了扔掉它并提取长度，这似乎是低效的。对此可以做些什么吗？
• 在我们的代数中，各种形式的重复是原始的，还是可以用更简单的东西来定义它们？
• 我们之前引入了一个类型ParseError，但到目前为止我们还没有为ParseError的API选择任何函数，我们的代数没有任何方法让程序员控制报告哪些错误。这似乎是一个限制，因为我们希望从解析器那里获得有意义的错误消息。你能做些什么吗？
• 做一个 |b 与 b |一个？这是你必须做出的选择。如果答案是肯定的，后果是什么？如果答案是否定的呢？
• 做一个 |（b | c） 的意思与 （a | b） |c ?如果是，这是代数的原始定律，还是更简单的东西所暗示的？
• 试着想出一套定律来指定你的代数。你不一定需要法律是完整的;只需写下一些您期望对任何解析器实现都适用的定律。

花一些时间根据本指南提出组合器和可能的定律。当您感到卡住或处于一个好的停止点时，请继续阅读下一节，该部分介绍了一种可能的设计。

代数设计的优势

当您首先设计库的代数时，代数数据类型的表示并不重要。只要他们支持所需的法律和职能，您甚至不需要公开您的陈述。

这里有一个想法，即类型根据其与其他类型（由函数集及其定律指定）的关系而不是其内部表示来赋予其含义。 7 这种观点通常与范畴论有关，范畴论是数学的一个分支。如果您有兴趣，请参阅章节注释 （https://github.com/fpinscala/fpinscala/wiki） 以获取有关此连接的更多信息。

9.2 可能的代数

我们将逐步发现一组用于前面提到的解析任务的组合器。如果你自己完成了这个设计任务，你可能会走一条不同的道路，最终可能会得到一组不同的组合器，这很好。

首先，让我们考虑一个解析器，它识别字符“a”的零个或多次重复，并返回它看到的字符数。我们可以从为它添加一个原始组合器开始;让我们称它为许多：

extension [A](p: Parser[A]) def many: Parser[List[A]]

这不完全是我们追求的;我们需要一个解析器[Int]来计算元素的数量。我们可以更改多组合器以返回 Parser[Int]，但这感觉太具体了——毫无疑问，有时我们关心的不仅仅是列表长度。最好介绍另一个现在应该熟悉的组合器——map：

extension [A](p: Parser[A]) def map[B](f: A => B): Parser[B]
 

现在我们可以像这样定义我们的解析器：

val numA: Parser[Int] = char('a').many.map(_.size)

例如，我们期望numA.run（“aaa”）给出Right（3），numA.run（“b”）给出Right（0）。

我们对 map 的行为有强烈的期望：如果解析器成功，它应该只转换结果值。map不应该检查额外的输入字符，一个失败的解析器不能通过map成为一个成功的解析器，反之亦然。一般来说，我们希望映射是 结构保留 的，就像我们对 Par 和 Gen 的要求一样。让我们通过规定现在熟悉的法律来正式化这一点：

p.map(a => a) == p

我们应该如何记录这条法律？我们可以把它放在文档注释中，但在前一章中，我们开发了一种使我们的法律 可执行 的方法。让我们在这里使用该库。

示例 9.2 将解析器与映射相结合

import fpinscala.testing.*
 
trait Parsers[ParseError, Parser[+_]]:
  ...
  object Laws:
    def equal[A](p1: Parser[A], p2: Parser[A])(in: Gen[String]): Prop =
      Prop.forAll(in)(s => p1.run(s) == p2.run(s))
 
    def mapLaw[A](p: Parser[A])(in: Gen[String]): Prop =
      equal(p, p.map(a => a))(in)

稍后，当我们测试解析器的实现是否按预期运行时，这将派上用场。当我们稍后发现更多定律时，我们鼓励您将它们写为 Laws 对象中的实际属性。 8

顺便说一下，现在我们有了map，我们可以用字符串来实现char：

def char(c: Char): Parser[Char] =
  string(c.toString).map(_.charAt(0))

类似地，另一个组合子 成功 可以用字符串和映射来定义：

def succeed[A](a: A): Parser[A] =
  string("").map(_ => a)

无论输入字符串如何，此解析器始终使用值 a 成功（因为 string（“”） 将始终成功，即使输入为空）。这个组合器对你来说很熟悉吗？我们可以用法律指定它的行为：

succeed(a).run(s) == Right(a)

9.2.1 切片和非空重复

许多和映射的组合当然让我们表达了计算“a”字符数量的解析任务，但是构造一个List[Char]只是为了丢弃其值并提取其长度似乎效率低下。如果我们可以纯粹运行一个解析器来查看它检查的输入字符串的哪一部分，那就太好了。让我们为此想出一个组合器：

extension [A](p: Parser[A]) def slice: Parser[String]

我们称这个组合器切片，因为我们打算让它返回解析器检查的输入字符串部分，如果成功的话。例如，（char（'a'） | char（'b'））.many.slice.run（“aaba”） 结果为 Right（“aaba”） ;我们忽略许多人累积的列表，只返回与解析器匹配的输入字符串部分。

使用 slice ，我们计算“a”个字符的解析器现在可以写为 char（'a'）.many.slice.map（_.size）。这里的 _.size 函数现在引用 String 上的 size 方法，该方法需要常量时间，而不是 List 上的 size 方法，它需要与列表长度成正比的时间（并且需要我们实际构造列表）。

请注意，这里还没有实现;我们仍然只是想出了我们想要的界面。但是slice确实对实现施加了一个约束，即即使解析器p.many.map（_.size）在运行时会生成一个中间列表，p.many.slice.map（_.size）也不会。这是一个强烈的暗示，即切片是原始的，因为它必须能够访问解析器的内部表示。

让我们考虑下一个用例。如果我们想识别 一个或多个 “a”字符怎么办？首先，我们为其介绍一个新的组合器— many1 ：

extension [A](p: Parser[A]) def many1: Parser[List[A]]

感觉 many1 不应该是原始的，但它应该以某种方式定义为许多。真的，p.many1 只是 p 后跟 p.many 。因此，我们似乎需要某种方法来运行一个解析器，然后运行另一个解析器，假设第一个解析器成功，并返回其结果的乘积。让我们补充一下：

extension [A](p: Parser[A])
  def product[B](p2: Parser[B]): Parser[(A, B)]
  def **[B](p2: Parser[B]): Parser[(A, B)] = product(p2)    ①

（1） 产品的运算符别名，其中 a ** b 委托给 a.product（b）

使用乘积，实现现在熟悉的组合器map2，然后用它来实现许多1。请注意，我们可以选择根据 map2 使 map2 成为原始和定义的乘积，就像我们在前面的章节中所做的那样。选择取决于您：

extension [A](p: Parser[A])
  def map2[B, C](p2: Parser[B])(f: (A, B) => C): Parser[C]

使用 many1 ，我们现在可以实现零个或多个 'a' 后跟一个或多个 'b' 的解析器，如下所示：

char('a').many.slice.map(_.size) ** char('b').many1.slice.map(_.size)

困难 ：尝试制定法律来指定产品的行为。

现在我们有了map2，很多真的是原始的吗？让我们想想p.many会做什么。它尝试运行 p ，然后再次运行 p.many，然后再次运行，依此类推，直到尝试解析 p 失败。它会将所有成功运行的 p 的结果累积到一个列表中。一旦 p 失败，解析器就会返回空列表。

困难 ：在继续之前，看看你是否可以用 |、地图 2 和成功。

困难 ：使用 map2 并成功，实现前面的 listOfN 组合器：

extension [A](p: Parser[A]) def listOfN(n: Int): Parser[List[A]]

现在让我们尝试实现许多.下面是一个实现 |、map2 和成功：

extension [A](p: Parser[A]) def many: Parser[List[A]] =
  p.map2(p.many)(_ :: _) | succeed(Nil)

这段代码看起来不错整洁。我们使用 map2 表示我们想要 p 后跟 p.many 再次，并且我们希望将它们的结果与 ：： 结合起来以构建结果列表。或者，如果失败了，我们希望使用空列表取得成功 - 但此实现存在问题。你能发现它是什么吗？我们在第二个参数中递归调用 map2，它在评估第二个参数时 是严格的 。考虑对某些解析器 p 的 p.many 求值进行简化的程序跟踪。我们只显示 |这里：

p.many
p.map2(p.many)(_ :: _)
p.map2(p.map2(p.many)(_ :: _))(_ :: _)
p.map2(p.map2(p.map2(p.many)(_ :: _))(_ :: _))(_ :: _)
...

因为对 map2 的调用总是计算它的第二个参数，所以我们的许多函数永远不会终止！那可不行。这表明我们需要在第二个参数中使产品和 map2 不严格：

extension [A](p: Parser[A])
  def product[B](p2: => Parser[B]): Parser[(A, B)]
 
  def map2[B,C](p2: => Parser[B])(f: (A, B) => C): Parser[C] =
    p.product(p2).map((a, b) => f(a, b))

我们也可以用一个单独的组合子来处理非严格性，就像我们在第7章中所做的那样。在这里试试这个，并对现有的运算器进行必要的更改。在这种情况下，您如何看待这种方法？

现在，我们对许多实施应该可以正常工作。从概念上讲，产品无论如何都应该在其第二个参数中不严格，因为如果第一个解析器失败，甚至不会咨询第二个解析器。

我们现在有很好的组合器，用于连续解析一个事物，然后是另一个或多个相同类型的事物。但是由于我们正在考虑组合子是否应该是非严格的，让我们重新审视前面的 or 组合器：

extension [A](p: Parser[A]) def or(p2: Parser[A]): Parser[A]
 

我们将假设或偏置，这意味着它会在输入上尝试 p1，然后仅在 p 失败时才尝试 p2。 9 在这种情况下，我们应该在第二个论点中使它不严格，甚至可能永远不会被参考：

extension [A](p: Parser[A]) infix def or(p2: => Parser[A]): Parser[A]

我们需要对 |算子。

9.3 处理上下文敏感度

让我们退后一步，看看到目前为止我们拥有的原语：

• 字符串 — 识别并返回单个字符串
• p.slice —如果成功，则返回 p 检查的输入部分
• 成功 （a） - 始终成功，值为 a
• p.map（f） - 如果成功，则将函数 f 应用于 p 的结果
• p1.product（p2） — 对两个解析器进行序列，先运行 p1，然后运行 p2，如果两个解析器都成功，则返回它们的结果对
• p1 或 p2 — 在两个解析器之间进行选择，首先尝试 p1，如果 p2 失败，则尝试 p1

使用这些基元，我们可以表达重复和非空重复（许多，listOfN和许多1），以及像char和map2这样的组合器。如果这些原语足以解析 任何 上下文无关的语法，包括 JSON，您会感到惊讶吗？嗯，他们是！我们很快就会开始编写 JSON 解析器，但我们还不能表达什么？

假设我们要解析一个数字，比如“4”，后跟 许多 “a”字符（这类问题应该在前面的章节中很熟悉）。有效输入的示例包括 “0” ， “1a” ， “2aa” ， “4aaaa” 等。这是上下文相关语法的一个示例。它不能用 product 表示，因为我们对第二个解析器的选择取决于第一个解析器的结果（第二个解析器取决于它的上下文）。我们希望运行第一个解析器，然后使用从第一个解析器的结果中提取的数字来执行 listOfN。你能明白为什么产品不能表达这一点吗？

这种进展可能对您来说很熟悉。在过去的章节中，我们遇到了类似的表现力限制，并通过引入一个新的原语来处理它们：flatMap。让我们在这里介绍一下：

extension [A](p: Parser[A]) def flatMap[B](f: A => Parser[B]): Parser[B]

你能看到这个签名如何意味着对解析器进行排序的能力，其中链中的每个解析器都依赖于前一个解析器的输出吗？

使用 flatMap 和任何其他组合器，编写我们之前无法表达的上下文相关解析器。要解析数字，您可以使用新的原语， 正则表达式 ，它将正则表达式提升为解析器 。 10 在 Scala 中，可以使用 s.r 将字符串 s 提升为正则表达式对象（具有匹配方法），例如 “[a-zA-Z_][a-zA-Z0-9_]*”.r ：

def regex(r: Regex): Parser[String]

在平面地图方面实现产品和地图2。

地图不再是原始的。用平面图和/或其他组合器来表达它。

看起来我们有一个新的原语， flatMap ，它支持上下文相关的解析并允许我们实现 map 和 map2 .这不是flatMap第一次出现。

我们现在有一个更小的集合，只有六个原语：字符串、正则表达式、切片、成功或、 和平面映射。但我们也比以前拥有更多的权力。使用flatMap，而不是不太通用的map和产品，我们不仅可以解析任意上下文无关的语法，如JSON，还可以解析上下文相关的语法，包括极其复杂的语法，如C++和PERL。

9.4 编写 JSON 解析器

现在让我们编写这个 JSON 解析器，好吗？我们还没有代数的实现，我们还没有添加任何组合子来报告良好的错误，但我们可以稍后处理这些事情。我们的 JSON 解析器不需要知道解析器如何表示的内部细节。我们可以简单地编写一个函数，仅使用我们定义的原语集和任何派生的组合器来生成 JSON 解析器。也就是说，对于某些 JSON 解析结果类型（我们将很快解释 JSON 格式和解析结果类型），我们将编写如下函数：

def jsonParser[Err, Parser[+_]](
  P: Parsers[Err, Parser]             ①
): Parser[JSON] =
  import P.*                          ②
  val spaces = char(' ').many.slice   ③
  ...

（1） Err 和 Parser 是类型参数，P 是 Parsers[Err， Parser] 类型的值。

（2）这将导入P的所有成员，使我们能够访问到目前为止编写的运算器。

（3） 字符、许多和切片是从 P 导入的。

这似乎是一件奇特的事情，因为在我们有解析器接口的具体实现之前，我们将无法运行我们的解析器。但是，我们将继续，因为在FP中，定义代数并探索其表达性而没有具体的实现是很常见的。具体的实现可能会束缚我们，并使对 API 的更改更加困难。特别是在库的设计阶段，无需提交任何特定实现 即可 轻松优化代数，我们这里的部分目标是让您熟悉这种工作方式。

在本节之后，我们将回到向解析 API 添加更好的错误报告的问题。我们可以在不干扰 API 的整体结构或非常更改我们的 JSON 解析器的情况下做到这一点。我们还将提出解析器类型的具体、可运行的表示形式。重要的是，我们将在下一节中实现的 JSON 解析器将完全独立于该表示形式。

9.4.1 JSON 格式

如果您还不熟悉 JSON 格式的所有详细信息，您可能需要阅读语法规范 （http://json.org）。下面是一个示例 JSON 文档：

{
  "Company name" : "Microsoft Corporation",
  "Ticker"  : "MSFT",
  "Active"  : true,
  "Price"   : 30.66,
  "Shares outstanding" : 8.38e9,
  "Related companies" :
    [ "HPQ", "IBM", "YHOO", "DELL", "GOOG" ]
}

JSON 中的 值 可以是多种类型之一。JSON 中的 对象 是以逗号分隔的键值对序列，括在大括号 （{} ） 中。键必须是字符串，如“Ticker”或“Price”，并且值可以是另一个对象;一个 数组 ，如 [“HPQ”、“IBM” ...]，包含更多值;或 文字 ，如“MSFT”、true、null 或 30.66 。

我们将编写一个相当愚蠢的解析器，它只是从文档中解析语法树，而不进行任何进一步的处理。 11 我们需要一个解析的 JSON 文档的表示形式。让我们为此引入一种数据类型：

enum JSON:
  case JNull
  case JNumber(get: Double)
  case JString(get: String)
  case JBool(get: Boolean)
  case JArray(get: IndexedSeq[JSON])
  case JObject(get: Map[String, JSON])

9.4.2 JSON 解析器

回想一下，我们已经构建了以下一组基元：

• 字符串 — 识别并返回单个字符串
• 正则表达式 — 识别正则表达式 s
• p.slice —如果成功，则返回 p 检查的输入部分
• 成功 （a） - 始终成功，值为 a
• p.flatMap（f） — 运行解析器，然后使用其结果选择要按顺序运行的第二个解析器
• P1 |p2 — 在两个解析器之间进行选择，首先尝试 p1，如果 p2 失败，则尝试 p1

我们使用这些基元来定义许多组合子，如map、map2、many和many1。

困难 ：在这一点上，您将接管该过程。您将使用我们定义的基元从头开始创建解析器[JSON]。你不需要担心（还）解析器的表示。随着你的前进，你无疑会发现额外的组合器和习语，注意并分解出常见的模式，等等。使用你在本书中一直在培养的技能，玩得开心！如果您遇到困难，您可以随时查阅答案。

以下是一些最低限度的指导：

• 您发现的任何通用组合器都可以直接添加到解析器特征中。
• 您可能希望引入组合器，以便更轻松地解析 JSON 格式的标记（如字符串文字和数字）。为此，您可以使用我们之前介绍的正则表达式原语。您还可以添加一些原语，如字母、数字、空格等，用于构建令牌解析器。

如果您需要更多指导，请参阅提示。完整的JSON解析器在答案的JSON.scala文件中给出。

9.5 错误报告

到目前为止，我们根本没有讨论错误报告。我们专注于发现一组原语，这些原语让我们可以表达不同语法的解析器，但除了解析语法之外，我们还希望能够确定解析器在给定意外输入时应该如何响应。

即使不知道解析器的实现会是什么样子，我们也可以抽象地推理一组组合器指定的信息。到目前为止，我们介绍的运算器都没有说明在发生故障时应该报告 什么错误消息 ，或者 ParseError 应该包含哪些其他信息。我们现有的组合器只指定语法是什么，以及如果成功如何处理结果。如果我们在这一点上宣布自己已完成并进入实施，我们将不得不对错误报告和错误消息做出一些武断的决定，这些决定不太可能普遍适用。

困难 ：如果你还没有这样做，花一些时间发现一组很好的组合器，用于表达解析器报告的错误。对于每个组合器，尝试提出指定其行为应该是什么的定律。这是一项非常开放式的设计任务;以下是一些指导性问题：

• 给定解析器字符串（“abra”） ** string（“ ”）.many ** string（“cadabra”） ，给定输入“abra cAdabra”（注意大写字母“A”）——类似于预期“a”或预期“cadabra”，您想报告哪种错误？如果要选择其他错误消息，例如“魔术词不正确，请重试！
• 给定 a 或 b，如果 a 在输入上失败，我们 是否总是 想运行 b，或者在某些情况下我们可能不想运行？如果有这种情况，你能想到额外的组合器，允许程序员指定何时或应该考虑第二个解析器吗？
• 您希望如何处理报告错误 位置 ？
• 给定一个 |b ，如果 a 和 b 在输入上都失败了，我们是否要支持报告两个错误？我们 是否总是 想报告这两个错误，或者我们是否想给程序员一种方法来指定报告两个错误中的哪一个？

我们建议您在对设计满意后继续阅读。下一节将详细介绍可能的设计。

组合器指定信息

在典型的函数库设计场景中，我们至少对具体表示有一些想法，我们通常根据函数将如何影响这种表示来考虑函数。从代数开始，我们被迫以不同的方式思考——我们必须根据函数为可能的实现指定的信息来思考函数。签名决定了向实现提供哪些信息，并且实现可以自由地使用这些信息，只要它遵守任何指定的法律。

9.5.1 可能的设计

现在您已经花了一些时间想出了一些好的错误报告组合器，我们将研究一种可能的设计。同样，您可能已经到达了不同的设计，这完全没问题。这只是另一个看到工作设计过程的机会。

我们将逐步介绍我们的错误报告组合器。首先，让我们介绍一个显而易见的。到目前为止，没有一个原语允许我们将错误消息分配给解析器。我们可以为此引入一个基元组合器— 标签：

extension [A](p: Parser[A]) def label(msg: String): Parser[A]

标签的预期含义是，如果 p 失败，它的 ParseError 将以某种方式包含 msg 。这到底是什么意思？好吧，我们可以假设类型ParseError = String，并且返回的ParseError将 等于 标签，但我们希望我们的解析错误也告诉我们问题发生 的位置 。让我们暂时将其添加到我们的代数中：

case class Location(input: String, offset: Int = 0):
  lazy val line = input.slice(0, offset + 1).count(_ == '\n') + 1
  lazy val col = input.slice(0, offset + 1).lastIndexOf('\n') match
    case -1 => offset + 1
    case lineStart => offset - lineStart
 
def errorLocation(e: ParseError): Location     ①
def errorMessage(e: ParseError): String        ②

（1） 从抽象的 ParseError 中提取具体位置

（2） 从抽象的 ParseError 中提取具体消息

我们在此处为 Location 选取了一个具体的表示形式，其中包括完整输入、此输入的偏移量以及行号和列号，这些表示可以从完整输入和偏移量中延迟计算。我们现在可以更准确地说出我们对标签的期望。如果 Left（e） 失败，错误消息 （e） 将等于 label 设置的消息。这可以用 Prop 指定：

def labelLaw[A](p: Parser[A], inputs: SGen[String]): Prop =
  forAll(inputs ** Gen.string):
    case (input, msg) =>
      p.label(msg).run(input) match
        case Left(e) => errorMessage(e) == msg
        case _ => true

位置呢？我们希望解析器实现使用发生错误的位置填充它。这个概念仍然有点模糊;如果我们有一个 |b ，并且两个解析器在输入上都失败，报告了哪个位置和标签？我们将在下一节中讨论这个问题。

9.5.2 嵌套错误

标签组合器是否足以满足我们所有的错误报告需求？差一点。让我们看一个例子：

val p = string("abra").label("first magic word") **
          string(" ").many **                           ①
          string("cadabra").label("second magic word")

（1） 跳过空格。

我们想从p.run（“abra cAdabra”）中获取什么样的ParseError？（请注意 cAdabra 中的大写字母 A。直接原因是大写的“A”，而不是预期的小写“a”。该错误将有一个位置，以某种方式报告它可能会很好。但是 只 报告低级错误不会提供很多信息，特别是如果这是大型语法的一部分，并且我们在更大的输入上运行解析器。我们还有一些有用的上下文 - 在标记为“第二个魔术词”的解析器中发生的即时错误。这当然是有用的信息。理想情况下，错误消息应该告诉我们，在解析“第二个魔术词”时，有一个意外的大写字母“A”。这查明了错误，并为我们提供了理解它所需的上下文。也许顶级解析器（在这种情况下是p）可能能够提供更高层次的描述，说明解析器在失败时正在做什么（比如“解析魔法咒语”），这也可能是有益的。

因此，假设一个级别的错误报告总是足够的似乎是错误的。因此，让我们提供一种 嵌套 标签的方法：

extension [A](p: Parser[A]) def scope(msg: String): Parser[A]

与标签不同，范围不会丢弃附加到p的标签 - 它只是在p失败时添加额外的信息。让我们指定这到底意味着什么。首先，我们修改从 解析错误 中提取信息的函数 .我们应该得到一个列表[（位置，字符串）]，而不是只包含单个位置和字符串消息：

case class ParseError(stack: List[(Location, String)])

ParseError 是一堆错误消息，指示解析器在失败时正在执行的操作。我们现在可以指定作用域的作用——如果 p.run（s） 是 Left（e1） ，那么 p.scope（msg） .run（s） 是 Left（e2） ，其中 e2.stack.head 将是 msg，e2.stack.tail 将是 e1。

我们可以稍后编写帮助程序函数，以使构造和操作 ParseError 值更加方便，并很好地格式化它们以供人类使用。目前，我们只想确保它包含错误报告的所有相关信息，并且似乎ParseError足以满足大多数目的。让我们选择它作为我们的具体表示，并从解析器中删除抽象类型参数：

trait Parsers[Parser[+_]]:
  extension [A](p: Parser[A])
    def run(input: String): Either[ParseError, A]
  ...

现在，我们将为 Parsers 实现提供构建漂亮的分层错误所需的所有信息（如果它愿意的话）。作为解析器库的用户，我们将明智地在我们的语法中加入标签和作用域调用，解析器实现可以在构造解析错误时使用这些调用。请注意，解析器的实现不使用 ParseError 的全部功能，只保留有关错误原因和位置的基本信息是完全合理的。

9.5.3 控制分支和回溯

关于错误报告，我们需要解决最后一个问题。正如我们刚才所讨论的，当我们在 or 组合器内部发生错误时，我们需要某种方法来确定要报告哪些错误。我们不想 为此只 制定一项全球公约;我们有时希望允许程序员控制这个选择。让我们看一个更具体的激励示例：

val spaces = string(" ").many
val p1 =
  (string("abra") ** spaces ** string("cadabra")).scope("magic spell")
val p2 =
  (string("abba") ** spaces ** string("babba")).scope("gibberish")
val p = p1 | p2

我们想从 p.run（“abra cAdabra”） 中获取什么 ParseError ？（再次注意 cAdabra 中的大写字母 A。或的两个分支都会在输入上产生错误。带有“胡言乱语”标签的解析器会因为期望第一个单词是“abba”而报告错误，而“魔术”解析器会因为“cAdabra”中的意外大写而报告错误。我们要向用户报告哪些错误？

在这种情况下，我们碰巧想要“魔术”解析错误;成功解析“abra”字后，我们将 致力于 OR的“魔法咒语”分支，这意味着如果我们遇到解析错误，我们不会检查OR的下一个分支。在其他情况下，我们可能希望允许解析器考虑 or 的下一个分支。

因此，我们似乎需要一个原语来让程序员指示何时提交到特定的解析分支。回想一下，我们松散地分配了 p1 |P2 表示尝试在输入上运行 P1 ，然后在 P2 失败时尝试在同一输入上运行 P1 。我们可以改变它的含义，尝试在输入上运行 p1，如果它在未提交状态下失败，请尝试在同一输入上运行 p2;否则，报告失败 。这不仅对提供良好的错误消息很有用，它还通过让实现避免检查大量可能的解析分支来提高效率。

此问题的一个常见解决方案是，如果所有解析器检查至少一个字符以生成结果，则默认情况下让所有解析器 提交 。 12 然后我们引入一个组合器，try ，它延迟提交到解析：

extension [A](p: Parser[A]) def attempt: Parser[A]

尝试组合器应该满足这样的要求： 13

def fail(msg: String): Parser[Nothing]        ①
 
p.flatMap(_ => fail("")).attempt | p2 == p2

（1） 新的解析器总是失败并显示提供的错误消息

这里的失败是一个总是失败的解析器。也就是说，即使 p 在检查输入的中途失败，也会尝试将提交恢复到该解析并允许运行 p2。每当语法中存在歧义时，都可以使用尝试组合器，并且可能需要检查多个标记才能解决歧义，并且解析可以提交到单个分支。例如，我们可以这样写：

((string("abra") ** spaces ** string("abra")).attempt **
  string("cadabra")) | ("abra" ** spaces ** "cadabra!")

假设这个解析器运行在“abra cadabra！”——在解析了第一个“abra”之后，我们不知道是期待另一个“abra”（第一个分支）还是“cadabra！（第二个分支）。通过尝试围绕 “abra” ** 空格 ** “abra” 进行包装，我们允许考虑第二个分支，直到我们完成解析第二个 “abra” ，此时我们提交到该分支。

你能想到任何其他原语可能有用的让程序员指定 or 链中的哪些错误被报告吗？

我们还没有写出代数的实现！但这个练习更多的是确保我们的组合器为我们库的用户提供了一种将正确的信息传达给实现的方法。由实施部门来弄清楚如何以满足我们规定的法律的方式使用这些信息。

9.6 实现代数

至此，我们已经充实了我们的代数，并据此定义了一个解析器[JSON]。 14 你不好奇尝试运行它吗？

让我们再次回顾一下我们的原语集：

• 字符串 — 识别并返回单个字符串
• 正则表达式 — 识别正则表达式 s
• p.slice —如果成功，则返回由 p 检查的输入部分
• p.label（e） — 发生故障时，将分配的消息替换为 e
• p.scope（e） — 如果失败，将 e 添加到 p 返回的错误堆栈中
• f.flatMap（p） — 运行解析器，然后使用其结果选择要按顺序运行的第二个解析器
• p.try — 延迟提交到 p 直到成功之后
• P1 |p2 — 在两个解析器之间进行选择，首先尝试 p1，如果 p2 在输入上处于未提交状态时失败，则尝试 p1

困难 ：在下一节中，我们将完成解析器的表示，并使用此表示实现解析器接口。但在我们这样做之前，试着自己想出一些想法。这是一个非常开放的设计任务，但我们设计的代数对可能的表示施加了强烈的约束。您应该能够提出一个简单的、纯函数式的解析器表示形式，可用于实现解析器接口。 15

您的代码可能如下所示：

class MyParser[+A](...):
  ...
 
object MyParsers extends Parsers[MyParser]:
  // implementations of primitives go here

将 MyParser 替换为用于表示解析器的任何数据类型。当你对某些东西感到满意、陷入困境或想要更多想法时，请继续阅读。

9.6.1 一种可能的实现

我们现在要讨论解析器的实现。我们的解析代数支持许多功能。与其直接跳到解析器的最终表示，我们将通过检查代数的原语并推理支持每个原语所需的信息来逐步构建它。

让我们从字符串组合器开始：

def string(s: String): Parser[A]

我们知道我们需要支持函数运行：

extension [A](p: Parser[A]) def run(input: String): Either[ParseError, A]

作为第一个猜测，我们可以假设我们的解析器只是 run 函数的实现：

opaque type Parser[+A] = String => Either[ParseError,A]

我们可以使用它来实现字符串原语：

def string(s: String): Parser[A] =
  input =>
    if input.startsWith(s) then
      Right(s)
    else
      Left(Location(input).toError("Expected: " + s))   ①

（1） 使用 toError（稍后定义）来构造 ParseError

else 分支必须建立一个 ParseError 。这些现在构造起来有点不方便，所以我们在位置上引入了一个辅助函数 toError ：

case class Location(input: String, offset: Int = 0):
  def toError(msg: String): ParseError =
    ParseError(List((this, msg)))

9.6.2 排序解析器

目前为止，一切都好。我们有一个解析器的表示形式，至少支持字符串。让我们继续对解析器进行排序。不幸的是，要表示像 string（“abra”） ** string（“cadabra”） 这样的解析器，我们现有的表示是不够的。如果 “abra” 的解析成功，那么我们要考虑 那些使用的 字符，并对其余字符运行 “cadabra” 解析器。因此，为了支持排序，我们需要一种方法来让解析器指示它消耗了多少个字符。捕获此内容非常简单： 16

opaque type Parser[+A] = Location => Result[A]            ①
 
enum Result[+A]:
  case Success(get: A, charsConsumed: Int)                ②
  case Failure(get: ParseError) extends Result[Nothing]   ③

（1） 解析器现在返回一个成功或失败的结果。

（2） 在成功的情况下，我们返回解析器消耗的字符数。

（3） 失败不引用类型参数 A，所以我们显式扩展 Result[Nothing]，这意味着我们在更改类型参数时不需要复制失败。

我们在这里引入了一个新类型， Result ，而不仅仅是使用 要么 。

如果成功，我们将返回类型 A 的值以及使用的输入字符数，调用方可以使用该值来更新 Location 状态。 17 这种类型开始理解解析器的本质——它是一种可能失败的状态操作，类似于我们在第 6 章中构建的内容。它接收输入状态，如果成功，它将返回一个值以及足够的信息来控制应如何更新状态。

这种理解——解析器只是一个状态行为——为我们提供了一种构建表示的方法，该表示支持我们规定的所有花哨的组合器和定律。我们只是考虑每个基元需要我们的状态类型跟踪的内容（只是一个位置可能还不够），并研究每个组合器如何转换此状态的细节。

实现字符串、正则表达式、成功和切片的解析器的初始表示。请注意，切片的效率低于它可能的效率，因为它仍然必须构造一个值才能丢弃它。我们稍后会回到这个问题。

9.6.3 标记解析器

向下移动我们的基元列表，接下来让我们看一下范围。如果失败，我们希望将新消息推送到 ParseError 堆栈上。让我们在 ParseError 上为此引入一个辅助函数;我们称之为推送： 18

case class ParseError(stack: List[(Location, String)] = Nil):
  def push(loc: Location, msg: String): ParseError =
    copy(stack = (loc, msg) :: stack)

有了这个，我们可以实现范围：

extension [A](p: Parser[A]) def scope(msg: String): Parser[A] =
  l => p(l).mapError(_.push(l, msg))                             ①

（1） 发生故障时，将 msg 推送到错误堆栈上。

函数 mapError 在 Result 上定义 — 它只是将函数应用于失败的情况：

def mapError(f: ParseError => ParseError): Result[A] = this match
  case Failure(e) => Failure(f(e))
  case _ => this

因为我们在内部解析器返回后推送到堆栈，所以堆栈底部将有稍后解析中发生的更详细的消息。例如，如果 （a ** b.scope（msg2））.scope（msg1） 在解析 b 时失败，那么堆栈上的第一个错误将是 msg1，然后是 a 生成的任何错误，然后是 msg2，最后是 b 生成的错误。

我们可以类似地实现标签，但它不是推送到错误堆栈上，而是替换已经存在的内容。我们可以使用 mapError 再次编写：

extension [A](p: Parser[A]) def label(msg: String): Parser[A] =
  l => p(l).mapError(_.label(msg))                               ①

（1） 在 ParseError 上调用一个帮助程序方法，该方法也称为 label

我们在 ParseError 中添加了一个辅助函数，也命名为 label。我们将做出一个设计决策，标记修剪错误堆栈，从内部范围切断更详细的消息，仅使用堆栈底部的最新位置：

case class ParseError(stack: List[(Location, String)] = Nil):
  def label(s: String): ParseError =
    ParseError(latestLoc.map((_, s)).toList)
 
  def latestLoc: Option[Location] =
    latest.map(_(0))
 
  def latest: Option[(Location, String)] =
    stack.lastOption                       ①

（1） 获取堆栈的最后一个元素，如果堆栈为空，则获取 None（如果堆栈为空）

考虑这个非负整数的解析器：

val nonNegativeInt: Parser[Int] =
  for
    nString <- regex("[0-9]+".r)
    n <- nString.toIntOption match
      case Some(n) => succeed(n)
      case None => fail("expected an integer")
  yield n

修改此实现以使用范围或标签在发生错误时提供更有意义的错误消息。

9.6.4 故障转移和回溯

现在让我们考虑或并尝试.回想一下我们为 or 的预期行为指定的内容：它应该运行第一个解析器，如果在 未提交状态下 失败，那么它应该在同一输入上运行第二个解析器。我们说过使用至少一个字符应该会导致提交的解析，并且 p.try 将 p 的已提交失败转换为未提交的失败。

我们可以通过在 Result 的失败案例中添加一条信息来支持我们想要的行为 - 一个布尔值，指示解析器是否在提交状态下失败：

case Failure(get: ParseError, isCommitted: Boolean)

尝试的实现只是取消对发生的任何失败的承诺。它使用了一个辅助函数， uncommit ，我们可以在 Result 上定义它：

extension [A](p: Parser[A]) def attempt: Parser[A] =
  l => p(l).uncommit
 
enum Result[+A]:
  ...
  def uncommit: Result[A] = this match
    case Failure(e, true) => Failure(e, false)
    case _ => this

现在的实现或可以在运行第二个解析器之前简单地检查isCommit 标志。在解析器p或p2中，如果p成功，那么整个事情就会成功。如果 p 在提交状态下失败，我们将提前失败并跳过运行 p2 。否则，如果 p 在未提交状态下失败，那么我们运行 p2 并忽略 p 的结果：

extension [A](p: Parser[A]) def or(p2: => Parser[A]): Parser[A] =
  l => p(l) match
    case Failure(e, false) => p2(s)
    case r => r                     ①

（2） 提交失败或成功跳过运行 p<>

9.6.5 上下文相关解析

现在是我们列表中的最后一个基元： 平面地图 .回想一下，flatMap 通过允许选择第二个解析器依赖于第一个解析器的结果来启用上下文相关解析器。实现很简单：我们在调用第二个解析器之前推进位置。同样，我们使用一个辅助函数， 前进由 ， 在位置 .有一个微妙之处 — 如果第一个解析器使用任何字符，我们确保第二个解析器被提交，使用一个帮助函数 addCommit ， 在 ParseError 上。

示例 9.3 使用 addCommit 来确保我们的解析器已提交

extension [A](p: Parser[A]) def flatMap[B](f: A => Parser[B]): Parser[B] =
  l => p(l) match
    case Success(a, n) => f(a)(l.advanceBy(n))    ①
                            .addCommit(n != 0)    ②
                            .advanceSuccess(n)    ③
    case f @ Failure(_, _) => f                   ④

（1） 在调用第二个解析器之前提前源位置。

（2） 如果第一个解析器消耗了任何字符，则提交。

（3） 如果成功，我们增加 n 消耗的字符数，以考虑 p 已经消耗的字符数。

（4） 因为 Failure 扩展了 Result[Nothing] 并且 Result 在其唯一的类型参数中是协变的，我们可以在这里直接返回 f。

进步有明显的实现。我们只需增加偏移量：

def advanceBy(n: Int): Location =
  copy(offset = offset + n)

同样，在 ParseError 上定义的 addCommit 也很简单：

def addCommit(isCommitted: Boolean): Result[A] = this match
  case Failure(e, c) => Failure(e, c || isCommitted)
  case _ => this

最后，advanceSuccess 会增加成功结果消耗的字符数。我们希望 flatMap 消耗的字符总数是解析器 p 和 f 生成的解析器消耗的字符之和。我们在 f 的结果上使用 advanceSuccess 来确保这一点：

def advanceSuccess(n: Int): Result[A] = this match
  case Success(a, m) => Success(a, n + m)
  case _ => this                             ①

（1）如果不成功，则不要管结果。

使用解析器的这种表示实现其余的原语，包括 run ，并尝试在各种输入上运行 JSON 解析器。不幸的是，您会发现这种表示会导致大型输入的堆栈溢出（例如，[1，2，3,...10000] ).对此的一种简单解决方案是提供许多的专用实现，避免对正在构建的列表的每个元素使用堆栈帧。只要任何重复的组合子都是用许多（它们都可以是）来定义的，这就解决了问题。

想出一种格式化 ParseError 以供人类使用的好方法。有许多选择需要做出，但关键的见解是，在将错误显示为字符串以供显示时，我们通常希望合并或分组附加到同一位置的标签。

困难 ：切片组合器的效率仍然低于预期。例如，char（'a'）.many.slice 仍然会建立一个 List[Char]，只是为了丢弃它。你能想到一种修改解析器表示以使切片更有效的方法吗？

当我们将解析器与 or 组合器结合使用时，某些信息会丢失。如果两个解析器都失败，我们只保留第二个解析器的错误。但是我们可能希望同时显示错误消息，或者从哪个分支中选择错误而不会失败。 更改 ParseError 的表示形式以跟踪分析器的其他分支中发生的错误。

9.7 结论

在本章中，我们介绍了 代数 设计，这是一种编写组合器库的方法，并使用它来设计解析器库并实现 JSON 解析器。一路走来，我们发现了许多类似于我们在前几章中看到的组合子，它们再次与熟悉的定律相关。在第 3 部分中，我们将最终了解这些库之间连接的本质，并学习如何抽象它们的共同结构。

这是第 2 部分的最后一章。我们希望您从这些章节中对函数式设计如何进行有一个基本的了解，更重要的是，我们希望这些章节能激励您尝试 为您感兴趣的任何 领域设计自己的函数库。函数式设计不仅仅是为专家保留的东西——它应该是各种经验水平的函数式程序员日常工作的一部分。在开始第 3 部分之前，我们鼓励您尝试阅读本书之外的内容，编写一些功能更强大的代码，并设计一些自己的库。玩得开心，享受与出现的设计问题作斗争，看看你发现了什么。当你回来时，在第 3 部分中等待着一个模式和抽象的世界。

总结

• 解析器将一系列非结构化数据转换为结构化表示形式。
• 解析器组合器库允许通过组合简单的基元解析器和通用组合器来构造解析器。
• 相反，解析器生成器库基于语法规范构造解析器。
• 代数设计是首先设计接口和相关定律，然后用于指导数据类型表示选择的过程。
• 明智地使用中缀运算符，使用符号定义，如 |或者使用 infix 关键字（如 或 ）可以使组合器库更易于使用。
• 多组合器创建一个解析器，该解析器解析输入解析器的零个或多个重复，并返回已解析值的列表。
• many1 组合器与 many 类似，但解析一个或多个重复。
• 产品组合器（或 ** 运算符）从两个输入分析器创建一个分析器，该分析器运行第一个分析器，如果成功，则对其余输入运行第二个分析器。每个输入分析器的结果值在元组中返回。
• map、map2 和平面映射操作对于构建复合解析器很有用。特别是，flatMap 允许创建上下文相关的解析器。
• 标签和作用域组合器允许在解析失败时生成更好的错误消息。
• 可以通过选择基元操作、构建组合器以及决定这些操作和组合器应如何交互来设计 API。
• API 设计是一个迭代过程，其中操作之间的交互、示例用法和实现困难都会导致该过程。

9.8 练习答案

取 p 和 p2 的乘积给我们一个解析器[（A， B）]。然后，我们使用提供的函数 f 映射它以获得解析器[C]：

extension [A](p: Parser[A])
  def map2[B, C](p2: Parser[B])(f: (A, B) => C): Parser[C] =
    p.product(p2).map((a, b) => f(a, b))

为了实现 many1，我们使用 map2 将 p 和 p.many 的结果组合到一个列表中，方法是将 p 的结果组合到 p.many 的结果上：

extension [A](p: Parser[A])
  def many1: Parser[List[A]] =
    p.map2(p.many)(_ :: _)

产品操作是关联的。这两个表达式大致相等：

(a ** b) ** c
a ** (b ** c)

唯一的区别是配对的嵌套方式。（a ** b） ** c 解析器返回 an （（A， B）， C） ，而 a ** （b ** c） 返回 （A， （B， C））。我们可以定义函数 unbiasL 和 unbiasR 将这些嵌套元组转换为平面 3 元组：

def unbiasL[A, B, C](p: ((A, B), C)): (A, B, C) = (p(0)(0), p(0)(1), p(1))
def unbiasR[A, B, C](p: (A, (B, C))): (A, B, C) = (p(0), p(1)(0), p(1)(1))

有了这些，我们现在可以声明关联性属性：

((a ** b) ** c).map(unbiasL) == (a ** (b ** c)).map(unbiasR)

我们有时会在双方之间存在明显的双射时使用 ~=：

(a ** b) ** c ~= a ** (b ** c)

地图和产品也有有趣的关系;我们可以在获取两个解析器的乘积之前或之后进行映射，而不会影响行为：

a.map(f) ** b.map(g) == (a ** b).map((a,b) => (f(a), g(b)))

例如，如果 a 和 b 都是 Parser[String]，并且 f 和 g 都计算字符串的长度，那么我们是否映射到 a 的结果以计算其长度或我们是否在乘积 之后 这样做都无关紧要。有关这些法律的更多讨论，请参阅第12章。

我们使用与练习 1.9 中的 many1 相同的方法，使用带有缺点的 map2 来构建列表。当由于耗尽输入或其他原因而失败时，我们成功使用空列表：

extension [A](p: Parser[A])
  def many: Parser[List[A]] =
    p.map2(p.many)(_ :: _) | succeed(Nil)

但是，这个实现有一个问题：我们递归调用 p.many ，并且我们的 map2 实现严格接受它的参数，导致堆栈溢出。为了纠正这一点，我们需要更改 map2 以非严格地采用解析器参数。我们将在本章的下一节中更深入地研究这一点。

listOfN 与许多元素非常相似 — 唯一的区别是对要解析的元素数量的限制。因此，我们可以通过类似的 map2 技术来实现它，并在每次迭代中递归调用 listOfN（n - 1）。当 n 达到零时，我们成功获得空列表：

extension [A](p: Parser[A])
  def listOfN(n: Int): Parser[List[A]] =
    if n <= 0 then succeed(Nil)
    else p.map2(p.listOfN(n - 1))(_ :: _)

我们需要一种方法来延迟解析器的创建。我们可以通过一个新的构造函数来做到这一点，该构造函数采用一个按名称解析器参数并延迟对该参数的评估，直到它尝试解析某些内容：

def defer[A](p: => Parser[A]): Parser[A]

请注意，我们不需要 defer 的实现。我们假设它是一个由解析器特征的实现提供的原语。 19

extension [A](p: Parser[A])
  def many: Parser[List[A]] =
    p.map2(defer(p.many))(_ :: _) | succeed(Nil)

在并行性章节中，我们特别感兴趣的是避免Par对象花费与相应的串行计算一样多的时间和空间来构建，而延迟组合器让我们更仔细地控制这一点。这在这里不是什么大问题，每次我们 map2 决定是否需要调用 defer 时都必须仔细考虑，这对于 API 的用户来说似乎是不必要的摩擦。

让我们将这个问题分成两部分 — 解析一个非负整数，然后解析指定数量的“a”字符：

val nonNegativeInt: Parser[Int] =
  for
    nString <- regex("[0-9]+".r)                 ①
    n <- nString.toIntOption match               ②
      case Some(n) => succeed(n)                 ③
      case None => fail("expected an integer")   ④
  yield n

（1） 使用正则表达式解析一个或多个数字字符。

（2）将解析的数字字符串转换为整数。

（3） 如果整数转换成功，则通过成功返回解析后的值作为解析器。

（4） 否则，返回解析器，该解析器失败并显示错误消息。

我们在正则表达式解析器上使用 flatMap 来进一步验证和转换解析的字符串——在本例中，将字符串转换为整数。我们必须创建一个新的原语， 失败 ，它构造了一个解析器，该解析器总是失败并显示提供的错误消息。

使用nonNegativeInt，我们可以使用flatMap使用我们已经定义的各种组合器来实现nConsecutiveAs：

val nConsecutiveAs: Parser[Int] =
  for
    n <- nonNegativeInt
    _ <- char('a').listOfN(n)
  yield n                      ①

（1） 我们选择返回解析的“a”字符的数量，而不是返回解析的字符串

乘积和 map2 都可以用理解来实现，它们绑定 p 和 p2 的结果，然后组合这些结果：

extension [A](p: Parser[A])
  def product[B](p2: => B): Parser[(A, B)] =
    for
      a <- p
      b <- p2
    yield (a, b)
 
  def map2[B, C](p2: => B)(f: (A, B) => C): Parser[C] =
    for
      a <- p
      b <- p2
    yield f(a, b)

我们可以使用 flatMap 实现 map 并成功：

extension [A](p: Parser[A])
  def map[B](f: A => B): Parser[B] =
    p.flatMap(a => succeed(f(a)))

JSON 文档以数组或对象开头。让我们从草图开始，根据需要发明新的解析器：

def document: Parser[JSON] = array | obj
def array: Parser[JSON] = ???
def obj: Parser[JSON] = ???

让我们也丢弃文档开头的任何空格。我们可以通过为空格编写一个解析器并将其与数组 |obj ：

def whitespace: Parser[String] = Parser.regex("\\s*".r)
def document: Parser[JSON] = whitespace.map2(array | obj)((_, doc) => doc)

我们使用 map2 并丢弃了解析后的空格。我们可以提取一个更通用的组合器，它结合了两个解析器并丢弃第一个解析器的结果。同样，我们可以丢弃正确解析器的结果：

extension [A](p: Parser[A])
  def *>[B](p2: => Parser[B]): Parser[B] = p.map2(p2)((_, b) => b)
  def <*[B](p2: => Parser[B]): Parser[A] = p.map2(p2)((a, _) => a)
 
def document: Parser[JSON] = whitespace *> (array | obj)

我们将这些组合器命名为 <* 和 *> — 箭头指向保留结果的方向。最后，让我们确保在解析的数组或对象之后没有剩余的输入：

def eof: Parser[String] =
  regex("\\z".r).label("unexpected trailing characters")
 
def document: Parser[JSON] = whitespace *> (array | obj) <* eof

在这里，我们定义了一个 eof 解析器，该解析器仅在给定空输入字符串时成功。我们使用了正则表达式解析器和 \z 模式，尽管我们可以手动将其写出来。

现在让我们实现一些未定义的解析器。JSON 数组是用方括号括起来的逗号分隔值 （CSV） 的列表。我们需要一个 JSON 值的解析器，以及一种表达由其他解析器分隔的元素列表的方法。让我们勾勒一下：

val value: Parser[JSON] = ???
 
extension [A](p: Parser[A])
  def sep(separator: Parser[Any]): Parser[List[A]] = ???
 
def array: Parser[JSON] =
  string("[") *> value.sep(string(",")).map(vs =>
    JArray(vs.toIndexedSeq)) <* string("]")

sep方法与许多方法类似，但是在重复原始解析器之前，它会解析一个分隔符，然后将其丢弃（因此sep的参数具有Parser[Any]类型）。我们可以以与许多类似的方式实现 sep — 使用解析一个或多个值的变体：

extension [A](p: Parser[A])
  def sep(separator: Parser[Any]): Parser[List[A]] =
    p.sep1(separator) | succeed(Nil)
 
  def sep1(separator: Parser[Any]): Parser[List[A]] =
    p.map2((separator *> p).many)(_ :: _)

sep1 操作很有趣，因为它将 p 与许多分隔符 *> p 迭代的结果相结合。

这个版本的数组的一个问题是我们不处理空格。此外，我们的令牌解析器（例如，[、] 和 ， ）被提交，这意味着如果它们不匹配，那么它们将无法进行整体解析，而不是允许通过 or 进行交替。让我们创建一个新的构造函数来解决这两个问题：

def token(s: String): Parser[String] =
  string(s).attempt <* whitespace
 
def array: Parser[JSON] =
  token("[") *> value.sep(token(",")).map(vs =>
    JArray(vs.toIndexedSeq)) <* token("]")

最后，让我们使用作用域组合器在解析数组失败时提供更多错误信息：

def array: Parser[JSON] = (
  token("[") *> value.sep(token(",")).map(vs =>
    JArray(vs.toIndexedSeq)) <* token("]")
).scope("array")

现在让我们实现值解析器。JSON 值可以是文本、数组或对象。文字是以下之一：* 空 * 一个数字 * 一个带引号的字符串 * 真或假。

我们可以直接将其转换为解析器：

def value: Parser[JSON] = lit | obj | array
 
def lit: Parser[JSON] = (
  token("null").as(JNull) |
  double.map(JNumber(_)) |
  escapedQuoted.map(JString(_)) |
  token("true").as(JBool(true)) |
  token("false").as(JBool(false))
).scope("literal")
 
def double: Parser[Double] = ???
def escapedQuoted: Parser[String] = ???

双精度和转义引号解析器在此处未定义，但有关完整定义，请参阅 GitHub 存储库中的答案。

最后，让我们实现前面的 obj 解析器。JSON 对象是以逗号分隔的键值对列表，用大括号括起来，其中每个键都是带引号的字符串，值通过 ： 标记与键分隔：

def obj: Parser[JSON] = (
  token("{") *> keyval.sep(token(",")).map(kvs =>
    JObject(kvs.toMap)) <* token("}")
).scope("object")
 
def keyval: Parser[(String, JSON)] = escapedQuoted ** (token(":") *> value)

以下部分详细介绍了一种可能的设计。

返回使用最多字符数后发生的错误，并返回最近遇到的错误。

以下部分详细介绍了一种可能的设计。

要实现字符串，我们需要检查输入是否以提供的字符串开头，如果没有，则报告一个错误，指示哪个字符不匹配。我们将使用一个辅助函数 firstNonmatchingIndex ，来做到这一点。firstNonmatchingIndex的细节在这里省略了，但请参阅Github存储库以获取完整的实现：

def firstNonmatchingIndex(s1: String, s2: String, offset: Int): Int = ...
 
def string(w: String): Parser[String] =
  l =>
    val i = firstNonmatchingIndex(l.input, w, l.offset)
    if i == -1 then
      Success(w, w.length)
    else
      Failure(l.advanceBy(i).toError(s"'$w'"))     ①

（1） 我们在位置中添加了一个 advanceBy 方法，该方法将偏移量增加指定的量。

为了实现正则表达式，我们可以在正则表达式上使用内置的 findPrefixOf 方法，传递剩余的输入。其余输入可通过 l.input.substring （l.offset） 获得：

def regex(r: Regex): Parser[String] =
  l => r.findPrefixOf(l.input.substring(l.offset)) match
    case Some(m) => Success(m, m.length)
    case None => Failure(l.toError(s"regex $r"))

成功的实现很简单 — 我们完全忽略输入并返回具有指定值的 Success，并指示未使用任何输入：

def succeed[A](a: A): Parser[A] =
  _ => Success(a, 0)

最后，切片 ;在这里，我们运行包装的解析器，并在成功后返回原始输入的子字符串，其长度等于包装的解析器使用的字符数，从当前偏移量开始：

extension [A](p: Parser[A])
  def slice: Parser[String] =
    l => p(l) match
      case Success(_, n) =>
        Success(l.input.substring(l.offset, l.offset + n), n)
      case f @ Failure(e) => f

我们可以用 标签 .这样做会将任何引发的错误替换为更简单的错误消息，指示需要非负整数。如果我们想保留原始错误细节，我们可以选择范围：

val nonNegativeIntOpaque: Parser[Int] =
  nonNegativeInt.label("non-negative integer")

请参阅 GitHub 存储库中的完整实现：https://mng.bz/QWoj。

让我们首先编写一个函数，将在同一位置发生的错误折叠为一条错误消息：

def collapseStack(s: List[(Location, String)]): List[(Location, String)] =
  s.groupBy(_(0)).
    view.
    mapValues(_.map(_(1)).mkString("; ")).
    toList.sortBy(_(0).offset)

我们使用 groupBy 函数创建了一个 Map[Location， List[（Location， String）]。然后，我们通过丢弃冗余位置并连接错误消息（用分号分隔）来转换每个内部列表。最后，我们将结果转换为列表并按位置排序，确保错误按照输入字符串中发生的顺序报告。

现在让我们在 ParseError 上的 toString 实现中使用这个函数：

override def toString: String =
  if stack.isEmpty then "no error message"
  else
    val collapsed = collapseStack(stack)
    val context =
      collapsed.lastOption.map("\n\n" + _(0).currentLine).getOrElse("") +
      collapsed.lastOption.map("\n" + _(0).columnCaret).getOrElse("")
    collapsed.map((loc, msg) =>
      s"${formatLoc(loc)} $msg").mkString("\n") + context

此实现打印折叠列表中的每个错误以及发生该错误的行和列。对于堆栈中的最后一个错误，我们包含了无法解析的输入行以及指向该行中发生错误的字符的插入符号。这利用了几个实用程序函数;有关详细信息，请参阅 GitHub 存储库中的完整实现：http://mng.bz/4jPV。

关键思想是引入一个新的状态片段：一个布尔标志，指示解析器是否被切片包围，表明其结果将被丢弃。为此，我们需要引入一个表示我们状态的新类型：

case class ParseState(loc: Location, isSliced: Boolean)

然后修改我们对解析器的定义以使用此新状态类型：

opaque type Parser[+A] = ParseState => Result[A]

我们还需要为结果类型引入一个新案例，指示结果是输入的一部分，而不是成功解析的类型 A 或失败的值。为此，我们需要将 Result 从枚举转换为密封特征，每种情况都有子类型：

sealed trait Result[+A]
case class Success[+A](get: A, length: Int) extends Result[A]
case class Failure(
  get: ParseError, isCommitted: Boolean) extends Result[Nothing]
case class Slice(length: Int) extends Result[String]

切片类型采用单个参数，即切片的输入字符数。请注意，切片扩展了结果[字符串];这是广义代数数据类型 （GADT） 的一个示例。GADT 类似于常规代数数据类型，除了一个或多个情况 优化一个或多个 类型参数。在这种情况下，Slice 将类型 A 固定为 字符串 。当我们在 Result[A] 上进行模式匹配并与 Slice 案例匹配时，Scala 知道 A 是一个字符串，并且可以在进一步的类型检查中使用该信息。例如，考虑为解析器定义的映射的覆盖：

override def map[B](f: A => B): Parser[B] =
  s => p(s) match
    case Success(a, n) => Success(f(a), n)
    case Slice(n) => Success(f(s.slice(n)), n)
    case f @ Failure(_, _) => f

在 Slice 的情况下，Scala 可以推断我们的解析器 p 必须是 Parser[String] 类型，否则解析不会返回 Slice 值。因此，它知道函数 f 必须是从字符串到 B 的函数，并随后允许返回字符串的 s.slice（n） 应用于 f。

有了这些定义，我们可以修改切片组合器，在解析器状态上设置 isSliced 标志：

extension [A](p: Parser[A])
  def slice: Parser[String] =
    s => p(s.copy(isSliced = true)) match
      case s @ Slice(_) => s
      case Success(_, length) => Slice(length)
      case f @ Failure(_, _) => f

切片组合器还会转换输出结果，确保我们将任何成功案例替换为切片案例。

最后，我们需要在各种组合器中使用 isSliced，优化它们以在 isSliced 为真时跳过结果的计算。以下是我们如何为许多人做到这一点：

override def many: Parser[List[A]] =
  s =>
    var nConsumed: Int = 0
    if s.isSliced then
      def go(p: Parser[String], offset: Int): Result[String] =
        p(s.advanceBy(offset)) match
          case f @ Failure(e, true) => f
          case Failure(e, _) => Slice(offset)
          case Slice(n) => go(p, offset + n)
          case Success(_, _) =>
            sys.error("sliced parser should not return success, only slice")
      go(p.slice, 0).asInstanceOf[Result[List[A]]]
    else
      val buf = new collection.mutable.ListBuffer[A]
      def go(p: Parser[A], offset: Int): Result[List[A]] =
        p(s.advanceBy(offset)) match
          case Success(a, n) =>
            buf += a
            go(p, offset + n)
          case f @ Failure(e, true) => f
          case Failure(e, _) => Success(buf.toList, offset)
          case Slice(n) =>
            buf += s.input.substring(offset, offset + n)
            go(p, offset + n)
      go(p, 0)

这里有很多东西！如果状态表明我们被切片了，那么我们使用递归函数来解析直到失败——但至关重要的是， 不要 累积每次迭代的结果！遇到未提交的故障时，将返回一个 Slice，指示已消耗的字符数。这里的演员看起来有点令人担忧，但它是完全安全的。我们知道结果是切片的，因此永远不会检查输出列表[A]。相反，如果状态表明我们没有被切片，那么我们使用类似的递归函数，但这次我们将每个解析的值累积到缓冲区中。

其他各种组合器将需要了解切片（例如，map2和flatMap）。有关完整详细信息，请参阅 GitHub 存储库：http://mng.bz/vovM。

让我们修改 ParserError 以存储解析时发生的其他错误：

case class ParseError(stack: List[(Location,String)] = Nil,
                      otherFailures: List[ParseError] = Nil):
 
  def addFailure(e: ParseError): ParseError =
    copy(otherFailures = e :: otherFailures)

然后，我们可以实现或以跟踪两个分支的错误的方式：

extension [A](p: Parser[A])
  infix def or(p2: => Parser[A]): Parser[A] =
    s => p(s) match
      case Failure(e, false) => p2(s).mapError(_.addFailure(e))
      case r => r

但是，此更改需要其他更改。我们需要更新 ParseError 的 toString，以有用且直观的方式呈现这些其他故障。我们还应该引入一些组合器来修剪解析错误或以其他方式过滤故障以最相关。

1 有关不同功能设计方法的更多信息，请参阅本章的章节注释（https://github.com/fpinscala/ fpinscala/wiki）。

2 正如我们将看到的，解析器的代数与计算机科学研究的语言类（即常规、上下文无关和上下文敏感）之间存在联系。

3 Scala 标准库曾经包含一个解析器组合器库，尽管它被移到了自己的存储库中，现在由社区维护。还有许多其他流行的开源解析器组合器库，提供了广泛的功能，包括 cats-parse 和 FastParse。与上一章一样，我们从第一原则派生出我们自己的图书馆，部分出于教学目的，以及进一步鼓励没有图书馆是权威的想法。

4 这当然是一个简化的设计选择。我们可以以一定的成本使解析库更加通用。有关更多讨论，请参阅章节注释 （https://github.com/fpinscala/fpinscala/wiki）。

5 我们将在接下来的几章中对此进行更多讨论。

6 这应该让你想起我们在上一章中写的一个类似的函数。

7 这种观点也可能与面向对象（OO）设计有关，尽管OO传统上不太强调代数定律。此外，在 OO 中封装的一个重要原因是对象通常具有一些可变状态，并且将其公开将允许客户端代码违反不变量。这种担忧与FP无关。

8 同样，有关更多示例，请参阅章节代码。为了缩短本章，我们不会给出所有定律的 Prop 实现，但这并不意味着您不应该自己编写它们！

9 这是一个设计选择。您可能希望考虑拥有 或 始终同时运行 p 和 p2 的版本的后果。

10 从理论上讲，这是没有必要的;我们可以写出字符串（“0”） |字符串（“1”） |...string（“9”） 来识别单个数字，但这不太可能非常有效。

11 关于替代办法的讨论，见章节注释（https://github.com/fpinscala/fpinscala/wiki）。

12 有关这方面的更多讨论，请参阅章节注释（https://github.com/fpinscala/fpinscala/wiki）。

13 这并不完全是平等的。即使我们想在尝试的解析器失败时运行 p2，我们也可能希望 p2 在失败时以某种方式合并来自两个分支的错误。

14 您可能希望重新访问解析器，以使用我们在上一节中讨论的一些错误报告组合器。

15 请注意，如果您在实现解析器后尝试运行 JSON 解析器，则可能会收到堆栈溢出错误。有关此内容的讨论，请参阅下一节的末尾。

16 回想一下，位置包含完整的输入字符串和此字符串的偏移量。

17 请注意，返回 （A， Location） 将使解析器能够更改存储在 Location 中的输入。这赋予它太多了权力！

18 复制方法免费提供任何案例类。它返回对象的副本，但修改了一个或多个属性。如果没有为字段指定新值，则该字段的值将与原始对象中的值相同。在幕后，这使用 Scala 中默认参数的普通机制。

19 或者，我们可以用成功和平面映射来实现 defer，尽管我们直到本章后面才定义 flatMap。