69

似乎有一个共识，您应该将 Parsec 用作应用程序而不是 monad。与单子解析相比，应用解析有什么好处？

  • 风格
  • 表现
  • 抽象

monadic 解析出来了吗？

4

5 回答 5

93

一元解析和应用解析之间的主要区别在于如何处理顺序组合。在应用解析器的情况下，我们使用(<*>)，而对于 monad 我们使用(>>=)。

(<*>) :: Parser (a -> b) -> Parser a -> Parser b
(>>=) :: Parser a -> (a -> Parser b) -> Parser b

monadic 方法更灵活，因为它允许第二部分的语法依赖于第一部分的结果，但在实践中我们很少需要这种额外的灵活性。

你可能认为拥有一些额外的灵活性不会有什么坏处，但实际上它可以。它阻止我们在不运行解析器的情况下对它进行有用的静态分析。例如，假设我们想知道解析器是否可以匹配空字符串，以及匹配中可能的第一个字符。我们想要函数

empty :: Parser a -> Bool
first :: Parser a -> Set Char

使用应用解析器，我们可以轻松回答这个问题。（我在这里有点作弊。想象一下，我们有一个数据构造函数对应于我们(<*>)的(>>=)候选解析器“语言”）。

empty (f <*> x) = empty f && empty x
first (f <*> x) | empty f   = first f `union` first x
                | otherwise = first f

然而，使用一元解析器，我们不知道第二部分的语法是什么，而不知道输入。

empty (x >>= f) = empty x && empty (f ???)
first (x >>= f) | empty x   = first x `union` first (f ???)
                | otherwise = first x

通过允许更多，我们能够减少推理。这类似于动态和静态类型系统之间的选择。

但这有什么意义呢？我们可以将这些额外的静态知识用于什么？好吧，例如，我们可以使用它来避免在 LL(1) 解析中回溯，方法是将下一个字符与first每个备选字符的集合进行比较。first我们还可以通过检查两个备选方案的集合是否重叠来静态地确定这是否会产生歧义。

另一个例子是它可以用于错误恢复，如S. Doaitse Swierstra 和 Luc Duponcheel的论文Deterministic, Error-Correcting Combinator Parsers所示。

但是，通常情况下，您正在使用的解析库的作者已经在应用解析和单子解析之间做出了选择。当像 Parsec 这样的库同时公开这两个接口时，选择使用哪一个纯粹是一种风格。在某些情况下，应用程序代码比单子代码更容易阅读，有时情况正好相反。

于 2011-10-22T23:45:53.160 回答
14

如果解析器纯粹是应用性的，则可以在运行之前分析其结构并“优化”它。如果解析器是单子的，那么它基本上是一个图灵完备的程序，并且对其执行几乎任何有趣的分析都相当于解决停机问题（即，不可能）。

哦，是的，还有风格上的差异......

于 2011-10-27T20:14:03.713 回答
11

我可以看到更喜欢应用程序解析器而不是 monadic 解析器的主要原因与在任何情况下更喜欢应用程序代码而不是 monadic 代码的主要原因相同：应用程序功能不那么强大，使用起来更简单。

这是更通用的工程格言的一个例子：使用完成工作的最简单的工具。当小车可以使用时，不要使用叉车。不要使用台锯切割优惠券。不要在IO可能是纯代码的情况下编写代码。把事情简单化。

但有时，您需要. Monad一个明确的迹象是，当您需要根据目前已计算的内容更改计算过程时。在解析方面，这意味着根据到目前为止已经解析的内容来确定如何解析接下来的内容；换句话说，您可以通过这种方式构建上下文相关的语法。

于 2011-10-22T23:02:08.573 回答
4

使用 Parsec，使用 Applicative 的好处就是风格。Monad 的优势在于它更强大——你可以实现上下文敏感的解析器。

如果仅用于应用程序，Doaitse Swierstra 的 UU 解析会更有效。

于 2011-10-22T19:10:16.230 回答
3

Monads 严格来说是比 Applicatives更具特征的抽象。你可以写

instance (Monad m) => Applicative m where
  pure  = return
  (<*>) = ap

但是没有办法写

instance (Applicative a) => Monad a where
  return = pure
  (>>=) = ???

所以是的，这本质上是一个风格问题。我想如果你使用returnand ，那么使用andap应该没有性能损失。pure<*>因为 Applicative 是一个严格小于 Monad 的接口，这意味着它<*>有时可以比ap. （但通过巧妙的 GHC 重写规则，通常可以实现相同的优化。）

monadic 解析出来了吗？

由于 Monads 是 Applicatives 的一个子集，我会得出结论，applicative 解析是 monadic 解析的一个子集。

于 2011-10-22T20:51:52.787 回答