应用程序解析比单一解析有哪些好处？

人们似乎一致认为应该使用 Parsec 作为应用程序而不是单子。应用程序解析比单一解析有哪些好处？

  • 风格
  • 表演
  • 抽象

单子语法分析出来了吗？

12456 次浏览
小开

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

DoaitseSwierstra 的 UU 解析如果仅用于应用程序，则效率更高。

小开

单子是严格的 更有特色的抽象比应用程序。你可以写

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

但是没有办法写

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

所以，是的，它本质上是一个 风格的问题。我想如果您使用 return和 ap，那么应该有使用 pure和 <*>的 没有性能损失。因为 Applicative 是一个比 Monad 小得多的接口，这意味着 <*>有时可以比 ap更高度优化。(但是使用聪明的 GHC 重写规则，无论如何都可以实现相同的优化。)

单子语法分析出来了吗？

由于 Monads 是 Applicative 的一个子集，因此我认为应用解析是一元解析的一个子集。

小开

我认为在任何上下文中更喜欢应用程序解析器而不是一元解析器的主要原因与更喜欢应用程序代码而不是一元代码的主要原因是相同的: 应用程序功能较弱，使用起来更简单。

这是一个更一般的工程格言的例子: 使用最简单的工具来完成工作。不要使用叉车时，一个推车就可以了。不要用锯子剪优惠券。如果 IO可以是纯的，就不要用它编写代码。简单点。

但有时候，你 需要的额外功率 Monad。当您需要根据到目前为止所计算的内容更改计算过程时，就是这种情况的明显标志。在解析术语中，这意味着根据到目前为止解析的内容确定如何解析接下来的内容; 换句话说，您可以通过这种方式构造与上下文相关的语法。

小开
最佳答案

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

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

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

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

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. DoaitseSwierstra 和 Luc Duponcheel 的论文 确定性，纠错组合器解析器所示。

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

小开

如果一个解析器纯粹是应用性的，那么在运行它之前就可以分析它的结构并对其进行“优化”。如果一个解析器是单子的，那么它基本上就是一个图灵完成的程序，对它执行几乎任何有趣的分析都相当于解决了停止问题(也就是说，不可能)。

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


提交答案