解析器组合子：从基础到JSON解析与错误处理

# 解析器组合子：从基础到JSON解析与错误处理 ## 1. 切片与非空重复 在解析任务中，`many` 和 `map` 的组合可以用于统计 'a' 字符的数量，但构建一个 `List[Char]` 然后丢弃其值并提取长度的做法效率不高。为了直接获取解析器检查的输入字符串部分，我们引入了 `slice` 组合子： ```scala extension [A](p: Parser[A]) def slice: Parser[String] ``` `slice` 组合子用于在解析成功时返回解析器检查的输入字符串部分。例如，`(char('a') | char('b')).many.slice.run("aaba")` 会返回 `Right("aaba")`，我们忽略 `many` 积累的列表，直接返回解析器匹配的输入字符串部分。 有了 `slice`，统计 'a' 字符数量的解析器可以写成： ```scala char('a').many.slice.map(_.size) ``` 这里的 `_.size` 函数引用的是 `String` 的 `size` 方法，时间复杂度为常数，而不是 `List` 的 `size` 方法，后者的时间复杂度与列表长度成正比。 接着，我们考虑识别一个或多个 'a' 字符的情况。为此，我们引入了 `many1` 组合子： ```scala extension [A](p: Parser[A]) def many1: Parser[List[A]] ``` `many1` 可以通过 `many` 来定义，因为 `p.many1` 实际上就是 `p` 后面跟着 `p.many`。这就需要一个组合子来依次运行两个解析器，并返回它们的结果对： ```scala extension [A](p: Parser[A]) def product[B](p2: Parser[B]): Parser[(A, B)] def **[B](p2: Parser[B]): Parser[(A, B)] = product(p2) ``` ### 练习 9.1 使用 `product` 实现 `map2` 组合子，然后使用 `map2` 和 `many` 实现 `many1`。 ### 练习 9.2 尝试为 `product` 组合子制定行为规则。 ## 2. 可能的代数 我们定义了 `map2` 组合子： ```scala extension [A](p: Parser[A]) def map2[B, C](p2: Parser[B])(f: (A, B) => C): Parser[C] ``` 有了 `many1`，我们可以实现解析零个或多个 'a' 后面跟着一个或多个 'b' 的解析器： ```scala char('a').many.slice.map(_.size) ** char('b').many1.slice.map(_.size) ``` 现在思考 `many` 是否真的是原始组合子。`p.many` 会不断尝试运行 `p`，直到解析 `p` 失败，然后将所有成功运行 `p` 的结果累积到一个列表中。如果 `p` 一开始就失败，解析器将返回空列表。 ### 练习 9.3 在继续之前，尝试用 `|`、`map2` 和 `succeed` 定义 `many`。 ### 练习 9.4 使用 `map2` 和 `succeed` 实现之前的 `listOfN` 组合子： ```scala extension [A](p: Parser[A]) def listOfN(n: Int): Parser[List[A]] ``` 我们尝试用 `|`、`map2` 和 `succeed` 实现 `many`： ```scala extension [A](p: Parser[A]) def many: Parser[List[A]] = p.map2(p.many)(_ :: _) | succeed(Nil) ``` 但这个实现存在问题，因为 `map2` 会严格计算其第二个参数，导致 `many` 函数会无限递归调用，无法终止。因此，我们需要让 `product` 和 `map2` 的第二个参数变为非严格求值： ```scala 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)) ``` ### 练习 9.5 我们也可以使用单独的组合子来处理非严格求值，尝试这种方法并对现有的组合子进行必要的更改。 此外，我们还需要让 `or` 组合子的第二个参数变为非严格求值： ```scala extension [A](p: Parser[A]) infix def ```