PointFree Episode 57:What Is a Parser?: Part 2

1. PointFree Episode 57:What Is a Parser?: Part 2
1. What is a parser?
1. Parsing as a multi-step process
1. Optimized parsing with inout
1. Optimized parsing with substring
1. Till next time

2. What is a parser?

根据我们刚才所做的工作，我们可以将解析器定义为从字符串到其他类型的函数。我们甚至可以将其定义为一个简单的类型别名：

typealias Parser<A> = (String) -> A

给它一个合适的类型会很方便，这样我们就可以用方法来扩展它，所以让我们将函数包装在一个结构中：

struct Parser<A> {
  let run: (String) -> A
}

然而，目前解析器的形状并不十分正确，因为解析并不总是保证成功并产生值。总会有一些格式不正确的数据块，我们就是无法解析它。那么，让我们来介绍一些故障性：

struct Parser<A> {
  let run: (String) -> A?
}

这种简单的类型在应用程序开发中经常出现。我们通常拥有非结构化数据，比如一个裸字符串，并希望将其转换为结构化数据。例如，iOS应用程序中的深度链接路由可以被视为解析器：

let router = Parser<Route> { str in
  fatalError()
}

Route表示应用程序中支持的路由树，例如：

enum Route {
  case home
  case profile
  case episodes
  case episode(id: Int)
}

如果我们可以构造该router值，那么每当深度链接请求通过我们的应用程序委托时，我们只需在其上运行解析器，从中获取一级Router值，switch该值，然后执行一些基本逻辑以在我们的应用程序中显示正确的屏幕：

router.run("/")
// .home

router.run("/episodes/42")
// .episode(42)

一旦你有了这个设备，你就可以使用switch语句来路由传入的深度链接。

switch router.run("/") {
case .none:
case .some(.home):
case .some(.profile):
case .some(.episodes):
case let .some(.episode(id)):
}

我们还可以将命令行工具视为解析器：

let cli = Parser<EnumPropertyGenerator> { _ in
  fatalError()
}

EnumPropertyGenerator表示可以使用该工具的所有方式。

enum EnumPropertyGenerator {
  case help
  case version
  case invoke(urls: [URL], dryRun: Bool)
}

就像我们的路由器一样，如果我们构造其中一个值，我们可以switch它来处理输入。

cli.run("generate-enum-properties --version")
// .version

cli.run("generate-enum-properties --help")
// .help

cli.run("generate-enum-properties --dry-run path/to/file")
// .invoke(urls: ["path/to/file"], dryRun: true)

switch cli.run("generate-enum-properties --dry-run path/to/file") {
case .none:
case .some(.help):
case .some(.version):
case let .some(.invoke(urls, dryRun)):
}

3. Parsing as a multi-step process

因此，尽管我们可以看到拥有这些解析器是多么有用，但到目前为止我们定义的类型仍然不太正确。创建这样一个解析器意味着我们必须明确回答如何将字符串转换为A值的问题，因此这不利于创建能够进行少量解析的小型解析器，并将它们拼接到能够解析大型事物的解析器中。

一种方法是将解析视为一个多步骤的过程，并且解析器类型应该只描述该过程中的一个步骤。这意味着更改函数签名以返回与要解析的字符串其余部分一起的结果。

我们希望为Parser类型提供此功能。解析的一个步骤是使用输入字符串的一些子集，然后返回要解析的字符串的剩余部分以及解析结果。

struct Parser<A> {
  let run: (String) -> (match: A?, rest: String)
}

作为一个非常简单的示例，让我们构建一个整数解析器。如果可能的话，它将解析字符串开头的整数，并将其与字符串的其余部分一起返回。让我们从解析器的基本设置开始：

let int = Parser<Int> { str in
  // (Int?, String)
}

不知何故，在这里，我们必须返回一个新字符串，该字符串表示在我们从开头消耗了一个整数之后的输入字符串，以及将消耗的前缀转换为字符串的结果。让我们从获取给定字符串的所有数字字符的前缀开始：

let int = Parser<Int> { str in
  let prefix = str.prefix(while: { $0.isNumber })

然后，我们可以尝试使用Int初始化器将此前缀转换为整数。

let int = Parser<Int> { str in
  let prefix = str.prefix(while: { $0.isNumber })
  let int = Int(prefix)

但是，这是一个失败的操作，如果字符串的前缀不是数字，int将是nil，因此我们希望防止这种情况，并通过返回nil和原始字符串来避免，因为如果解析失败，我们不希望使用任何字符串。

let int = Parser<Int> { str in
  let prefix = str.prefix(while: { $0.isNumber })
  guard let int = Int(prefix) else { return (nil, str) }

我们越来越接近了，我们有了想要返回的整数，但是我们没有使用的字符串的“rest”。如果执行此操作，我们可以使用其结束索引返回未使用的字符：

let int = Parser<Int> { str in
  let prefix = str.prefix(while: { $0.isNumber })
  guard let int = Int(prefix) else { return (nil, str) }
  let rest = String(str[prefix.endIndex...])
  return (int, rest)
}

这是我们的第一个解析器！这有点复杂，我们正在使用字符串索引，这可能很棘手，但它应该封装从字符串开头解析整数的所有含义。

让我们来试一试：

int.run("42")
// (match 42, rest "")

int.run("42 Hello World")
// (match 42, rest " Hello World"

int.run("Hello World")
// (match nil, rest "Hello World"

就像这样，我们已经创建了一个解析器。它可能看起来不多，但这个小单元将成为许多令人惊奇的事情的基础。

4. Optimized parsing with inout

但是在我们继续开发解析器类型之前，让我们先讨论一些快速优化的机会。现在，解析器的run函数接受一个字符串，并返回一个全新的字符串，该字符串表示在解析过程中使用了输入的某个子集后剩下的内容。我们可以通过改变输入来表示消耗来提高效率。

我们以前在可组合架构中证明了在A中获取值并在A中返回值的函数与仅获取inout A并返回Void的函数之间存在等价性：

// (A)       -> A
// (inout A) -> Void

您可以轻松构建在这两种类型的函数之间通用转换。通常来说，如果函数签名中的某个类型在函数箭头的每一侧出现一次，则可以将其转换为接受inout输入且不再返回该类型的函数。

struct Parser<A> {
//  let run: (String) -> (match: A?, rest: String)
  let run: (inout String) -> A?
}

现在我们必须修复int解析器。我们将对字符串进行适当的变异以使用前缀，而不是返回新字符串和结果。

let int = Parser<Int> { str in
  let prefix = str.prefix(while: { $0.isNumber })
  guard let match = Int(prefix) else { return nil }
  str.removeFirst(prefix.count)
  return match
}

现在我们的构建不起作用，因为它们需要一个inout参数，所以现在让我们重新创建run的非变异版本，以便我们可以继续以这种方式使用它：

extension Parser {
  func run(_ str: String) -> (match: A?, rest: String) {
    var str = str
    let match = self.run(&str)
    return (match, str)
  }
}

一切都像以前一样继续工作。

5. Optimized parsing with substring

我们还可以做一个优化，这是一个很大的优化。现在我们正在对字符串进行操作，每次从字符串的前面消耗一点，我们就从run函数返回创建的一个全新的字符串。如果我们试图解析大的输入字符串，这可能会非常低效。但不一定要这样。由于我们通常从字符串的前面开始消费，如果我们可以做一些非常轻量级的事情，比如更改字符串的startIndex以指向字符串中的字符，该怎么办。

事实证明，这正是Swift中Substring类型的工作方式。因此，如果我们使用字符串的子字符串，也许我们可以移动索引，使事情真正有效果。

子字符串是一些字符串存储的包装器，它旨在与其他Substring实例共享该存储。然后，子字符串的某些突变可以非常有效地完成，因为在内部它所做的只是在指示字符串开始和结束位置的索引之间移动。

每个Swift集合都有一个底层SubSequence类型，它们都旨在提高集合的使用效率。

让我们尝试更新解析器来处理Substring，看看哪些是正确的，哪些是错误的。我们将首先更改它的mutating run函数以使用inout Substring而不是String。

struct Parser<A> {
  let run: (inout Substring) -> A?
}

这破坏了我们的run的非变异版本，该版本仍在使用普通ole字符串：

func run(_ str: String) -> (match: A?, rest: String) {
  var str = str
  let match = self.run(&str)

🛑 Cannot invoke ‘run’ with an argument list of type ‘(inout String)’

现在，我们可以通过使用其substring表示来避免字符串复制，我们可以通过使用Swift所称的“无界范围表达式”进行订阅来获得该表示：

var str = str[...]

这看起来有点时髦，但它实际上给了我们对字符串的看法，而不是创建一个全新的。

最后，我们应该更新返回值以返回该子字符串。

func run(_ str: String) -> (match: A?, rest: Substring) {
  var str = str[...]
  let match = self.run(&str)
  return (match, str)
}

这就是需要改变的一切！用于突变子字符串的接口与用于突变字符串的接口相同，但我们将通过在字符串中使用视图而不是副本来提高性能。

我们仍然有整个字符串必须在内存中的限制，这意味着解析一个非常大的字符串是没有效率的，但是到目前为止我们所做的优化非常简单，已经给我们带来了很多好处，所以让我们继续努力吧。

6. Till next time

现在我们有了解析器的“final form”：它是一个函数，它获取一个in-out子字符串并生成一个可选的匹配项。因此，让我们再创建几个解析器，这样我们就可以了解这是如何进行的。

Kayouyou's Den